Development of scalable linear solvers for engineering applications

The numerical simulation of modern engineering problems can easily incorporate millions or even billions of unknowns. In several applications, particularly those with diffusive character, sparse linear systems with symmetric positive definite (SPD) matrices need to be solved, and multilevel methods represent common choices for the role of iterative solvers or preconditioners. The weak scalability showed by those techniques is one of the main reasons for their popularity, since it allows the solution of linear systems with growing size without requiring a substantial increase in the computational time and number of iterations. On the other hand, single-level preconditioners such as the adaptive Factorized Sparse Approximate Inverse (aFSAI) might be attractive for reaching strong scalability due to their simpler setup. In this thesis, we propose four multilevel preconditioners based on aFSAI targeting the efficient solution of ill-conditioned SPD systems through parallel computing. The first two novel methods, namely Block Tridiagonal FSAI (BTFSAI) and Domain Decomposition FSAI (DDFSAI), rely on graph reordering techniques and approximate block factorizations carried out by aFSAI. Then, we introduce an extension of the previous techniques called the Multilevel Factorization with Low-Rank corrections (MFLR) that ensures positive definiteness of the Schur complements as well as improves their approximation with the aid of tall-and-skinny correction matrices. Lastly, we present the adaptive Smoothing and Prolongation Algebraic MultiGrid (aSPAMG) preconditioner belonging to the adaptive AMG family that introduces the use of aFSAI as a flexible smoother; three strategies for uncovering the near-null space of the system matrix and two new approaches to dynamically compute the prolongation operator. We assess the performance of the proposed preconditioners through the solution of a set of model problems along with real-world engineering test cases. Moreover, we perform comparisons to other approaches such as aFSAI, ILU (ILUPACK), and BoomerAMG (HYPRE), showing that our new methods prove comparable, if not superior, in many test cases.

Nell'ingegneria d'oggigiorno, le simulazioni numeriche possono facilmente arrivare alle dimensioni di milioni, se non miliardi, di incognite. Diverse applicazioni, specificatamente quelle a carattere diffusivo, richiedono la soluzione di sistemi lineari sparsi con matrici simmetriche definite positive (SPD). In questo contesto, i metodi multilivello rappresentano una scelta corrent, sia da usarsi per come solutori iterativi che come precondizionatori. La weak scalability mostrata da queste tecniche è una delle ragioni principali alla base della loro popolarità, dal momento che consente la soluzione di sistemi lineari di dimensioni crescenti senza un sostanziale aumento del tempo di calcolo e del numero di iterazioni. D'altro canto, i precondizionatori singolo livello, come l'adaptive Factorized Sparse Approximate Inverse (aFSAI), possono avere il vantaggio della strong scalability, principalmente grazie alla fase di setup più semplice. In questo lavoro di tesi, si propongono quattro precondizionatori multilivello, basati sulla tecnica aFSAI. L'obiettivo è la soluzione efficiente di problemi SPD mal condizionati, attraverso l'utilizzo di algoritmi adatti al calcolo parallelo. I primi due metodi, ovvero Block Tridiagonal FSAI (BTFSAI) e Domain Decomposition FSAI (DDFSAI), si basano su tecniche di riordinamento della matrice e su fattorizzazioni approssimate a blocchi, ottenute grazie alla aFSAI. In seguito, si presenta un'estensione delle tecniche precedenti, denominata Multilevel Factorization with Low-Rank corrections (MFLR), in grado di assicurare la definitezza (positiva) dei complementi di Schur e di migliorarne l'approssimazione grazie a delle matrici di correzione a rango basso. Infine, si introduce l'adaptive Smoothing and Prolongation Algebraic MultiGrid (aSPAMG), un precondizionatore appartenente alla famiglia dei metodi multigrid adattivi, che si distingue per alcune caratteristiche, quali l'uso della aFSAI come smoother flessibile, tre strategie per approssimare il near-null space della matrice e due nuovi approcci per calcolare dinamicamente l'operatore d'interpolazione. Nel presente lavoro, si analizzano le caratteristiche dei precondizionatori proposti attraverso la soluzione sia di problemi artificiali che di matrici reali, ricavate da applicazioni ingegneristiche. Infine, si realizzano confronti con altri approcci molto noti, quali aFSAI, ILU (ILUPACK) e BoomerAMG (HYPRE), dimostrando che i metodi proposti hanno delle prestazioni comparabili, se non superiori, in diversi problemi.