An Improved Wavelet Based Preconditioner for Sparse Linear Problems

Arikera Padmanabha Reddy, Nagendrapp M. Bujurke

.

DOI: 10.4236/am.2010.15049                

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.

Keywords

Discrete Wavelet Transform, Preconditioners, Sparse Matrices, Krylov Subspace Iterative Methods

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	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/
[2]	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.
[3]	Y. Saad, “Iterative Methods for Sparse Linear Systems,” SIAM, Philadelphia, 2003.
[4]	M. Benzi, “Preconditioning Techniques for Large Linear Systems: A Survey,” Journal of Computational Physics, Vol. 182, No. 2, 1 November 2002, pp. 418-477.
[5]	K. Chen, “Matrix Preconditioning Techniques and Applications,” Cambridge University Press, Cambridge, 2005.
[6]	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
[7]	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.
[8]	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.
[9]	D. F. Walnut, “An Introduction to Wavelet Analysis,” Birkhauser, Boston–Basel–Berlin, 2002.
[10]	S. Mallat, “A Wavelet Tour of Signal Processing,” Academic Press, Elsevier, California, 1999.
[11]	G. Strang and T. Nguyen, “Wavelets and Filter Banks,” Wellesley-Cambridge Press, Wellesley, 1997.
[12]	I. Daubechies, “Ten Lectures on Wavelets,” SIAM, Philadelphia, 1992.
[13]	G. Uytterhoeven, “Wavelets: Software and Applications,” Ph.D. Dissertation, Katholieke Universiteit Leuven, Belgium, 1999.
[14]	G. H. Goulab and C. F. van Loan, “Matrix Computations,” Hindustan Book Agency, Hindustan, 2007.
[15]	Z. Zlatev, “Computational Methods for General Sparse Matrices,” Kluwer, Dordrecht, the Netherlands, 1991.
[16]	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.
[17]	W. Sweldens, “The Lifting Scheme: A Construction of Second Generation Wavelets,” SIAM Journal on Mathematical Analysis, Vol. 29, No. 2, March 1998, pp. 511- 546.