In this dissertation, we study iterative methods for computing eigenvalues and exponentials of large matrices. These types of computational problems arise in a large number of applications, including mathematical models in economics, physical and biological processes. Although numerical methods for computing eigenvalues and matrix exponentials have been well studied in the literature, there is a lack of analysis in inexact iterative methods for eigenvalue computation and certain variants of the Krylov subspace methods for approximating the matrix exponentials. In this work, we proposed an inexact inverse subspace iteration method that generalizes the inexact inverse iteration for computing multiple and clustered eigenvalues of a generalized eigenvalue problem. Compared with other methods, the inexact inverse subspace iteration method is generally more robust. Convergence analysis showed that the linear convergence rate of the exact case is preserved. The second part of the work is to present an inverse Lanczos method to approximate the product of a matrix exponential and a vector. This is proposed to allow use of larger time step in a time-propagation scheme for solving linear initial value problems. Error analysis is given for the inverse Lanczos method, the standard Lanczos method as well as the shift-and-invert Lanczos method. The analysis demonstrates different behaviors of these variants and helps in choosing which variant to use in practice.

No description available.

This thesis develops ways of localizing the Ritz values of non-Hermitian matrices. The restarted Arnoldi method with exact shifts, useful for determining a few desired eigenvalues of a matrix, employs Ritz values to refine eigenvalue estimates. In the Hermitian case, using selected Ritz values produces convergence due to interlacing. No generalization of interlacing exists for non-Hermitian matrices, and as a consequence no satisfactory general convergence theory exists. To study Ritz values, I propose the inverse field of values problem for k Ritz values, which asks if a set of k complex numbers can be Ritz values of a matrix. This problem is always solvable for k = 1 for any complex number in the field of values; I provide an improved algorithm for finding a Ritz vector in this case. I show that majorization can be used to characterize, as well as localize, Ritz values. To illustrate the difficulties of characterizing Ritz values, this work provides a complete analysis of the Ritz values of two 3 × 3 matrices: a Jordan block and a normal matrix. By constructing conditions for localizing the Ritz values of a matrix with one simple, normal, sought-after eigenvalue, this work develops sufficient conditions that guarantee convergence of the restarted Arnoldi method with exact shifts. For general matrices, the conditions provide insight into the subspace dimensions that ensure that shifts do not cluster near the wanted eigenvalue. As Ritz values form the basis for many iterative methods for determining eigenvalues and solving linear systems, an understanding of Ritz value behavior for non-Hermitian matrices has the potential to inform a broad range of analysis.

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.

No description available.

A investigação dos mecanismos de instabilidade pode ter um papel importante no entendimento do processo laminar para turbulento de um escoamento. Análise de instabilidade de uma camada limite de uma linha de estagnação compressível foi realizada no contexto de teoria linear BiGlobal. O estudo dos mecanismos de instabilidade deste escoamento pode proporcionar uma visão útil no desenho aerodinâmico das asas. Um novo procedimento foi desenvolvido e implementado computacionalmente de maneira sequencial e paralela para o estudo de instabilidade BiGlobal. O mesmo baseia-se em formar a matriz esparsa associada ao problema discretizado por dois métodos: pontos de colocação de Chebyshev-Gauss-Lobatto e diferenças finitas, além das combinações destes métodos. Isto permitiu o uso de bibliotecas computacionais eficientes para resolver o sistema linear associado ao problema de autovalor utilizando o algoritmo de Arnoldi. O desempenho do método numérico e código computacional proposto são analisados do ponto de vista do uso de métodos de ordenação dos elementos da matriz, coeficientes de preenchimento, memória e tempo computacional a fim de determinar a solução mais eficiente para um problema físico geral com técnicas de matrizes esparsas. Um estudo paramétrico da instabilidade da camada limite de uma linha de estagnação foi realizado incluindo o estudo dos efeitos de compressibilidade. O excelente desempenho código computacional permitiu obter as curvas neutras e seus respectivos valores críticos para a faixa de número de Mach 0 \'< OU =\' Ma \'< OU =\' 1. Os resultados confirmam a teoria assintótica apresentada por (THEOFILIS; FEDOROV; COLLIS, 2004) e mostram que o incremento do número de Mach reduz o numero de Reynolds crítico e a faixa instável do número de ondas. / Investigation of linear instability mechanisms is essential for understanding the process of transition from laminar to turbulent flow. An algorithm for the numerical solution of the compressible BiGlobal eigenvalue problem is developed. This algorithm exploits the sparsity of the matrices resulting from the spatial discretization of the enigenvalue problem in order to improve the performance in terms of both memory and CPU time over previous dense algebra solutions. Spectral collocation and finite differences spatial discretization methods are implemented, and a performance study is carried out in order to determine the best practice for the efficient solution of a general physical problem with sparse matrix techniques. A combination of spectral collocation and finite differences can further improve the performance. The code developed is then applied in order to revisit and complete the parametric analyses on global instability of the compressible swept Hiemenz flow initiated in (THEOFILIS; FEDOROV; COLLIS, 2004) and obtain neutral curves of this flow as a function of the Mach number in the 0 \'< OU =\' Ma \'< OU =\' 1 range. The present numerical results fully confirm the asymptotic theory results presented in (THEOFILIS; FEDOROV; COLLIS, 2004). This work presents a complete parametric study of the instability properties of modal three dimensional disturbances in the subsonic range for the flow conguration at hand. Up to the subsonic maximum Mach number value studied, it is found that an increase in this parameter reduces the critical Reynolds number and the range of the unstable spanwise wavenumbers.

A investigação dos mecanismos de instabilidade pode ter um papel importante no entendimento do processo laminar para turbulento de um escoamento. Análise de instabilidade de uma camada limite de uma linha de estagnação compressível foi realizada no contexto de teoria linear BiGlobal. O estudo dos mecanismos de instabilidade deste escoamento pode proporcionar uma visão útil no desenho aerodinâmico das asas. Um novo procedimento foi desenvolvido e implementado computacionalmente de maneira sequencial e paralela para o estudo de instabilidade BiGlobal. O mesmo baseia-se em formar a matriz esparsa associada ao problema discretizado por dois métodos: pontos de colocação de Chebyshev-Gauss-Lobatto e diferenças finitas, além das combinações destes métodos. Isto permitiu o uso de bibliotecas computacionais eficientes para resolver o sistema linear associado ao problema de autovalor utilizando o algoritmo de Arnoldi. O desempenho do método numérico e código computacional proposto são analisados do ponto de vista do uso de métodos de ordenação dos elementos da matriz, coeficientes de preenchimento, memória e tempo computacional a fim de determinar a solução mais eficiente para um problema físico geral com técnicas de matrizes esparsas. Um estudo paramétrico da instabilidade da camada limite de uma linha de estagnação foi realizado incluindo o estudo dos efeitos de compressibilidade. O excelente desempenho código computacional permitiu obter as curvas neutras e seus respectivos valores críticos para a faixa de número de Mach 0 \'< OU =\' Ma \'< OU =\' 1. Os resultados confirmam a teoria assintótica apresentada por (THEOFILIS; FEDOROV; COLLIS, 2004) e mostram que o incremento do número de Mach reduz o numero de Reynolds crítico e a faixa instável do número de ondas. / Investigation of linear instability mechanisms is essential for understanding the process of transition from laminar to turbulent flow. An algorithm for the numerical solution of the compressible BiGlobal eigenvalue problem is developed. This algorithm exploits the sparsity of the matrices resulting from the spatial discretization of the enigenvalue problem in order to improve the performance in terms of both memory and CPU time over previous dense algebra solutions. Spectral collocation and finite differences spatial discretization methods are implemented, and a performance study is carried out in order to determine the best practice for the efficient solution of a general physical problem with sparse matrix techniques. A combination of spectral collocation and finite differences can further improve the performance. The code developed is then applied in order to revisit and complete the parametric analyses on global instability of the compressible swept Hiemenz flow initiated in (THEOFILIS; FEDOROV; COLLIS, 2004) and obtain neutral curves of this flow as a function of the Mach number in the 0 \'< OU =\' Ma \'< OU =\' 1 range. The present numerical results fully confirm the asymptotic theory results presented in (THEOFILIS; FEDOROV; COLLIS, 2004). This work presents a complete parametric study of the instability properties of modal three dimensional disturbances in the subsonic range for the flow conguration at hand. Up to the subsonic maximum Mach number value studied, it is found that an increase in this parameter reduces the critical Reynolds number and the range of the unstable spanwise wavenumbers.

This thesis primarily concerns kinematic dynamo action by the 1:1:1 ABC flow, in the highly conducting limit of large magnetic Reynolds number Rm. The flow possesses 24 symmetries, with a symmetry group isomorphic to the group O24 of orientation-preserving transformations of a cube. These symmetries are exploited to break up the linear eigenvalue problem into five distinct symmetry classes, which we label I-V. The thesis discusses how to reduce the scale of the numerical problem to a subset of Fourier modes for a magnetic field in each class, which then may be solved independently to obtain distinct branches of eigenvalues and magnetic field eigenfunctions. Two numerical methods are employed: the first is to time step a magnetic field in a given symmetry class and obtain the growth rate and frequency by measuring the magnetic energy as a function of time. The second method involves a more direct determination of the eigenvalue using the eigenvalue solver ARPACK for sparse matrix systems, which employs an implicitly restarted Arnoldi method. The two methods are checked against each other, and compared for efficiency and reliability. Eigenvalue branches for each symmetry class are obtained for magnetic Reynolds numbers Rm up to 10^4 together with spectra and magnetic field visualisations. A sequence of branches emerges as Rm increases and the magnetic field structures in the different branches are discussed and compared. All symmetry classes are found to contain a dynamo, though dynamo effectiveness varies greatly between classes, suggesting that the symmetries play an important role in the field amplification mechanisms. A closely related problem, that of linear hydrodynamic stability, is also explored in the limit of large Reynolds number Re. As the same symmetry considerations apply, the five symmetry classes of the linear instability can be resolved independently, reducing the size of the problem and allowing exploration of the effects of the symmetries on instability growth rate. Results and visualisations are obtained for all five classes for Re up to 10^3, with comparisons drawn between the structures seen in each class and with those found in the analogous magnetic problem. For increasing Re, multiple mode crossings are observed within each class, with remarkably similar growth rates seen in all classes at Re=10^3, highlighting a lack of dependence on the symmetries of the instability, in contrast with the magnetic problem. This thesis also investigates the problem of large-scale magnetic fields in the 1:1:1 ABC flow through the introduction of Bloch waves that modify the periodicity of the magnetic field relative to the flow. Results are found for a field with increased periodicity in a single direction for Rm up to 10^3; it is established that the optimal scale for dynamo action varies as Rm increases, settling on a consistent scale for large Rm. The emerging field structures are studied and linked with those of the original dynamo problem. On contrasting this method with a previous study in which the flow is instead rescaled, it is shown that the use of Bloch waves drastically increases the range of possible scales, whilst cutting required computing time. Through a multiple-scale analysis, the contribution from the alpha-effect is calculated for the 1:1:1 ABC flow and is seen in growth rates for Rm &lt;&lt; 1.

A multiple-point Arnoldi method is derived for model reduction of computational fluid dynamic systems. By choosing the number of frequency interpolation points and the number of Arnoldi vectors at each frequency point, the user can select the accuracy and range of validity of the resulting reduced-order model while balancing computational expense. The multiple-point Arnoldi approach is combined with a singular value decomposition approach similar to that used in the proper orthogonal decomposition method. This additional processing of the basis allows a further reduction in the number of states to be obtained, while retaining a significant computational cost advantage over the proper orthogonal decomposition. Results are presented for a supersonic diffuser subject to mass flow bleed at the wall and perturbations in the incoming flow. The resulting reduced-order models capture the required dynamics accurately while providing a significant reduction in the number of states. The reduced-order models are used to generate transfer function data, which are then used to design a simple feedforward controller. The controller is shown to work effectively at maintaining the average diffuser throat Mach number. / Singapore-MIT Alliance (SMA)

We present a comparative study of the application of modern eigenvalue algorithms to an eigenvalue problem arising in quantum physics, namely, the computation of a few interior eigenvalues and their associated eigenvectors for the large, sparse, real, symmetric, and indefinite matrices of the Anderson model of localization. We compare the Lanczos algorithm in the 1987 implementation of Cullum and Willoughby with the implicitly restarted Arnoldi method coupled with polynomial and several shift-and-invert convergence accelerators as well as with a sparse hybrid tridiagonalization method. We demonstrate that for our problem the Lanczos implementation is faster and more memory efficient than the other approaches. This seemingly innocuous problem presents a major challenge for all modern eigenvalue algorithms.