An inverse LU preconditioner based on the Sherman–Morrison formula

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

doi:10.2478/auom-2024-0006

.blurhash-client-img { display: none !important; }

An inverse LU preconditioner based on the Sherman–Morrison formula

Analele ştiinţifice ale Universităţii "Ovidius" Constanţa. Seria Matematică

Volume 32 (2024): Issue 1 (April 2024)

By: R. Bru, J. Cerdán, J. Marín and J. Mas

Open Access

|May 2024

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

Articles in this issue

DOI: https://doi.org/10.2478/auom-2024-0006 | Journal eISSN: 1844-0835 | Journal ISSN: 1224-1784

Journal RSS Feed

Language: English

Page range: 105 - 126

Submitted on: Dec 1, 2022

Accepted on: Apr 20, 2023

Published on: May 27, 2024

Published by: Ovidius University of Constanta

In partnership with: Paradigm Publishing Services

Publication frequency: 3 issues per year

Keywords:

Nonsymmetric linear systems,

iterative methods,

aproximate inverse LU preconditioning,

Sherman-Morrison formula

Related subjects:

Mathematics,

General mathematics

© 2024 R. Bru, J. Cerdán, J. Marín, J. Mas, published by Ovidius University of Constanta
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Volume 32 (2024): Issue 1 (April 2024)