A sparse approximate inverse preconditioner for nonsymmetric linear systems.

*(English)*Zbl 0930.65027The authors construct preconditioners for Krylov space iterative methods applied to the matrix equation \(Ax=b\) with sparse nonsymmetric matrix \(A\). These preconditioners are based on approximating \(A^{-1}\) directly with a product of sparse upper- and lower-triangular matrices rather than approximating \(A\) with triangular matrices that must be inverted during each iteration. Because the Krylov space iterations can be carried out without inverting matrices, parallel implementation is potentially more efficient than for preconditioners approximating \(A\).

This work extends earlier work of M. Benzi, C. D. Meyer and J. Tuma [SIAM J. Sci. Comput. 17, No. 5, 1135-1149 (1996; Zbl 0856.65019)]. Preconditioners based on approximating \(A^{-1}\) appear in the literature, but the most successful ones have been based on a minimization process. In contrast, the authors discuss a construction based on a conjugate Gram-Schmidt process that would result in a direct solution method were small terms not dropped during construction. The authors draw heavily on the technology of incomplete factorization in their presentation, and the effectiveness (in terms of numbers of iterations) of the preconditioners presented in the paper is similar to incomplete LU preconditioners; however, the authors present a simple \(3\times 3\) matrix example to show that the incomplete inverse factorization is not algebraically equivalent to incomplete LU factorization. The authors also present and prove a characterization of fill-in of the triangular factors.

Finally, the authors present an extensive study of the approximate inverse preconditioner applied to matrices selected from collections of challenging test matrices. Three representative iterative solution methods: Bi-CGSTAB, QMR, and GMRES were chosen and results using incomplete LU preconditioning were compared with results using approximate inverse preconditioning. The overall conclusion the authors present is that the approximate inverse preconditioner is of similar quality and effectiveness as the incomplete LU preconditioner, both in numbers of iterations and computation time (for scalar implementation), and requires only a modest increase in time for constructing the preconditioner. The approximate inverse preconditioner promises much more efficient implementation on parallel computers than the incomplete LU preconditioner.

This work extends earlier work of M. Benzi, C. D. Meyer and J. Tuma [SIAM J. Sci. Comput. 17, No. 5, 1135-1149 (1996; Zbl 0856.65019)]. Preconditioners based on approximating \(A^{-1}\) appear in the literature, but the most successful ones have been based on a minimization process. In contrast, the authors discuss a construction based on a conjugate Gram-Schmidt process that would result in a direct solution method were small terms not dropped during construction. The authors draw heavily on the technology of incomplete factorization in their presentation, and the effectiveness (in terms of numbers of iterations) of the preconditioners presented in the paper is similar to incomplete LU preconditioners; however, the authors present a simple \(3\times 3\) matrix example to show that the incomplete inverse factorization is not algebraically equivalent to incomplete LU factorization. The authors also present and prove a characterization of fill-in of the triangular factors.

Finally, the authors present an extensive study of the approximate inverse preconditioner applied to matrices selected from collections of challenging test matrices. Three representative iterative solution methods: Bi-CGSTAB, QMR, and GMRES were chosen and results using incomplete LU preconditioning were compared with results using approximate inverse preconditioning. The overall conclusion the authors present is that the approximate inverse preconditioner is of similar quality and effectiveness as the incomplete LU preconditioner, both in numbers of iterations and computation time (for scalar implementation), and requires only a modest increase in time for constructing the preconditioner. The approximate inverse preconditioner promises much more efficient implementation on parallel computers than the incomplete LU preconditioner.

Reviewer: Myron Sussman (Bethel Park)

##### MSC:

65F10 | Iterative numerical methods for linear systems |

65F50 | Computational methods for sparse matrices |

65Y05 | Parallel numerical computation |

65F35 | Numerical computation of matrix norms, conditioning, scaling |