Research ArticleOpen AccessGoogle Scholar indexed
An Improved Wavelet Based Preconditioner for Sparse Linear Problems
- 1
- 2
Applied Mathematics·Volume 01 (2010)·Pages 370–376·Published 30 November 2010·DOI10.4236/am.2010.15049
Copy link · social · email
Abstract
In this paper, we present the construction of purely algebraic Daubechies wavelet based preconditioners for Krylov subspace iterative methods to solve linear sparse system of equations. Effective preconditioners are designed with DWTPerMod algorithm by knowing size of the matrix and the order of Daubechies wavelet. A notable feature of this algorithm is that it enables wavelet level to be chosen automatically making it more robust than other wavelet based preconditioners and avoids user choosing a level of transform. We demonstrate the efficiency of these preconditioners by applying them to several matrices from Tim Davis collection of sparse matrices for restarted GMRES.
KeywordsDiscrete Wavelet TransformPreconditionersSparse MatricesKrylov Subspace Iterative Methods
- T. A. Davis, “University of Florida Sparse Matrix Collection,” NA Digest, Vol. 97, No. 23, 1997, p. 7. http://www. cise.ufl.edu/research/sparse/matrices/
- J. M. Ford, “A Black Box at the End of the Rainbow: Searching for the Perfect Preconditioner,” Philosophical Transactions of Royal Society London A, Vol. 361, No. 1813, 2003, pp. 2665-2680.
- Y. Saad, “Iterative Methods for Sparse Linear Systems,” SIAM, Philadelphia, 2003.
- M. Benzi, “Preconditioning Techniques for Large Linear Systems: A Survey,” Journal of Computational Physics, Vol. 182, No. 2, 1 November 2002, pp. 418-477.
- K. Chen, “Matrix Preconditioning Techniques and Applications,” Cambridge University Press, Cambridge, 2005.
- K. Chen, “Discrete Wavelet Transforms Accelerated Sparse Preconditioners for Dense Boundary Element Systems,” Electronic Transactions on Numerical Analysis, Vol. 8, 1999, pp. 138-153. http://etna.mcs.kent.edu/ vol.8.1999/pp138-153.dir/pp138-153.pdf
- J. M. Ford, “An Improved Discrete Wavelet Transform Preconditioner for Dense Matrix Problems,” SIAM Journal on Matrix Analysis and Applications, Vol. 25, No. 3, 2003, pp. 642-661.
- B. V. R. Kumar and M. Mehra, “Wavelet-Based Preconditioners for Sparse Linear Systems,” Applied Mathematics and Computation, Vol. 171, No. 1, 1 December 2005, pp. 203-224.
- D. F. Walnut, “An Introduction to Wavelet Analysis,” Birkhauser, Boston–Basel–Berlin, 2002.
- S. Mallat, “A Wavelet Tour of Signal Processing,” Academic Press, Elsevier, California, 1999.
- G. Strang and T. Nguyen, “Wavelets and Filter Banks,” Wellesley-Cambridge Press, Wellesley, 1997.
- I. Daubechies, “Ten Lectures on Wavelets,” SIAM, Philadelphia, 1992.
- G. Uytterhoeven, “Wavelets: Software and Applications,” Ph.D. Dissertation, Katholieke Universiteit Leuven, Belgium, 1999.
- G. H. Goulab and C. F. van Loan, “Matrix Computations,” Hindustan Book Agency, Hindustan, 2007.
- Z. Zlatev, “Computational Methods for General Sparse Matrices,” Kluwer, Dordrecht, the Netherlands, 1991.
- A. Cohen, I. Daubechies and J. C. Feauveau, “Biorthogonal Bases of Compactly Supported Wavelets,” Communications on Pure and Applied Mathematics, Vol. 45, No. 5, June 1992, pp. 485-560.