An inverse LU preconditioner based on the Sherman–Morrison formula

Bru, R.; Cerdán, J.; Marín, J.; Mas, J.

doi:10.2478/auom-2024-0006

Abstract

An approximate inverse LU preconditioner is constructed based on the Sherman–Morrison formula. Applying recursively that inversion formula a multiplicative decomposition of the inverse of a matrix is obtained. This recursion in compact form is the base to build the proposed preconditioner that we call V–AISM. For nonsingular M-matrices and H-matrices of the invertible class the stability of the preconditioner is proved. Numerical results show that V–AISM is robust and competitive compared with other preconditioners.

References

M. Benzi and M. Tuma. A sparse approximate inverse preconditioner for nonsymmetric linear systems. SIAM Journal on Scientific Computing, 19, 968–994, 1998.
Search in Google Scholar Back to article
M. Benzi and M. Tuma. A comparative study of sparse approximate inverse preconditioners. Appl. Numer. Math. 30, 305–340, 1999.
Search in Google Scholar Back to article
A. Berman and R. J. Plemmons. Nonnegative Matrices in the Mathematical Sciences. SIAM, Philadelphia, PA, USA, 1979.
Search in Google Scholar Back to article
M. Bollhöfer and Y. Saad. On the relations between ILUs and factored approximate inverses. SIAM J. Matrix Anal. Appl., 24(1), 219–237, 2002.
Search in Google Scholar Back to article
R. Bru, C. Corral, M. I. Gimenez and J. Mas. Classes of general H–matrices. Linear Algebra and its Applications. 429(10), 2358–2366, 2008.
Search in Google Scholar Back to article
R. Bru, J. Cerdán, J. Marín and J. Mas. Preconditioning sparse nonsymmetric linear systems with the Sherman–Morrison formula. SIAM Journal on Scientific Computing, 25, 701–715, 2003.
Search in Google Scholar Back to article
R. Bru, J. Marín, J. Mas and M. Tůma. Balanced incomplete factorization. SIAM J. Sci. Comput., 30, 2302–2318, 2008.
Search in Google Scholar Back to article
R. Bru, J. Marín, J. Mas and M. Tůma. Improved balanced incomplete factorization. SIAM J. Matrix Anal. Appl., 31, 2431–2452, 2010.
Search in Google Scholar Back to article
R. Byrd, J. Nocedal and R. Schnabel. Representations of Quasi-Newton matrices and their use in limited memory methods. Mathematical Programming, 63(13), 129–156, 1994.
Search in Google Scholar Back to article
J. Cerdán, T. Faraj, N. Malla, J. Marín and J. Mas. Block approximate inverse preconditioners for sparse nonsymmetric linear systems. Electron. Trans. Numer. Anal., 37, 23–40, 2010.
Search in Google Scholar Back to article
T. A. Davis and Y. Hu. The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software 38, 1, Article 1 (December 2011), 25 pages.
Search in Google Scholar Back to article
I. S. Du, R.G. Grimes and J. G. Lewis. Users’ Guide for the Harwell-Boeing Sparse Matrix Collection. Tech. Report RAL 92–886, Rutherford Appleton Laboratory, Chilton, England, 1992.
Search in Google Scholar Back to article
I. Du, M. Heroux, R. Pozo. An Overview of the Sparse Basic Linear Algebra Subprograms: The New Standard from the BLAS Technical Forum. ACM Trans. Math. Softw. 28, 2, 239–267, 2002.
Search in Google Scholar Back to article
W. W. Hager. Updating the inverse of matrix. SIAM Rev., 31(2), 221–239, 1989.
Search in Google Scholar Back to article
A. Rafiei, M. Bollhöfer and F. Benkhaldoun. A block version of left-looking AINV preconditioner with one by one or two by two block pivots. Applied Mathematics and Computation, 350, 36–385, 2019.
Search in Google Scholar Back to article
J. Sherman and W. J. Morrison. Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. Ann. Math. Statist., 21, 124–127, 1950.
Search in Google Scholar Back to article
C. N. van Duin. Scalable parallel preconditioning with the sparse approximate inverse of triangular matrices. SIAM J. Matrix Anal. Appl. 20(4), 987–1006, 1999. MR1699790.
Search in Google Scholar Back to article

An inverse LU preconditioner based on the Sherman–Morrison formula

Abstract

Paradigm

My account