The Nested Recursive Two-Level Factorization Method for Nine-Point Difference Matrices
9-point stencil\(V\)-cycle\(W\)-cyclecomputational complexitycondition numberfinite differencefinite elementmassively parallel computer architecturesmultilevel incomplete factorization preconditionersoptimal preconditionersred/black structureSchur complementspectral equivalence
Iterative numerical methods for linear systems (65F10) Numerical computation of matrix norms, conditioning, scaling (65F35) Finite difference methods for boundary value problems involving PDEs (65N06) Numerical solution of discretized equations for boundary value problems involving PDEs (65N22) Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs (65N30) Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20)
The authors describe and analyze multilevel incomplete factorization preconditioners \(M^{(l)}\) to a 9-point stencil finite element or finite difference matrix \(S^{(l)}\). The preconditioner is based on the following ideas: {1. } Approximation of 9-point stencil by a spectrally equivalent 5/9-point stencil corresponding to red/black structure of the grid. {2. } Incomplete factorization of a 5/9-point stencil matrix \(A^{(l)}\) by approximating the Schur complement \(S^{(l-1)}\) to the red points part of the grid. {3. } Consideration of the black points part of the grid as a lower level grid. The Schur complement \(S^{(l-1)}\) then corresponds to a 9-point stencil matrix on this grid and can be again approximated by 5/9-point stencil matrix \(A^{(l-1)}\) and the same type of incomplete factorization \(M^{(l-1)}\) as above. {4. } Better approximation of the Schur complement \(S^{(l-1)}\) can be achieved by means of polynomials in \((M^{(l- 1)})^{-1}S^{(l-1)}\) or in \((M^{(l-1)})^{-1}A^{(l-1)}\). The use of first order polynomials correspond to \(V\)-cycle, the use of higher order polynomials can be considered as a generalized \(W\)-cycle approximation. {5. } The above ideas can be applied recursively since the lowest level \(l=0\) is reached. For the lowest level \(M^{(0)}=A^{(0)}\). The analysis concerns the spectral equivalence between 9-point and 5/9- point stencil matrices, the preconditioning effect of the multilevel preconditioner, i.e. the condition number \(\hbox{cond}(M^{(l)^{- 1}}S^{(l)})\), and the computational complexity. It is proved that certain combinations of \(V\)- and \(W\)-cycles will give optimal preconditioners which are spectrally equivalent to the original matrix and the computational cost of their exploiting is proportional to the number of unknowns. The preconditioners are suitable for massively parallel computer architectures because they involve only solution of systems of diagonal form and local communications.
- The method of diagonal compensation of reduced matrix entries and multilevel iteration
- Implementation strategies for block recursive factorizations
- How fast the Laplace equation was solved in 1995
- An algebraic multilevel iteration method for finite element matrices
- Numerical linear algebra algorithms and software
- Condition numbers of approximate Schur complements in two- and three-dimensional discretizations on hierarchically ordered grids
- Iterative solution methods
- A unified framework for the construction of various algebraic multilevel preconditioning methods
- Experience in implementing the algebraic multilevel iteration method on a SIMD-type computer
- Nested grids ILU-decomposition (NGILU)
- The stabilized \(V\)-cycle method
- Diagonal threshold techniques in robust multi-level ILU preconditioners for general sparse linear systems
- scientific article; zbMATH DE number 4178637 (Why is no real title available?)
- A robust algebraic multilevel preconditioner for non-symmetricM-matrices
- Finite-element based sparse approximate inverses for block-factorized preconditioners
- Constant wavefront iteration methods for nine- and 15-point difference matrices
- Asymptotic work estimates for AMLI methods
This page was built for publication: The Nested Recursive Two-Level Factorization Method for Nine-Point Difference Matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3982111)