Democritus University of Thrace (DUTH)
A study of advanced computational methods: high performance generic sparse approximate inverse preconditioning and multilevel techniques
Abstract
dc:descriptionIn 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, theoretical estimates on the convergence rate of the multigrid method in conjunction with the Generic Approximate Sparse Inverse matrix are also studied. The modified Moore-Penrose conditions based on Explicit and Generic Approximate Inverse schemes are also given. Theoretical estimates on the quality of the Multilevel Algebraic Recursive Generic Approximate Inverse Solver (MARGAIS) are provided.In Chapter 6, a class of methods for solving nonlinear problems in conjunction with the mutligrid method based on the Generic Approximate Sparse Inverse matrix is presented. The Inexact Newton and Inexact Broyden method with Backtracking, the Inexact Jacobian-Free type methods with Backtracking as well as Full Approximation Scheme are given. The performance of these schemes is improved using a novel updating scheme based on “Good Broyden Update” formula. The modified “Good Broyden Update” formula is used to update the approximate inverse matrices in each step, instead of recomputing them, resulting in improved performance. The aforementioned nonlinear methods in conjunction with the Krylov accelerated multigrid method, the Generic Approximate Sparse Inverse matrix and the proposed update formula for solving ill-conditioned nonlinear problems are also presented.In Chapter 7, applications including hybrid implicit time explicit approximate inverse matrix schemes, based on the mutligrid method, are provided for solving Initial Value Problems (IVPs). Moreover, stable Finite Difference and Finite Element discretization schemes for convection diffusion type problems, based on upwind schemes and the Streamline Upwind Petrov-Galerkin method, respectively, are given. Furthermore, the effect of various reordering schemes, such as Reverse Cuthil-McKee (RCM), Approximate Minimum Degree (AMD) and Block Breadth First Search (BBFS), on the growth of nonzero elements of the Modified Generic Factored Approximate Sparse Inverse (MGenFAspI) matrix is studied. The impact on the performance of the computation of the proposed schemes is also discussed. The numerical solution of the Incompressible Navier-Stokes equation, for the two-dimensional lid driven cavity problem, in conjunction with the MGenFAspI, Approximate Minimum Degree (AMD) reordering scheme and the Explicit Preconditioned Bi-Conjugate Gradient STABilized (EPBiCGSTAB) is provided, following the Chorin’s projection method approach. Implementation details and discussions for these schemes are also given.In Chapter 8, the parallel design of the Generic Approximate Sparse Inverse matrix, namely PGenAspI, for Shared memory parallel systems is provided, utilizing the novel “strip” approach. Moreover, the functional level parallelized Explicit Preconditioned Bi-Conjugate Gradient STABilized method (PEPBiCGSTAB) is presented. The parallel modified truncated V-Cycle multigrid method is given, which utilizes a Parallel Explicit Preconditioned Bi-Conjugate Gradient STABilized (PEPBiCGSTAB), based on PGenAspI, replacing the levels of the multigrid method that do not possess enough parallelizable computational work. Replacing those levels with PEPBiCGSTAB retains the convergence behavior of the multigrid method, while improving parallel performance. Moreover, the Distributed Generic Approximate Sparse Inverse (DGenAspI) matrix is presented, based on a decoupled column-wise approach which does not require any intermediate communications enhancing parallel performance. Furthermore, a load balancing scheme is given for computing the DGenAspI matrix in case of a matrix with high standard deviation of nonzero elements per column. The hybrid parallelized Preconditioned Conjugate Gradient Chronopoulos-Gear variant method is also provided, for Distributed memory parallel systems with multicore nodes. Furthermore, the CUDA Parallel Fishbone Optimized Banded Generalized Approximate Inverse Finite Element Matrix, along with CUDA Explicit Preconditioned Bi-Conjugate Gradient STABilized method, for General Purpose Graphics Processing Units, is given. Discussions along with implementation details are also presented.Finally, in Chapter 9, numerical results for various model problems, in order to assess the performance, efficiency and convergence behavior of the proposed schemes, are provided. Moreover, comparative results with schemes presented by other researchers are provided. Furthermore, discussions on the numerical results are given.Finally, concluding remarks along with suggestions for future work are presented.
Degree
thesis:*- Grantor dc:publisher
- Democritus University of Thrace (DUTH)
- Year dc:date
- 2014
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Papadopoulos-Filelis, Christos
- Παπαδόπουλος-Φιλέλης, Χρήστος
Subjects
dc:subject × 29- Επίλυση μεγάλων αραιών συστημάτων
- Γενικοί προσεγγιστικοί αραιοί αντίστροφοι
- Πολυπλεγματικές μέθοδοι
- Πολυεπίπεδες μέθοδοι
- Προσυντονισμένες επαναληπτικές μέθοδοι
- Παράλληλα συστήματα μεριζόμενης μνήμης και παράλληλα συστήματα κατανεμημένης μνήμης
- Μελέτη σύγκλισης
- Εφαρμογές
- Μη γραμμικά προβλήματα
- Προβλήματα συνοριακών και αρχικών τιμών
- 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
- Φυσικές Επιστήμες
- Μαθηματικά
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Natural Sciences
- Mathematics
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/35177