Analysis of large networks in biology, science, technology and social systems have become very popular recently. These networks are mathematically represented as graphs. The task is then to extract relevant qualitative information about the empirical networks from the analysis of these graphs. It was found that a graph can be conveniently represented by the spectrum of a suitable difference operator, the normalized graph Laplacian, which underlies diffusions and random walks on graphs. When applied to large networks, this requires computation of the spectrum of large matrices. The normalized Laplacian matrices representing large networks are usually sparse and unstructured. The thesis consists in a systematic evaluation of the available eigenvalue solvers for nonsymmetric large normalized Laplacian matrices describing directed graphs of empirical networks. The methods include several Krylov subspace algorithms like implicitly restarted Arnoldi method, Krylov-Schur method and Jacobi-Davidson methods which are freely available as standard packages written in MATLAB or SLEPc, in the library written C++. The normalized graph Laplacian as employed here is normalized such that its spectrum is confined to the range [0, 2]. The eigenvalue distribution plays an important role in network analysis. The numerical task is then to determine the whole spectrum with appropriate eigenvalue solvers. A comparison of the existing eigenvalue solvers is done with Paley digraphs with known eigenvalues and for citation networks in sizes 400, 1100 and 4500 by computing the residuals.

Orientadores: Carlos Eduardo Durán Fernandez, Marcos Benevenutto Jardim / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-16T11:28:16Z (GMT). No. of bitstreams: 1 Vitorio_HenriquedeBarrosCorreia_D.pdf: 1074812 bytes, checksum: e23ca71f5e87d6990c05425cdcb87bee (MD5) Previous issue date: 2010 / Resumo: A presente tese dá continuidade ao recente trabalho de J.C . Álvarez e C.E. Durán acerca dos invariantes geométricos de uma classe genérica de curvas em variedades de Grassmann, ditas "curvas fanning". Mais precisamente, considera-se como tais curvas de planos lagrangeanos comportam-se mediante uma redução simplética, e conclui-se a existência de dois novos invariantes que desempenham um papel fundamental neste contexto, mais notavelmente a maneira pela qual eles generalizam as bem conhecidas fórmulas de O'Neill para submersões isométricas / Abstract: The present thesis gives continuity to the recent work of J.C. Álvarez e C.E. Durán about the geometric invariants of a generic class of curves in the Grassmann manifolds, called "fanning curves". More precisely, we look at how such curves of lagrangean planes behave under a symplectic reduction, and establish the existence of two new invariants which play a fundamental role in that context, more notably the way they generalize the well known O'Neill's formulas for isometric submersions / Doutorado / Matematica / Doutor em Matemática

[pt] O problema do subespaço invariante consiste na seguinte pergunta: será que todo operador (i.e., transformação linear limitada) atuando em um espaço de Hilbert separável (complexo de dimensão infinita) tem subespaço invariante nãotrivial? Este é, possivelmente, o mais importante problema em aberto na teoria de operadores. Em particular, o problema do subespaço invariante permanece em aberto (pelo menos até a presente data) para operadores hiponormais, ou seja, ainda não se sabe se todo operador hiponormal (atuando em um espaço de Hilbert complexo separável) tem subespaço invariante não-trivial. O objetivo desta dissertação é apresentar, de maneira unificada, um levantamento sobre subespaços invariantes para operadores hiponormais. Inicialmente, o problema do subespaço invariante é abordado em sua forma geral (sem restrição a classes de operadores) onde diversos resultados clássicos são expostos. Em seguida, o problema específico de se encontrar subespaços invariantes para operadores hiponormais é apresentado de maneira sistemática. Em particular, investigamos propriedades do espectro de um operador hiponormal que não tenha subespaço invariante não trivial. / [en] The invariant subspace problem is: does every operator acting on an infinite-dimensional complex separable Hilbert space have a nontrivial invariant subspace? This is, probably, the most important open question in the operator theory. In particular, the problem of the invariant subspace remains open (at least until now) for hyponormal operators, that is, it is still unknown whether every hyponormal operator (on a complex separable Hilbert space) has a nontrivial invariant subspace. The purpose of these dissertation is to present, in an unified way, a survey on invariant subspaces for hyponormal operators. At first, the invariant subspace problem is posed in a general form (without any restriction on the operator classes), where some of classical results are discussed. Secondly, the specific problem of finding invariant subspaces for hyponormal operators is presented in a systematic way and, in particular, we show some characteristics of the spectrum of a hyponormal operator with no nontrivial invariant subspace.

Beaucoup de phénomènes physiques sont modélisés par des équations aux dérivées partielles, la discrétisation de ces équations conduit souvent à des systèmes dynamiques (continus ou discrets) dépendant d'un vecteur de contrôle dont le choix permet de stabiliser le système dynamique. Comme ces problèmes sont, dans la pratique, de grandes tailles, il est intéressant de les étudier via un autre problème dérivé réduit et plus proche du modèle initial. Dans cette thèse, on introduit et on étudie de nouvelles méthodes basées sur les processus de type Krylov rationnel afin d'extraire un modèle réduit proche du modèle original. Des applications numériques seront faites à partir de problèmes pratiques. Après un premier chapitre consacré au rappel de quelques outils mathématiques, on s'intéresse aux méthodes basées sur le processus d'Arnoldi rationnel par blocs pour réduire la taille d'un système dynamique de type Multi-Input/Multi-Output (MIMO). On propose une sélection adaptative de choix de certains paramètres qui sont cruciaux pour l'efficacité de la méthode. On introduit aussi un nouvel algorithme adaptatif de type Arnoldi rationnel par blocs afin de fournir une nouvelle relation de type Arnoldi. Dans la deuxième partie de ce travail, on introduit la méthode d'Arnoldi rationnelle globale, comme alternative de la méthode d'Arnoldi rationnel par blocs. On définit la projection au sens global, et on applique cette méthode pour approcher les fonctions de transfert. Dans la troisième partie, on s'intéresse à la méthode d'Arnoldi étendue (qui est un cas particulier de la méthode d'Arnoldi rationnelle) dans les deux cas (global et par blocs), on donnera quelques nouvelles propriétés algébriques qui sont appliquées aux problèmes des moments. On consièdère dans la quatrième partie la méthode de troncature balancée pour la réduction de modèle. Ce procédé consiste à résoudre deux grandes équations algébriques de Lyapunov lorsque le système est stable ou à résoudre deux équations de Riccati lorsque le système est instable. Comme ces équations sont de grandes tailles, on va appliquer la méthode de Krylov rationnel par blocs pour approcher la solution de ces équations. Le travail de cette thèse sera cloturé par une nouvelle idée, dans laquelle on définit un nouvel espace sous le nom de sous-espace de Krylov rationnelle étendue qui sera utilisée pour la réduction du modèle. / Many physical phenomena are modeled by PDEs. The discretization of these equations often leads to dynamical systems (continuous or discrete) depending on a control vector whose choice can stabilize the dynamical system. As these problems are, in practice, of a large size, it is interesting to study the problem through another one which is reduced and close to the original model. In this thesis, we develop and study new methods based on rational Krylov-based processes for model reduction techniques in large-scale Multi-Input Multi-Output (MIMO) linear time invariant dynamical systems. In chapter 2 the methods are based on the rational block Arnoldi process to reduce the size of a dynamical system through its transfer function. We provide an adaptive selection choice of shifts that are crucial for the effectiveness of the method. We also introduce a new adaptive Arnoldi-like rational block algorithm to provide a new type of Arnoldi's relationship. In Chapter 3, we develop the new rational global Arnoldi method which is considered as an alternative to the rational block Arnoldi process. We define the projection in the global sense, and apply this method to extract reduced order models that are close to the large original ones. Some new properties and applications are also presented. In chapter 4 of this thesis, we consider the extended block and global Arnoldi methods. We give some new algebraic properties and use them for approaching the firt moments and Markov parameters in moment matching methods for model reduction techniques. In chapter 5, we consider the method of balanced truncation for model reduction. This process is based on the soluytions of two major algebraic equations : Lyapunov equations when the system is stable or Riccati equations when the system is unstable. Since these equations are of large sizes, we will apply the rational block Arnoldi method for solving these equations. In chapter 6, we introduce a new method based on a new subspace called the extended-rational Krylov subspace. We introduce the extended-rational Krylov method which will be used for model reduction in large-scale dynamical systems.

This paper demonstrates the properties of a Hilbert structure. In order to have a Hilbert structure it is necessary to satisfy certain properties or axioms. The main body of the paper is centered on six questions that develop these ideas.

<div>Physical phenomena in nature are typically represented by complex systems of ordinary differential equations (ODEs) or partial differential equations (PDEs), modeling a wide range of spatio-temporal scales and multi-physics. The field of computational science has achieved indisputable success in advancing our understanding of the natural world - made possible through a combination of increasingly sophisticated mathematical models, numerical techniques and hardware resources. Furthermore, there has been a recent revolution in the data-driven sciences - spurred on by advances in the deep learning/stochastic optimization communities and the democratization of machine learning (ML) software.</div><div><br></div><div><div>With the ubiquity of use of computational models for analysis and prediction of physical systems, there has arisen a need for rigorously characterizing the effects of unknown variables in a system. Unfortunately, Uncertainty quantification (UQ) tasks such as model calibration, uncertainty propagation, and optimization under uncertainty, typically require several thousand evaluations of the underlying physical models. In order to deal with the high cost of the forward model, one typically resorts to the surrogate idea - replacing the true response surface with an approximation that is both accurate as well cheap (computationally speaking). However, state-ofart numerical systems are often characterized by a very large number of stochastic parameters - of the order of hundreds or thousands. The high cost of individual evaluations of the forward model, coupled with the limited real world computational budget one is constrained to work with, means that one is faced with the task of constructing a surrogate model for a system with high input dimensionality and small dataset sizes. In other words, one faces the <i>curse of dimensionality</i>.</div></div><div><br></div><div><div>In this dissertation, we propose multiple ways of overcoming the<i> curse of dimensionality</i> when constructing surrogate models for high-dimensional numerical simulators. The core idea binding all of our proposed approach is simple - we try to discover special structure in the stochastic parameter which captures most of the variance of the output quantity of interest. Our strategies first identify such a low-rank structure, project the high-dimensional input onto it, and then link the projection to the output. If the dimensionality of the low dimensional structure is small enough, learning the map between this reduced input space to the output is a much easier task in</div><div>comparison to the original surrogate modeling task.</div></div>

No description available.

Cardinality constrained optimization problems (CCOP) are a new class of optimization problems with many applications. In this thesis, we propose a framework called mathematical programs with disjunctive subspaces constraints (MPDSC), a special case of mathematical programs with disjunctive constraints (MPDC), to investigate CCOP. Our method is different from the relaxed complementarity-type reformulation in the literature. The first contribution of this thesis is that we study various stationarity conditions for MPDSC, and then apply them to CCOP. In particular, we recover disjunctive-type strong (S-) stationarity and Mordukhovich (M-) stationarity for CCOP, and then reveal the relationship between them and those from the relaxed complementarity-type reformulation. The second contribution of this thesis is that we obtain some new results for MPDSC, which do not hold for MPDC in general. We show that many constraint qualifications like the relaxed constant positive linear dependence (RCPLD) coincide with their piecewise versions for MPDSC. Based on such result, we prove that RCPLD implies error bounds for MPDSC. These two results also hold for CCOP. All of these disjunctive-type constraint qualifications for CCOP derived from MPDSC are weaker than those from the relaxed complementarity-type reformulation in some sense. / Graduate

No description available.

No description available.