Variable Block Multilevel Iterative Solution of General Sparse Linear Systems
We present numerical results with a variable block multilevel incomplete LU factorization preconditioners for solving sparse linear systems arising, e.g., from the discretization of 2D and 3D partial differential equations on unstructured meshes. The prop
- PDF / 196,371 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 29 Downloads / 184 Views
Institute of Mathematics and Computing Science, University of Groningen, 9747 AG Groningen, The Netherlands {b.carpentieri,j.liao}@rug.nl 2 Department of Modeling, Simulation and Visualization Engineering, Old Dominion University, Norfolk, VA 23529, USA [email protected]
Abstract. We present numerical results with a variable block multilevel incomplete LU factorization preconditioners for solving sparse linear systems arising, e.g., from the discretization of 2D and 3D partial differential equations on unstructured meshes. The proposed method automatically detects and exploits any available block structure in the matrix to maximize computational efficiency. Both sequential and parallel experiments are shown on selected matrix problems in different application areas, also against other standard preconditioners. Keywords: Linear systems · Sparse matrices · Krylov methods Algebraic preconditioners · Multilevel incomplete LU factorization Graph compression
1
· ·
Introduction
We consider iterative solutions of sparse linear systems of the form Ax = b
(1)
typically arising from the finite element, finite difference or finite volume discretization of partial differential equations (PDEs) on unstructured meshes. Here we denote by A = [aij ] ∈ Rn×n a large and sparse matrix, b ∈ Rn is a given right-hand side vector and x ∈ Rn is the unknown solution vector. We are particularly interested to design multilevel incomplete LU factorization methods for this problem class that can exploit any existing block structure in the matrix, and maximize computational efficiency. It is known that many sparse matrices arising from the solution of systems of partial differential equations exhibit a natural block structure inherited from the underlying physical problem, e.g., when several physical quantities are associated with the same mesh node. If the, say , distinct variables associated with the same node are numbered consecutively, the permuted matrix has a sparse R. Wyrzykowski et al. (Eds.): PPAM 2013, Part II, LNCS 8385, pp. 520–530, 2014. c Springer-Verlag Berlin Heidelberg 2014 DOI: 10.1007/978-3-642-55195-6 49,
Variable Block Multilevel Iterative Solution
521
block structure with nonzero blocks of size × . The blocks are usually fully dense, as variables at the same node are mutually coupled. We call this form of blocking a perfect block ordering. In multiphysics solution of coupled systems of PDEs, the blocks may correspond to sets of unknowns associated to different mathematical models, and thus may have variable size. Even in the case of general unstructured matrices, it is sometimes possible to compute imperfect block orderings by grouping together sets of columns and rows with a similar sparsity pattern, and treating some zero entries of the reordered matrix as nonzeros, and the nonzero blocks as dense, with a little sacrifice of memory [6]. In all these situations it is natural to consider block forms of multilevel factorization methods that exploit any available block structure (either perfect or imperfect) in the linear s
Data Loading...
