AbstractsBusiness Management & Administration

A study of advanced computational methods: high performance generic sparse approximate inverse preconditioning and multilevel techniques

by Christos Papadopoulos - Filelis

Institution: Democritus University of Thrace (DUTH); Δημοκρίτειο Πανεπιστήμιο Θράκης (ΔΠΘ)
Year: 2014
Keywords: Επίλυση μεγάλων αραιών συστημάτων; Γενικοί προσεγγιστικοί αραιοί αντίστροφοι; ΠΟΛΥΠΛΕΓΜΑΤΙΚΕΣ ΜΕΘΟΔΟΙ; Πολυεπίπεδες μέθοδοι; Προσυντονισμένες επαναληπτικές μέθοδοι; Παράλληλα συστήματα μεριζόμενης μνήμης και παράλληλα συστήματα κατανεμημένης μνήμης; Προσυντονισμένες επαναληπτικές μέθοδοι; Μελέτη σύγκλισης; Εφαρμογές; Μη γραμμικά προβλήματα; Προβλήματα συνοριακών και αρχικών τιμών; Solution of large sparse linear systems; Generic approximate sparse inverses; Multigrid methods; Multilievel methods; Preconditioned iterative methods; Shared memory parallel and distributed memory parallel systems; General purpose graphics processing units; Convergence analysis; Applications; Non-linear problems; Boundary and initial value problems
Record ID: 1153077
Full text PDF: http://hdl.handle.net/10442/hedi/35177


In this thesis we introduce new generic sparse approximate inverse matrix techniques as well as multilevel techniques for solving general sparse linear systems. Such linear systems are derived mainly from the Finite Difference method, the Finite Element method, multigrid or multilevel methods. Moreover, the relationship of these algorithmic procedures is provided. Furthermore, the convergence analysis of the proposed schemes is studied.In Chapter 1, basic mathematical concepts for the numerical solution of Partial Differential Equations (PDEs) are introduced. Moreover, various preconditioned iterative methods for solving linear systems are introduced including the Multigrid method. Furthermore, an introduction to software environments for modern parallel computer systems is provided.In Chapter 2, the approximate inverse sparsity patterns algorithm and discussions on generic schemes are given. The Generic Approximate Sparse Inverse (GenAspI) matrix and the Generic Factored Approximate Sparse Inverse (GenFAspI) matrix are proposed along with implementation issues. Moreover, modified versions of such schemes, namely Modified GenApsI (MGenAspI) and Modified GenFAspI (MGenFAspI), that enhance performance, are also presented. Furthermore, an approximate inverse matrix refinement scheme that retains the number of nonzero elements is given.In Chapter 3, explicit preconditioned iterative methods are presented. The Explicit Preconditioned Bi-Conjugate Gradient STABilized (EPBiCGSTAB), the Explicit Preconditioned Generalized Minimum RESidual restarted (EPGMRES(m)) and the Explicit Preconditioned Induced Dimension Reduction (EPIDR(s)) are introduced. Moreover, multigrid methods based on approximate inverse matrices, various cycle schemes and the Dynamic Over/Under Relaxation (DOUR) scheme are also presented. Furthermore, multigrid preconditioning based on approximate inverse matrices and Krylov subspace iterative methods is presented. Discussions and implementation details are also provided.In Chapter 4, a novel multilevel scheme based on the Modified Generic Factored Approximate Sparse Inverse (MGenFAspI) matrix and a Block Breadth First Search reordering scheme is given. The Multilevel Algebraic Recursive Generic Approximate Inverse Solver (MARGAIS) exploits the idea of block independent set reordering along with a block inversion scheme. To compute the hierarchy of the multilevel scheme a partial Incomplete LU factorization is used. Moreover, the algorithm can be implemented using a recursive scheme, simplifying the data organization. Discussions concerning techniques to reduce memory requirements along with implementation details are also provided.In Chapter 5, the sensitivity of the Optimized Banded Generalized Approximate Inverse Matrix (OBGAIM) is studied and theoretical estimates are presented. Moreover, theoretical estimates on the convergence rate and computational complexity of the Explicit Preconditioned Conjugate Gradient method based on the Generic Approximate Sparse Inverse matrix are given. Furthermore,…