The Nested Recursive Two-Level Factorization Method for Nine-Point Difference Matrices

From MaRDI portal





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.











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)