×

A fast wavelet block Jacobi method. (English) Zbl 1232.42030

Summary: We develop a fast block Jacobi method for linear systems based on discrete wavelet transform (DWT). Traditional wavelet-based methods for linear systems do not fully utilize the sparsity and the multi-level block structure of the transformed matrix after DWT. For the sake of numerical efficiency, we truncate the transformed matrix to be a sparse matrix by letting the small values be zero. To combine the advantages of the direct method and the iterative method, we solve the sub-systems appropriately based on the multi-level block structure of the transformed matrix after DWT. Numerical examples show that the proposed method is very numerically effective.

MSC:

42C40 Nontrigonometric harmonic analysis involving wavelets and other special systems
65T60 Numerical methods for wavelets
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Atkinson, K., The Numercial Solution of Integral Equation of the Second Kind (1997), Cambridge University Press
[2] Bai, Z.; Parlett, N.; Wang, Z., On generalized successive overrelaxation methods for augmented linear systems, Numer. Math., 102, 1-38 (2005) · Zbl 1083.65034
[3] Barrett, R.; Berry, M.; Chan, T. F.; Demmel, J.; Donato, J.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, C.; der Vorst, H. V., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (1994), SIAM: SIAM Philadelphia, PA
[4] Bertero, M.; Boccacci, P., Introduction to Inverse Problems in Imaging (1998), Institute of Physics Publ.: Institute of Physics Publ. Bristol · Zbl 0914.65060
[5] Beylkin, G.; Coifman, R.; Rokhlin, V., Fast wavelet transforms and numerical algorithms I, Comm. Pure Appl. Math., 44, 141-183 (1991) · Zbl 0722.65022
[6] Bujurke, N.; Salimath, C.; Kudenatti, R.; Shiralashetti, S., A fast wavelet-based multigrid method to solve elliptic partial differential equations, Appl. Math. Comput., 185, 667-680 (2007) · Zbl 1107.65347
[7] Chen, W. S.; Zou, J., Compatible wavelet—Galerkin method to solve Stokes interior problem with circular boundary, Appl. Anal., 87, 7, 755-772 (2008) · Zbl 1148.76343
[8] Chen, W. S.; You, X. G.; Fang, B.; Tang, Y. Y.; Huang, J., Wavelet natural boundary element method for the Neumann exterior problem of Stokes equations, Int. J. Wavelets Multiresolut., 4, 1, 23-40 (2006)
[9] Daubechies, I., Ten Lectures on Wavelets, CBMS Conf. Ser. in Appl. Math., vol. 61 (1992), SIAM: SIAM Philadelphia · Zbl 0776.42018
[10] Leon, D., A new wavelet multigrid method, J. Comput. Appl. Math., 220, 674-685 (2008) · Zbl 1146.65074
[11] Glines, D.; Beylkin, G.; Dunn, J., LU factorization of non-standard forms and direct multiresolution solvers, Appl. Comput. Harmon. Anal., 5, 156-201 (1998) · Zbl 0914.65017
[12] Golub, G.; Van Loan, C., Matrix Computations (1989), Johns Hopkins · Zbl 0733.65016
[13] Garcia, V.; Acevedo, L.; Vidal, A., Variants of algebraic wavelet-based multigrid method: Application to shifted linear systems, Appl. Math. Comput., 202, 287-299 (2008) · Zbl 1147.65027
[14] Lu, Y.; Shen, L.; Xu, Y., Shadow block iteration for solving linear systems obtained from wavelet transforms, Appl. Comput. Harmon. Anal., 19, 359-385 (2005) · Zbl 1086.65029
[15] Mallat, S., A theory for multiresolution signal decomposition: the wavelet representation, IEEE Trans. Pattern Anal. Mach. Intell., 11, 674-693 (1989) · Zbl 0709.94650
[16] Mallat, S., A Wavelet Tour of Signal Processing (1999), Academic Press · Zbl 0998.94510
[17] Mitchell, T., Machine Learning (1997), McGraw-Hill: McGraw-Hill New York · Zbl 0913.68167
[18] Pereira, F.; Verardi, S.; Nabeta, S., A wavelet-based algebraic multigrid preconditioner for sparse linear systems, Appl. Math. Comput., 182, 1098-1107 (2006) · Zbl 1107.65040
[19] Saad, Y., Iterative Methods for Sparse Linear Systems (1996), PWS · Zbl 1002.65042
[20] Wang, G.; Dutton, R.; Hou, J., A fast wavelet multigrid algorithm for solution of electromagnetic integral equations, Microw. Opt. Technol. Lett., 24, 86-91 (2000)
[21] Wilkinson, J., The Algebraic Eigenvalue Problem (1965), Oxford University Press · Zbl 0258.65037
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.