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.

Miniaturisation of electronic chips poses challenges at the design stage. The progressively decreasing circuit dimensions result in complex electrical behaviour that necessitates complex models. Simulation of complex circuit models involves extraordinarily large compu- tational complexity. Such complexity is better managed through Model Order Reduction. Model order reduction has been successful in large reductions in system order for most types of circuits, at high levels of accuracy. However, multiport circuits with large number of inputs/outputs, pose an additional computational challenge. A strategy based on exible clustering of interconnects results in more e cient reduction of multiport circuits. Clustering methods traditionally use Krylov-subspace methods such as PRIMA for the actual model reduction step. These clustering methods are unable to reduce the model order to the optimum extent. SVD-based methods like Truncated Balanced Realization have shown higher reduction potential than Krylov-subspace methods. In this thesis, the di erences in reduction potential and computational cost thereof between SVD-based methods and Krylov-subspace methods are identi ed, analyzed and quanti ed. A novel algorithm has been developed, utilizing a particular combination of both these methods to achieve better results. It enhances the clustering method for model reduction using Truncated Balanced Realization as a second-level reduction technique. The algorithm is tested and signi cant gains are illustrated. The proposed novel algorithm preserves the other advantages of the current clustering algorithm.

La performance d'un algorithme sur une architecture donnée dépend à la fois de la vitesse à laquelle le processeur effectue des opérations à virgule flottante (flops) et de la vitesse d'accès à la mémoire et au disque. Etant donné que le coût de la communication est beaucoup plus élevé que celui des opérations arithmétiques, celle-là forme un goulot d'étranglement dans les algorithmes numériques. Récemment, des méthodes de sous-espace de Krylov basées sur les méthodes 's-step' ont été développées pour réduire les communications. En effet, très peu de préconditionneurs existent pour ces méthodes, ce qui constitue une importante limitation. Dans cette thèse, nous présentons le préconditionneur nommé ''Communication-Avoiding ILU0'', pour la résolution des systèmes d’équations linéaires (Ax=b) de très grandes tailles. Nous proposons une nouvelle renumérotation de la matrice A ('alternating min-max layers'), avec laquelle nous montrons que le préconditionneur en question réduit la communication. Il est ainsi possible d’effectuer « s » itérations d’une méthode itérative préconditionnée sans communication. Nous présentons aussi deux nouvelles méthodes itératives, que nous nommons 'multiple search direction with orthogonalization CG' (MSDO-CG) et 'long recurrence enlarged CG' (LRE-CG). Ces dernières servent à la résolution des systèmes linéaires d’équations de très grandes tailles, et sont basées sur l’enrichissement de l’espace de Krylov par la décomposition du domaine de la matrice A. / The performance of an algorithm on any architecture is dependent on the processing unit’s speed for performing floating point operations (flops) and the speed of accessing memory and disk. As the cost of communication is much higher than arithmetic operations, and since this gap is expected to continue to increase exponentially, communication is often the bottleneck in numerical algorithms. In a quest to address the communication problem, recent research has focused on communication avoiding Krylov subspace methods based on the so called s-step methods. However there are very few communication avoiding preconditioners, and this represents a serious limitation of these methods. In this thesis, we present a communication avoiding ILU0 preconditioner for solving large systems of linear equations (Ax=b) by using iterative Krylov subspace methods. Our preconditioner allows to perform s iterations of the iterative method with no communication, by applying a heuristic alternating min-max layers reordering to the input matrix A, and through ghosting some of the input data and performing redundant computation. We also introduce a new approach for reducing communication in the Krylov subspace methods, that consists of enlarging the Krylov subspace by a maximum of t vectors per iteration, based on the domain decomposition of the graph of A. The enlarged Krylov projection subspace methods lead to faster convergence in terms of iterations and to parallelizable algorithms with less communication, with respect to Krylov methods. We discuss two new versions of Conjugate Gradient, multiple search direction with orthogonalization CG (MSDO-CG) and long recurrence enlarged CG (LRE-CG).

Title: Krylov Subspace Methods - Analysis and Application Author: Tomáš Gergelits Department: Department of Numerical Mathematics Supervisor: prof. Ing. Zdeněk Strakoš, DrSc., Department of Numerical Mathematics Abstract: Convergence behavior of Krylov subspace methods is often studied for linear algebraic systems with symmetric positive definite matrices in terms of the condition number of the system matrix. As recalled in the first part of this thesis, their actual convergence behavior (that can be in practice also substantially affected by rounding errors) is however determined by the whole spectrum of the system matrix, and by the projections of the initial residual to the associated invariant subspaces. The core part of this thesis investigates the spectra of infinite dimensional operators −∇ · (k(x)∇) and −∇ · (K(x)∇), where k(x) is a scalar coefficient function and K(x) is a symmetric tensor function, preconditioned by the Laplace operator. Subsequently, the focus is on the eigenvalues of the matrices that arise from the discretization using conforming finite elements. Assuming continuity of K(x), it is proved that the spectrum of the preconditi- oned infinite dimensional operator is equal to the convex hull of the ranges of the diagonal function entries of Λ(x) from the spectral decomposition K(x) =...

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Em uma grande gama de problemas físicos, governados por equações diferenciais, muitas vezes é de interesse obter-se soluções para o regime transiente e, portanto, deve-se empregar técnicas de integração temporal. Uma primeira possibilidade seria a de aplicar-se métodos explícitos, devido à sua simplicidade e eficiência computacional. Entretanto, esses métodos frequentemente são somente condicionalmente estáveis e estão sujeitos a severas restrições na escolha do passo no tempo. Para problemas advectivos, governados por equações hiperbólicas, esta restrição é conhecida como a condição de Courant-Friedrichs-Lewy (CFL). Quando temse a necessidade de obter soluções numéricas para grandes períodos de tempo, ou quando o custo computacional a cada passo é elevado, esta condição torna-se um empecilho. A fim de contornar esta restrição, métodos implícitos, que são geralmente incondicionalmente estáveis, são utilizados. Neste trabalho, foram aplicadas algumas formulações implícitas para a integração temporal no método Smoothed Particle Hydrodynamics (SPH) de modo a possibilitar o uso de maiores incrementos de tempo e uma forte estabilidade no processo de marcha temporal. Devido ao alto custo computacional exigido pela busca das partículas a cada passo no tempo, esta implementação só será viável se forem aplicados algoritmos eficientes para o tipo de estrutura matricial considerada, tais como os métodos do subespaço de Krylov. Portanto, fez-se um estudo para a escolha apropriada dos métodos que mais se adequavam a este problema, sendo os escolhidos os métodos Bi-Conjugate Gradient (BiCG), o Bi-Conjugate Gradient Stabilized (BiCGSTAB) e o Quasi-Minimal Residual (QMR). Alguns problemas testes foram utilizados a fim de validar as soluções numéricas obtidas com a versão implícita do método SPH. / In a wide range of physical problems governed by differential equations, it is often of interest to obtain solutions for the unsteady state and therefore it must be employed temporal integration techniques. One possibility could be the use of an explicit methods due to its simplicity and computational efficiency. However, these methods are often only conditionally stable and are subject to severe restrictions for the time step choice. For advective problems governed by hyperbolic equations, this restriction is known as the Courant-Friedrichs-Lewy (CFL) condition. When there is the need to obtain numerical solutions for long periods of time, or when the computational cost for each time step is high, this condition becomes a handicap. In order to overcome this restriction implicit methods can be used, which are generally unconditionally stable. In this study, some implicit formulations for time integration are used in the Smoothed Particle Hydrodynamics (SPH) method to enable the use of larger time increments and obtain a strong stability in the time evolution process. Due to the high computational cost required by the particles tracking at each time step, the implementation will be feasible only if efficient algorithms were applied for this type of matrix structure such as Krylov subspace methods. Therefore, we carried out a study for the appropriate choice of methods best suited to this problem, and the methods chosen were the Bi-Conjugate Gradient (BiCG), the Bi-Conjugate Gradient Stabilized (BiCGSTAB) and the Quasi-Minimal Residual(QMR). Some test problems were used to validate the numerical solutions obtained with the implicit version of the SPH method.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Em uma grande gama de problemas físicos, governados por equações diferenciais, muitas vezes é de interesse obter-se soluções para o regime transiente e, portanto, deve-se empregar técnicas de integração temporal. Uma primeira possibilidade seria a de aplicar-se métodos explícitos, devido à sua simplicidade e eficiência computacional. Entretanto, esses métodos frequentemente são somente condicionalmente estáveis e estão sujeitos a severas restrições na escolha do passo no tempo. Para problemas advectivos, governados por equações hiperbólicas, esta restrição é conhecida como a condição de Courant-Friedrichs-Lewy (CFL). Quando temse a necessidade de obter soluções numéricas para grandes períodos de tempo, ou quando o custo computacional a cada passo é elevado, esta condição torna-se um empecilho. A fim de contornar esta restrição, métodos implícitos, que são geralmente incondicionalmente estáveis, são utilizados. Neste trabalho, foram aplicadas algumas formulações implícitas para a integração temporal no método Smoothed Particle Hydrodynamics (SPH) de modo a possibilitar o uso de maiores incrementos de tempo e uma forte estabilidade no processo de marcha temporal. Devido ao alto custo computacional exigido pela busca das partículas a cada passo no tempo, esta implementação só será viável se forem aplicados algoritmos eficientes para o tipo de estrutura matricial considerada, tais como os métodos do subespaço de Krylov. Portanto, fez-se um estudo para a escolha apropriada dos métodos que mais se adequavam a este problema, sendo os escolhidos os métodos Bi-Conjugate Gradient (BiCG), o Bi-Conjugate Gradient Stabilized (BiCGSTAB) e o Quasi-Minimal Residual (QMR). Alguns problemas testes foram utilizados a fim de validar as soluções numéricas obtidas com a versão implícita do método SPH. / In a wide range of physical problems governed by differential equations, it is often of interest to obtain solutions for the unsteady state and therefore it must be employed temporal integration techniques. One possibility could be the use of an explicit methods due to its simplicity and computational efficiency. However, these methods are often only conditionally stable and are subject to severe restrictions for the time step choice. For advective problems governed by hyperbolic equations, this restriction is known as the Courant-Friedrichs-Lewy (CFL) condition. When there is the need to obtain numerical solutions for long periods of time, or when the computational cost for each time step is high, this condition becomes a handicap. In order to overcome this restriction implicit methods can be used, which are generally unconditionally stable. In this study, some implicit formulations for time integration are used in the Smoothed Particle Hydrodynamics (SPH) method to enable the use of larger time increments and obtain a strong stability in the time evolution process. Due to the high computational cost required by the particles tracking at each time step, the implementation will be feasible only if efficient algorithms were applied for this type of matrix structure such as Krylov subspace methods. Therefore, we carried out a study for the appropriate choice of methods best suited to this problem, and the methods chosen were the Bi-Conjugate Gradient (BiCG), the Bi-Conjugate Gradient Stabilized (BiCGSTAB) and the Quasi-Minimal Residual(QMR). Some test problems were used to validate the numerical solutions obtained with the implicit version of the SPH method.

[pt] Companhias de petróleo investindo no desenvolvimento de campos de hidrocarboneto dependem de estudos de reservatórios para realizarem previsões de produção e quantificarem os riscos associados à economicidade dos projetos. Neste sentido, a área de modelagem de reservatórios é de suma importância, sendo responsável por prever o desempenho futuro do reservatório sob diversas condições operacionais. Considerando que a solução dos sistemas de equações construídos a cada passo de tempo de uma simulação, durante o ciclo de linearização, é a parte que apresenta a maior demanda computacional, esta dissertação foca na análise de diferentes técnicas de solvers numéricos que podem ser aplicadas a simuladores, para mensurar seus desempenhos. Os solvers numéricos mais adequados para a solução de grandes sistemas de equações, tais como os encontrados em simulações de reservatórios, são os denominados solvers iterativos, que gradativamente aproximam a solução de um dado problema por meio da combinação de um método iterativo e um precondicionador. Os métodos iterativos avaliados nesta pesquisa foram o Gradiente Biconjugado Estabilizado (BiCGSTAB), Mínimos Resíduos Generalizado (GMRES) e Minimização Ortogonal (ORTHOMIN). Além disso, três técnicas de precondicionamento foram implementadas para auxiliar os métodos iterativos, sendo estas a Decomposição LU Incompleta (ILU), Fatoração Aninhada (NF) e Pressão Residual Restrita (CPR). A combinação destes diferentes métodos iterativos e precondicionadores permite a avaliação de diversas configurações distintas de solvers, em termos de seus desempenhos em um simulador. Os testes numéricos conduzidos neste trabalho utilizaram um novo simulador de reservatórios que está sendo desenvolvido pela Pontifícia Universidade Católica (PUC-Rio) em conjunto com a Petrobras. O objetivo dos testes foi analisar a robustez e eficiência de cada um dos solvers quanto à sua capacidade de resolver as equações de escoamento multifásico no meio poroso, visando assim auxiliar na seleção do solver mais adequado para o simulador. / [en] Petroleum companies investing in the development of hydrocarbon fields rely upon a variety of reservoir studies to perform production forecasts and quantify the risks associated with the economics of their projects. Integral to these studies is the discipline of reservoir modeling, responsible for predicting future reservoir performance under various operational conditions. Considering that the most time-demanding aspect of reservoir simulations is the solution of the systems of equations that arise within the linearization cycles at each time-step, this research focuses on analyzing different numerical solver techniques to be applied to a simulator, in order to assess their performance. The numerical solvers most suited for the solution of very large systems of equations, such as those encountered in reservoir simulations, are the so-called iterative solvers, which gradually approach the solution to a problem by combining an iterative strategy with a preconditioning method. The iterative methods examined in this research were the Stabilized Biconjugate Gradient (BiCGSTAB), the Generalized Minimum Residual (GMRES), and the Orthogonal Minimization (ORTHOMIN) methods. Furthermore, three preconditioning techniques were implemented to aid the iterative methods, namely the Incomplete LU Factorization (ILU), the Nested Factorization (NF), and the Constrained Pressure Residual (CPR) methods. The combination of these different iterative methods and preconditioners enables the appraisal of several distinct solver configurations, in terms of their performance in a simulator. The numerical tests conducted in this work made use of a new reservoir simulator currently under development at Pontifical Catholic University of Rio de Janeiro (PUC-Rio), as part of a joint project with Petrobras. The objective of these tests was to assess the robustness and efficiency of each solver in the solution of the multiphase flow equations in porous media, and support the selection of the solver most suited for the simulator.