A comparative study of sparse approximate inverse preconditioners. (English) Zbl 0949.65043

Numerical analysis practitioners are well aware of the increasing number of preconditioners available to solve the large linear systems that arise in many applications. They also encounter difficulties when it comes to decide which approach might prove more suitable for a specific problem in a given computational environment. After more than two decades since the pioneering paper by J. A. Meijerink and H. A. van der Vorst [Math. Comput. 31, 148-162 (1977; Zbl 0349.65020)], introducing the subject via the incomplete factorizations, here is a systematic attempt to organize those newcomers based on sparse approximate inverses, which also takes into account the differences that may arise between serial and parallel processing.
From the start the authors take the view that sparse approximate inverse methods will become an increasingly important tool for high-performance preconditioning of large linear systems. Accordingly, these methods are carefully classified into three main groups, which are generically described as methods based on Frobenius norm minimization, methods with factorized sparse approximate inverses, and those which consider incomplete factorizations followed by an approximate inversion of the incomplete factors.
A large number of numerical experiments have been carried out on both symmetric positive definite systems and nonsymmetric ones. The systems have been taken from well-known benchmarks and cover a wide spectrum of problems arising from applications such as structural analysis, oil reservoir simulation, circuit modelling and power system network. The approximate inverse methods are thoroughly compared with the classic preconditioning methods based on incomplete factorizations and also polynomial preconditioning based on truncated Neumann series is considered. As general heuristical conclusions it is stated that on circuit problems, approximate inverse techniques can be more effective than incomplete factorizations, while the reverse is more often true for all other problems.
The wealth of experiments performed on a Cray C98 whose conclusions are summarized in the paper could prove very useful for those practitioners mentioned above, by providing them with many practical guidelines. Some recent papers with similar objectives or that are a complement to those in this paper are mentioned in its extensive bibliography.


65F35 Numerical computation of matrix norms, conditioning, scaling
65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices


Zbl 0349.65020
Full Text: DOI