×

Wavelet sparse approximate inverse preconditioners. (English) Zbl 0891.65048

The authors are interested in solving large sparse problems of the form \(Ax= b\) using sparse approximate inverse preconditioners. This amounts to first solving \(AMy= b\) and then computing \(x= My\). The aim is to choose \(M\) such that it has as much sparsity as possible while \(AM\) is still an approximation to the identity matrix. The main idea in the present paper is to represent \(A\) in a different basis in which \(A^{-1}\) has a sparse approximation. Specifically, if \(A^{-1}\) presents some piecewise smoothness then one uses a wavelet transformation to convert this smoothness into small wavelet coefficients.
The authors compare this idea to that of a hierarchical basis preconditioner (to which it is closely related) and present a large number of interesting numerical experiments. The weak points of the method are also fairly discussed with suggestions for future work.
Reviewer: W.Govaerts (Gent)

MSC:

65F35 Numerical computation of matrix norms, conditioning, scaling
65F50 Computational methods for sparse matrices
65T50 Numerical methods for discrete and fast Fourier transforms
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] O. Axelsson,Iterative Solution Methods, Cambridge University Press, Cambridge, 1994. · Zbl 0795.65014
[2] M. Benson,Iterative Solution of Large Scale Linear Systems, Master’s thesis, Lake-head Univeristy, Thunder Bay, Ontario, 1973.
[3] M. Benson and P. Frederickson,Iterative solution of large sparse linear systems arising in certain multidimensional approximation problems, Utilitas Math., 22 (1982), pp. 127–140. · Zbl 0502.65020
[4] M. Benzi, C. D. Meyer, and M. Tuma,A sparse approximate inverse preconditioner for the conjugate gradient method, SIAM J. Sci. Comput., 17 (1996), pp. 1135–1149. · Zbl 0856.65019
[5] M. Benzi and M. Tuma,A sparse approximate inverse preconditioner for nonsymmetric linear systems, Tech. Rep. TR-PA-96-15, CERFACS, 1996. To appear in SIAM J. Sci. Comput., 1997. · Zbl 0930.65027
[6] G. Beylkin, R. Coifman, and V. Rokhlin,Fast wavelet transforms and numerical algorithms I, Comm. Pure Appl. Math., 44 (1991), pp. 141–184. · Zbl 0722.65022
[7] C. D. Boor,Dichotomies for band matrices, SIAM J. Numer. Anal., 17 (1980), pp. 894–907. · Zbl 0453.15002
[8] F. Canning and J. Scholl,Diagonal preconditioners for the EFIE using a wavelet basis, IEEE Trans. Antennas and Propagation, 44 (1996), pp. 1239–1246. · Zbl 0947.78016
[9] E. Chow and Y. Saad,Approximate inverse techniques for block-partitioned matrices. 1995. To appear in SIAM J. Sci Comput. · Zbl 0888.65035
[10] E. Chow and Y. Saad,Approximate inverse preconditioners for general sparse matrices, Colorado Conference on Iterative Methods, April 5–9, (1994). To appear in SIAM J. Sci. Comput.
[11] J. Cosgrove, J. Diaz, and A. Griewank,Approximate inverse preconditionings for sparse linear systems, Internat. J. Comput. Math., 44 (1992), pp. 91–110. · Zbl 0762.65025
[12] I. Daubechies,Orthonormal bases of compactly supported wavelets, Comm. Pure Appl. Math., 41 (1988), pp. 909–996. · Zbl 0644.42026
[13] I. Daubechies,Ten Lectures on Wavelets, CBMS-NSF Series Appl. Math., SIAM, Philadelphia, 1991.
[14] S. Demko,Inverses of band matrices and local convergence of spline projections, SIAM J. Numer. Anal., 14 (1977), pp. 616–619. · Zbl 0367.65024
[15] S. Demko, W. Moss, and P. Smith,Decay rates for inverses of band matrices, Math. Comp., 43 (1984), pp. 491–499. · Zbl 0568.15003
[16] V. Eijkhout and B. Polman,Decay rates of inverses of banded m-matrices that are near to Toeplitz matrices, Linear Algebra Applic., 109 (1988), pp. 247–277. · Zbl 0654.15014
[17] B. Engquist, S. Osher, and S. Zhong,Fast wavelet based algorithms for linear evolution equations, SIAM J. Sci. Comput., 15 (1994), pp. 755–775. · Zbl 0851.65060
[18] R. Glowinski, A. Rieder, R. Wells, Jr., and X. Zhou,A wavelet multigrid preconditioner for dirichlet boundary-value problems in general domains, Tech. Rep. TR93-06, Rice Computational Mathematics Laboratory, 1993. · Zbl 0860.65121
[19] N. I. M. Gould and J. A. Scott,On approximate-inverse preconditioners, Tech. Rep. RAL-TR-95-026, The Central Laboratory of the Research Councils, 1995.
[20] M. Grote and T. Huckle,Parallel preconditioning with sparse approximate inverses. 1995. To appear in SIAM J. Sci. Comput. · Zbl 0836.65066
[21] M. Grote and H. Simon,Parallel preconditioning and approximate inverses on the connection machine, in Scalable High Performance Computing Conference (SH-PCC), 1992 Williamsburg, VA, IEEE Computer Science Press, 1992, pp. 76–83.
[22] M. Grote and H. Simon,Parallel preconditioning and approximate inverses on the connection machine, in Sixth SIAM Conference on Parallel Processing for Scientific Computing II, R. S???? et al, eds., SIAM, 1993, pp. 519–523.
[23] L. Kolotilina, A. Nikishin, and A. yeremin,Factorized sparse approximate inverse (FSAI) preconditionings for solving 3D FE systems on massively parallel computers II, in Iterative Methods in Linear Algebra, Proceedings of the IMACS International Symposium, Brussels, April 2–4, 1991, R. Beauwens and P. Groen, eds., 1992, pp. 311–312.
[24] L. Kolotilina and A. Yeremin,Factorized sparse approximate inverse preconditionings I. theory, SIAM J. Matrix Anal. Appl., 14 (1993), pp. 45–58. · Zbl 0767.65037
[25] J. Lifshitz, A. Nikishin, and A. Yeremin,Sparse approximate inverse (FSAI) preconditionings for solving 3D CFD problems on massively parallel computers, in Iterative Methods in Linear Algebra, Proceedings of the IMACS International Symposium, Brussels, April 2–4, 1991, R. Beauwens and P. Groen, eds., 1992, pp. 83–84.
[26] G. Meurant,A review on the inverse of symmetric tridiagonal and block tridiagonal matrices, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 707–728. · Zbl 0754.65029
[27] E. Ong,Hierarchical Basis Preconditioners for Second Order Elliptic Problems in Three Dimensions, Ph.D. thesis, University of Washington, Seattle, 1989.
[28] W. P. Tang,Effective sparse approximate inverse preconditioners. In preparation, 1995.
[29] P. Vassilevski and J. Wang,Stabilizing the hierarchical basis by approximate wavelets, I: Theory, Tech. Rep. 95-47, Dept. of Mathematics, UCLA, 1995.
[30] P. Vassilevski and J. Wang,Stabilizing the hierarchical basis by approximate wavelets, II: Implementation and numerical results, Tech. Rep. 95-48, Dept of Mathematics, UCLA, 1995. · Zbl 0924.65108
[31] H. Yserentant,On the multilevel splitting of finite element spaces, Numer. Math., 49 (1986), pp. 379–412. · Zbl 0608.65065
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.