Krylov subspace methods are the state-of-the-art iterative algorithms for solving large, sparse systems of equations, which are ubiquitous throughout scientific computing. Even with Krylov methods, these problems are often infeasible to solve on standard workstation computers and must be solved instead on supercomputers. Most modern supercomputers fall into the category of “heterogeneous architectures”, typically meaning a combination of CPU and GPU processors. Thus, development and analysis of Krylov subspace methods on these heterogeneous architectures is of fundamental importance to modern scientific computing. This dissertation focuses on how this relates to several specific problems. Thefirst analyzes the performance of block GMRES (BGMRES) compared to GMRES for linear systems with multiple right hand sides (RHS) on both CPUs and GPUs, and modelling when BGMRES is most advantageous over GMRES on the GPU. On CPUs, the current paradigm is that if one wishes to solve a system of equations with multiple RHS, BGMRES can indeed outperform GMRES, but not always. Our original goal was to see if there are some cases for which BGMRES is slower in execution time on the CPU than GMRES on the CPU, while on the GPU, the reverse holds. This is true, and we generally observe much faster execution times and larger improvements in the case of BGMRES on the GPU. We also observe that for any fixed matrix, when the number of RHS increase, there is a point in which the improvements start to decrease and eventually any advantage of the (unrestarted) block method is lost. We present a new computational model which helps us explain why this is so. The significance of this analysis is that it first demonstrates increased potential of block Krylov methods on heterogeneous architectures than on previously studied CPU-only machines. Moreover, the theoretical runtime model can be used to identify an optimal partitioning strategy of the RHS for solving systems with many RHS. The second problem studies the s-step GMRES method, which is an implementation of GMRES that attains high performance on modern heterogeneous machines by generating s Krylov basis vectors per iteration, and then orthogonalizing the vectors in a block-wise fashion. The use of s-step GMRES is currently limited because the algorithm is prone to numerical instabilities, partially due to breakdowns in a tall-and-skinny QR subroutine. Further, a conservatively small step size must be used in practice, limiting the algorithm’s performance. To address these issues, first a novel randomized tall-and-skinny QR factorization is presented that is significantly more stable than the current practical algorithms without sacrificing performance on GPUs. Then, a novel two-stage block orthogonalization scheme is introduced that significantly improves the performance of the s-step GMRES algorithm when small step sizes are used. These contributions help make s-step GMRES a more practical method in heterogeneous, and therefore exascale, environments. / Mathematics

Dynamical systems are mathematical models characterized by a set of differential or difference equations. Model reduction aims to replace the original system with a reduced system of significantly smaller dimension that still describes the important dynamics of the large-scale model. Interpolatory model reduction methods define a reduced model that interpolates the full model at selected interpolation points. The reduced model may be obtained through a Krylov reduction process or by using the Iterative Rational Krylov Algorithm (IRKA), which iterates this Krylov reduction process to obtain an optimal ℋ₂ reduced model. This dissertation studies interpolatory model reduction for first-order descriptor systems, second-order systems, and DAEs. The main computational cost of interpolatory model reduction is the associated linear systems. Especially in the large-scale setting, inexact solves become desirable if not necessary. With the introduction of inexact solutions, however, exact interpolation no longer holds. While the effect of this loss of interpolation has previously been studied, we extend the discussion to the preconditioned case. Then we utilize IRKA's convergence behavior to develop preconditioner updates. We also consider the interpolatory framework for DAEs and second-order systems. While interpolation results still hold, the singularity associated with the DAE often results in unbounded model reduction errors. Therefore, we present a theorem that guarantees interpolation and a bounded model reduction error. Since this theorem relies on expensive projectors, we demonstrate how interpolation can be achieved without explicitly computing the projectors for index-1 and Hessenberg index-2 DAEs. Finally, we study reduction techniques for second-order systems. Many of the existing methods for second-order systems rely on the model's associated first-order system, which results in computations of a 2𝑛 system. As a result, we present an IRKA framework for the reduction of second-order systems that does not involve the associated 2𝑛 system. The resulting algorithm is shown to be effective for several dynamical systems. / Ph. D.

Engineering problems frequently require solving a sequence of dual linear systems. This paper introduces recycling BiCG, that recycles the Krylov subspace from one pair of linear systems to the next pair. Augmented bi-Lanczos algorithm and modified two-term recurrence are developed for using the recycle space. Recycle space is built from the approximate invariant subspace corresponding to eigenvalues close to the origin. Recycling approach is extended to the CGS and the BiCGSTAB algorithms. Experiments on a convection-diffusion problem give promising results. / Master of Science

MOR (Model Order Reduction) est devenu un domaine très répondu dans la recherche grâce à l'intérêt qu'il peut apporter dans la réduction des systèmes, ce qui permet d'économiser du temps, de la mémoire et le coût de CPU pour les outils de CAO. Ce domaine contient principalement deux branches: linéaires et non linéaires. MOR linéaire est un domaine mature avec des techniques numériques bien établie et bien connus dans la domaine de la recherche, par contre le domaine non linéaire reste vague, et jusqu'à présent il n'a pas montré des bons résultats dans la simulation des circuits électriques. La recherche est toujours en cours dans ce domaine, en raison de l’intérêt qu'il peut fournir aux simulateurs contemporains, surtout avec la croissance des puces électroniques en termes de taille et de complexité, et les exigences industrielles vers l'intégration des systèmes sur la même puce.Une contribution significative, pour résoudre le problème de Harmonic Balance (Equilibrage Harmonique) en utilisant la technique MOR, a été proposé en 2002 par E. Gad et M. Nakhla. La technique a montré une réduction substantielle de la dimension du système, tout en préservant, en sortie, la précision de l'analyse en régime permanent. Cette méthode de MOR utilise la technique de projection par l'intermédiaire de Krylov, et il préserve la passivité du système. Cependant, il souffre de quelques limitations importantes dans la construction de la matrice “pre-conditioner“ qui permettrait de réduire le système. La limitation principale est la nécessité d'une factorisation explicite comme une suite numérique de l'équation des dispositifs non linéaires . cette limitation rend la technique difficile à appliquer dans les conditions générales d'un simulateur. Cette thèse examinera les aspects non linéaires du modèle de réduction pour les équations de bilan harmoniques, et il étudiera les solutions pour surmonter les limitations mentionnées ci-dessus, en particulier en utilisant des approches de dérivateur numériques. / MOR recently became a well-known research field, due to the interest that it shows in reducing the system, which saves time, memory, and CPU cost for CAD tools. This field contains two branches, linear and nonlinear MOR, the linear MOR is a mature domain with well-established theory and numerical techniques. Meanwhile, nonlinear MOR domain is still stammering, and so far it didn’t show good and successful results in electrical circuit simulation. Some improvements however started to pop-up recently, and research is still going on this field because of the help that it can give to the contemporary simulators, especially with the growth of the electronic chips in terms of size and complexity due to industrial demands towards integrating systems on the same chip. A significant contribution in the MOR technique of HB solution has been proposed a decade ago by E. Gad and M. Nakhla. The technique has shown to provide a substantial system dimension reduction while preserving the precision of the output in steady state analysis. This MOR method uses the technique of projection via Krylov, and it preserves the passivity of the system. However, it suffers a number of important limitations in the construction of the pre-conditioner matrix which is ought to reduce the system. The main limitation is the necessity for explicit factorization as a power series of the equation of the nonlinear devices. This makes the technique difficult to apply in general purpose simulator conditions. This thesis will review the aspects of the nonlinear model order reduction technique for harmonic balance equations, and it will study solutions to overcome the above mentioned limitations, in particular using numerical differentiation approaches.

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.

Le sujet de cette thèse est le développement de méthodes itératives permettant la résolution degrands systèmes linéaires creux d'équations présentant plusieurs seconds membres simultanément. Ces méthodes seront en particulier utilisées dans le cadre d'une application géophysique : la migration sismique visant à simuler la propagation d'ondes sous la surface de la terre. Le problème prend la forme d'une équation d'Helmholtz dans le domaine fréquentiel en trois dimensions, discrétisée par des différences finies et donnant lieu à un système linéaire creux, complexe, non-symétrique, non-hermitien. De plus, lorsque de grands nombres d'onde sont considérés, cette matrice possède une taille élevée et est indéfinie. Du fait de ces propriétés, nous nous proposons d'étudier des méthodes de Krylov préconditionnées par des techniques hiérarchiques deux niveaux. Un tel pre-conditionnement s'est montré particulièrement efficace en deux dimensions et le but de cette thèse est de relever le défi de l'adapter au cas tridimensionel. Pour ce faire, des méthodes de Krylov sont utilisées à la fois comme lisseur et comme méthode de résolution du problème grossier. Ces derniers choix induisent l'emploi de méthodes de Krylov dites flexibles. / The topic of this PhD thesis is the development of iterative methods for the solution of large sparse linear systems of equations with possibly multiple right-hand sides given at once. These methods will be used for a specific application in geophysics - seismic migration - related to the simulation of wave propagation in the subsurface of the Earth. Here the three-dimensional Helmholtz equation written in the frequency domain is considered. The finite difference discretization of the Helmholtz equation with the Perfect Matched Layer formulation produces, when high frequencies are considered, a complex linear system which is large, non-symmetric, non-Hermitian, indefinite and sparse. Thus we propose to study preconditioned flexible Krylov subspace methods, especially minimum residual norm methods, to solve this class of problems. As a preconditioner we consider multi-level techniques and especially focus on a two-level method. This twolevel preconditioner has shown efficient for two-dimensional applications and the purpose of this thesis is to extend this to the challenging three-dimensional case. This leads us to propose and analyze a perturbed two-level preconditioner for a flexible Krylov subspace method, where Krylov methods are used both as smoother and as approximate coarse grid solver.

La complexification de la modélisation multi-physique conduit d’une part à devoir simuler des systèmes d’équations différentielles ordinaires et d’équations différentielles algébriques de plus en plus grands en nombre d’inconnues et sur des temps de simulation longs. D’autre part l’évolution des architectures de calcul parallèle nécessite d’autres voies de parallélisation que la décomposition de système en sous-systèmes. Dans ce travail, nous proposons de concevoir des méthodes de décomposition de domaine pour la résolution d’EDO en temps. Nous reformulons le problème à valeur initiale en un problème aux valeurs frontières sur l’intervalle de temps symétrisé, sous l’hypothèse de réversibilité du flot. Nous développons deux méthodes, la première apparentée à une méthode de complément de Schur, la seconde basée sur une méthode de type Schwarz dont nous montrons la convergence pouvant être accélérée par la méthode d’Aitken dans le cadre linéaire. Afin d’accélérer la convergence de cette dernière dans le cadre non-linéaire, nous introduisons les techniques d’extrapolation et d’accélération de la convergence des suites non-linéaires. Nous montrons les avantages et les limites de ces techniques. Les résultats obtenus nous conduisent à développer l’accélération de la méthode de type Schwarz par une méthode de Newton. Enfin nous nous intéressons à l’étude de conditions de raccord non-linéaires adaptées à la décomposition de domaine de problèmes non-linéaires. Nous nous servons du formalisme hamiltonien à ports, issu du domaine de l’automatique, pour déduire les conditions de raccord dans le cadre l’équation de Saint-Venant et de l’équation de la chaleur non-linéaire. Après une étude analytique de la convergence de la DDM associée à ces conditions de transmission, nous proposons et étudions une formulation de Lagrangien augmenté sous l’hypothèse de séparabilité de la contrainte. / Complexification of multi-physics modeling leads to have to simulate systems of ordinary differential equations and algebraic differential equations with increasingly large numbers of unknowns and over large times of simulation. In addition the evolution of parallel computing architectures requires other ways of parallelization than the decomposition of system in subsystems. In this work, we propose to design domain decomposition methods in time for the resolution of EDO. We reformulate the initial value problem in a boundary values problem on the symmetrized time interval, under the assumption of reversibility of the flow. We develop two methods, the first connected with a Schur complement method, the second based on a Schwarz type method for which we show convergence, being able to be accelerated by the Aitken method within the linear framework. In order to accelerate the convergence of the latter within the non-linear framework, we introduce the techniques of extrapolation and of acceleration of the convergence of non-linear sequences. We show the advantages and the limits of these techniques. The obtained results lead us to develop the acceleration of the method of the type Schwarz by a Newton method. Finally we investigate non-linear matching conditions adapted to the domain decomposition of nonlinear problems. We make use of the port-Hamiltonian formalism, resulting from the control field, to deduce the matching conditions in the framework of the shallow-water equation and the non-linear heat equation. After an analytical study of the convergence of the DDM associated with these conditions of transmission, we propose and study a formulation of augmented Lagrangian under the assumption of separability of the constraint.

Numerical methods based on rational Krylov spaces have become an indispensable tool of scientific computing. In this thesis we study rational Krylov spaces by considering rational Krylov decompositions; matrix relations which, under certain conditions, are associated with these spaces. We investigate the algebraic properties of such decompositions and present an implicit Q theorem for rational Krylov spaces. We derive standard and harmonic Ritz extraction strategies for approximating the eigenpairs of a matrix and for approximating the action of a matrix function onto a vector. While these topics have been considered previously, our approach does not require the last pole to be infinite, which makes the extraction procedure computationally more efficient. Typically, the computationally most expensive component of the rational Arnoldi algorithm for computing a rational Krylov basis is the solution of a large linear system of equations at each iteration. We explore the option of solving several linear systems simultaneously, thus constructing the rational Krylov basis in parallel. If this is not done carefully, the basis being orthogonalized may become poorly conditioned, leading to numerical instabilities in the orthogonalization process. We introduce the new concept of continuation pairs which gives rise to a near-optimal parallelization strategy that allows to control the growth of the condition number of this non orthogonal basis. As a consequence we obtain a more accurate and reliable parallel rational Arnoldi algorithm. The computational benefits are illustrated using our high performance C++ implementation. We develop an iterative algorithm for solving nonlinear rational least squares problems. The difficulty is in finding the poles of a rational function. For this purpose, at each iteration a rational Krylov decomposition is constructed and a modified linear problem is solved in order to relocate the poles to new ones. Our numerical results indicate that the algorithm, called RKFIT, is well suited for model order reduction of linear time invariant dynamical systems and for optimisation problems related to exponential integration. Furthermore, we derive a strategy for the degree reduction of the approximant obtained by RKFIT. The rational function obtained by RKFIT is represented with the aid of a scalar rational Krylov decomposition and an additional coefficient vector. A function represented in this form is called an RKFUN. We develop efficient methods for the evaluation, pole and root finding, and for performing basic arithmetic operations with RKFUNs. Lastly, we discuss RKToolbox, a rational Krylov toolbox for MATLAB, which implements all our algorithms and is freely available from http://rktoolbox.org. RKToolbox also features an extensive guide and a growing number of examples. In particular, most of our numerical experiments are easily reproducible by downloading the toolbox and running the corresponding example files in MATLAB.

Les travaux de ce doctorat concernent le développement de méthodes itératives pour la résolution de systèmes linéaires creux de grande taille comportant de nombreux seconds membres. L’application visée est la résolution d’un problème inverse en géophysique visant à reconstruire la vitesse de propagation des ondes dans le sous-sol terrestre. Lorsque de nombreuses sources émettrices sont utilisées, ce problème inverse nécessite la résolution de systèmes linéaires complexes non symétriques non hermitiens comportant des milliers de seconds membres. Dans le cas tridimensionnel ces systèmes linéaires sont reconnus comme difficiles à résoudre plus particulièrement lorsque des fréquences élevées sont considérées. Le principal objectif de cette thèse est donc d’étendre les développements existants concernant les méthodes de Krylov par bloc. Nous étudions plus particulièrement les techniques de déflation dans le cas multiples seconds membres et recyclage de sous-espace dans le cas simple second membre. Des gains substantiels sont obtenus en terme de temps de calcul par rapport aux méthodes existantes sur des applications réalistes dans un environnement parallèle distribué. / This PhD thesis concerns the development of flexible Krylov subspace iterative solvers for the solution of large sparse linear systems of equations with multiple right-hand sides. Our target application is the solution of the acoustic full waveform inversion problem in geophysics associated with the phenomena of wave propagation through an heterogeneous model simulating the subsurface of Earth. When multiple wave sources are being used, this problem gives raise to large sparse complex non-Hermitian and nonsymmetric linear systems with thousands of right-hand sides. Specially in the three-dimensional case and at high frequencies, this problem is known to be difficult. The purpose of this thesis is to develop a flexible block Krylov iterative method which extends and improves techniques already available in the current literature to the multiple right-hand sides scenario. We exploit the relations between each right-hand side to accelerate the convergence of the overall iterative method. We study both block deflation and single right-hand side subspace recycling techniques obtaining substantial gains in terms of computational time when compared to other strategies published in the literature, on realistic applications performed in a parallel environment.