In [1], the author introduced a wavelet multigrid method that used the wavelet transform to define the coarse grid, interpolation, and restriction operators for the multigrid method. In this paper, we modify the method by using symmetric biorthogonal wavelet transforms to define the requisite operators. Numerical examples are presented to demonstrate the effectiveness of the modified wavelet multigrid method for diffusion problems with highly oscillatory coefficients, as well as for advection-diffusion equations in which the advection is moderately dominant.
KeywordsMultigridWaveletsBiorthogonal Wavelets
D. De Leon, “A New Wavelet Multigrid Method,” Journal of Computational and Applied Mathematics, Vol. 220, No. 1-2, 2008, pp. 674-675. doi:10.1016/j.cam.2007.09.021
B. Engquist and E. Luo, “The Multigrid Method Based on a Wavelet Transformation and Schur Complement,” Unpublished.
D. De Leon, “Wavelet Operators Applied to Multigrid Methods,” Ph.D. Thesis, UCLA, Los Angeles, 2000.
W. L. Briggs and V. E. Henson, “Wavelets and Multigrid,” SIAM Journal on Scientific Computing, Vol. 14, No. 2, 1993, pp. 506-510. doi:10.1137/0914031
M. Dorobantu and B. Engquist, “Wavelet-Based Numerical Homogenization,” SIAM Journal on Numerical Analysis, Vol. 35, No. 2, 1998, pp. 540-559. doi:10.1137/S0036142996298880
B. Engquist and E. Luo, “New Coarse Grid Operators for Highly Oscillatory Coefficient Elliptic Problems,” Journal of Computational Physics, Vol. 129, No. 2, 1996, pp. 296-306. doi:10.1006/jcph.1996.0251
B. Engquist and E. Luo, “Convergence of a Multigrid Method for Elliptic Equations with Highly Oscillatory Coefficients,” SIAM Journal on Numerical Analysis, Vol. 34, No. 6, 1997, pp. 2254-2273. doi:10.1137/S0036142995289408
N. Neuss, W. Jager and G. Wittum, “Homogenization and Multigrid,” Computing, Vol. 66, No. 1, 2001, pp. 1-26. doi:10.1007/s006070170036
J. D. Moulton, J. E. Dendy, Jr. and J. M. Hyman, “The Black Box Multigrid Numerical Homogenization Algorithm,” Journal of Computational Physics, Vol. 142, No. 1, 1998, pp. 80-108. doi:10.1006/jcph.1998.5911
P. J. Van Fleet, “Discrete Wavelet Transformations: An Elementary Approach with Applications,” Wiley-Interscience, Hoboken, 2008. doi:10.1002/9781118032404
X. Yang, Y. Shi and B. Yang, “General Framework of the Construction of Biorthogonal Wavelets Based on Bernstein Bases: Theory Analysis and Application in Image Compression,” IET Computer Vision, Vol. 5, No. 1, 2011, pp. 50-67. doi:10.1049/iet-cvi.2009.0083
W. Sweldens, “The Lifting Scheme: A Construction of Second Generation Wavelets,” SIAM Journal on Mathematical Analysis, Vol. 29, No. 2, 1997, pp. 511-546. doi:10.1137/S0036141095289051
D. Taubman and M. Marcellin, “JPEG2000: Image Compression Fundamentals, Standards and Practice,” The International Series in Engineering and Computer Science, Kluwer Academic, Norwell, 2002.
S. Dahlke and A. Kunoth, “Biorthogonal Wavelets and Multigrid,” In Adaptive Methods: Algorithms, Theory and Applications, Proceedings of the 9th GAMM Seminar, Kiel, 1993, pp. 99-119.
L. Cheng, H. Wang and Z. Zhang, “The Solution of Ill-Conditioned Symmetric Toeplitz Systems via Two-Grid and Wavelet Methods,” Computers and Mathematics with Applications, Vol. 46, No. 5-6, 2003, pp. 793-804. doi:10.1016/S0898-1221(03)90142-8
A. P. Reddy and N. M. Bujurke, “Biorthogonal Wavelet Based Algebraic Multigrid Preconditioners for Large Sparse Linear Systems,” Applied Mathematics, Vol. 2, No. 11, 2011, pp. 1378-1381. doi:10.4236/am.2011.211194
W. L. Briggs, S. F. McCormick and V. E. Henson, “A Multigrid Tutorial,” 2nd Edition, SIAM, Philadelphia, 2000. doi:10.1137/1.9780898719505
S. McCormick, Ed., “Multigrid Methods,” Frontiers in Applied Mathematics, SIAM, Philadelphia, 1987.
U. Trottenberg, C. W. Oosterlee and A. Schüller, “Multigrid,” Academic Press, London, 2001.
J. W. Ruge and K. Stüben, “Algebraic Multigrid,” In: Multigrid Methods, Frontiers in Applied Mathematics, SIAM, Philadelphia, 1987, pp. 73-130. doi:10.1137/1.9781611971057.ch4
W. Dahmen and L. Elsner, “Algebraic Multigrid Methods and the Schur Complement,” In: Kiel, Ed., Robust Multi-Grid Methods, Notes on Numerical Fluid Mechanics, Vol. 23, Vieweg, Braunschweig, 1989, pp. 58-68.
K. Stüben, “Algebraic Multigrid (AMG): An Introduction with Applications,” Technical Report 70, GMD, 1999.
I. Daubechies, “Orthonormal Bases of Compactly Supported Wavelets,” Communications on Pure and Applied Mathematics, Vol. 41, No. 7, 1988, pp. 909-996. doi:10.1002/cpa.3160410705
I. Daubechies, “Ten Lectures on Wavelets,” CBMS-NSF Series in Applied Mathematics, Vol. 61, SIAM, Philadelphia, 1992.
A. Cohen, I. Daubechies and J.-C. Feauveau, “Biorthogonal Bases of Compactly Supported Wavelets,” Communications on Pure and Applied Mathematics, Vol. 45, No. 5, 1992, pp. 485-560. doi:10.1002/cpa.3160450502
D. K. Salkuyeh, “A New Approach to Compute Sparse Approximate Inverse Factors of a Matrix,” Applied Mathematics and Computation, Vol. 174, No. 2, 2006, pp. 1110-1121. doi:10.1016/j.amc.2005.06.011
L. Y. Kolotilina and A. Y. Yeremin, “Factorized Sparse Approximate Inverse Preconditioning I. Theory,” SIAM Journal on Matrix Analysis and Applications, Vol. 14, No. 1, 1993, pp. 45-58. doi:10.1137/0614004
L. Y. Kolotilina and A. Y. Yeremin, “Factorized Sparse Approximate Inverse Preconditioning II: Solution of 3D FE Systems on Massively Parallel Computers,” International Journal of High Speed Computing, Vol. 7, No. 2, 1995, pp. 191-215. doi:10.1142/S0129053395000117
E. Chow and Y. Saad, “Approximate Inverse Preconditioners via Sparse-Sparse Iterations,” SIAM Journal on Scientific Computing, Vol. 19, No. 3, 1998, pp. 995-1023. doi:10.1137/S1064827594270415
I. Yavneh, C. H. Venner and A. Brandt, “Fast Multigrid Solution of the Advection Problem with Closed Characteristics,” SIAM Journal on Scientific Computing, Vol. 19, No. 1, 1998, pp. 111-125. doi:10.1137/S1064827596302989
I. Yavneh, “Coarse-Grid Correction for Nonelliptic and Singular Perturbation Problems,” SIAM Journal on Scientific Computing, Vol. 19, No. 5, 1998, pp. 1682-1699. doi:10.1137/S1064827596310998