research-article

On Two Variants of an Algebraic Wavelet Preconditioner

Authors:

Ke ChenAuthors Info & Claims

SIAM Journal on Scientific Computing, Volume 24, Issue 1

Pages 260 - 283

https://doi.org/10.1137/S1064827501391436

Published: 01 January 2002 Publication History

Abstract

A recursive method of constructing preconditioning matrices for the nonsymmetric stiffness matrix in a wavelet basis is proposed for solving a class of integral and differential equations. It is based on a level-by-level application of the wavelet scales decoupling the different wavelet levels in a matrix form just as in the well-known nonstandard form. The result is a powerful iterative method with built-in preconditioning leading to two specific algebraic multilevel iteration algorithms: one with an exact Schur preconditioning and the other with an approximate Schur preconditioning. Numerical examples are presented to illustrate the efficiency of the new algorithms.

References

[1]

K. Amaratunga, A wavelet‐based approach for the compression of kernel data in large scale simulations of 3D integral problems, IEEE Comput. Sci. Engrg., 2 (2000), pp. 34–45.

Digital Library

[2]

O. Axelsson, P. Vassilevski, Algebraic multilevel preconditioning methods. I, Numer. Math., 56 (1989), 157–177

Digital Library

[3]

O. Axelsson, P. Vassilevski, Algebraic multilevel preconditioning methods. II, SIAM J. Numer. Anal., 27 (1990), 1569–1590

Digital Library

[4]

O. Axelsson, M. Neytcheva, Algebraic multilevel iteration method for Stieltjes matrices, Numer. Linear Algebra Appl., 1 (1994), 213–236

[5]

O. Axelsson and M. Neytcheva, The Algebraic Multilevel Iteration Methods—Theory and Applications, preprint, 1994.

[6]

Owe Axelsson, Alexander Padiy, On the additive version of the algebraic multilevel iteration method for anisotropic elliptic problems, SIAM J. Sci. Comput., 20 (1999), 1807–1830

Digital Library

[7]

Randolph Bank, Hierarchical bases and the finite element method, Acta Numer., Vol. 5, Cambridge Univ. Press, Cambridge, 1996, 1–43

[8]

Maurice Benson, Paul Frederickson, Iterative solution of large sparse linear systems arising in certain multidimensional approximation problems, Utilitas Math., 22 (1982), 127–140

[9]

Michele Benzi, John Haws, Miroslav Tůma, Preconditioning highly indefinite and nonsymmetric matrices, SIAM J. Sci. Comput., 22 (2000), 1333–1353

Digital Library

[10]

G. Beylkin, R. Coifman, V. Rokhlin, Fast wavelet transforms and numerical algorithms. I, Comm. Pure Appl. Math., 44 (1991), 141–183

[11]

D. Bond and S. Vavasis, Fast Wavelet Transforms for Matrices Arising from Boundary Element Methods, Computer Science Research Report TR‐174, Cornell University, Ithaca, NY, 1994.

[12]

E. Botta, F. Wubs, Matrix renumbering ILU: an effective algebraic multilevel ILU preconditioner for sparse matrices, SIAM J. Matrix Anal. Appl., 20 (1999), 1007–1026, Sparse and structured matrices and their applications (Coeur d’Alene, ID, 1996)

Digital Library

[13]

T. F. Chan and K. Chen, Two‐Stage Preconditioners Using Wavelet Band Splitting and Sparse Approximation, CAM Report 00‐26, Department of Mathematics, UCLA, 2000.

[14]

T. Chan, W. Tang, W. Wan, Wavelet sparse approximate inverse preconditioners, BIT, 37 (1997), 644–660, Direct methods, linear algebra in optimization, iterative methods (Toulouse, 1995/1996)

Digital Library

[15]

Ke Chen, Discrete wavelet transforms accelerated sparse preconditioners for dense boundary element systems, Electron. Trans. Numer. Anal., 8 (1999), 138–153

[16]

Ke Chen, An analysis of sparse approximate inverse preconditioners for boundary integral equations, SIAM J. Matrix Anal. Appl., 22 (2001), 1058–1078

Digital Library

[17]

Albert Cohen, Wolfgang Dahmen, Ronald DeVore, Adaptive wavelet methods for elliptic operator equations: convergence rates, Math. Comp., 70 (2001), 27–75

Digital Library

[18]

A. Cohen, R. Masson, Wavelet methods for second‐order elliptic problems, preconditioning, and adaptivity, SIAM J. Sci. Comput., 21 (1999), 1006–1026

Digital Library

[19]

A. Cohen, R. Masson, Wavelet adaptive method for second order elliptic problems: boundary conditions and domain decomposition, Numer. Math., 86 (2000), 193–238

[20]

Wolfgang Dahmen, Wavelet and multiscale methods for operator equations, Acta Numer., Vol. 6, Cambridge Univ. Press, Cambridge, 1997, 55–228

[21]

Iain Duff, Jacko Koster, The design and use of algorithms for permuting large entries to the diagonal of sparse matrices, SIAM J. Matrix Anal. Appl., 20 (1999), 889–901, Sparse and structured matrices and their applications (Coeur d’Alene, ID, 1996)

Digital Library

[22]

D. Gines, G. Beylkin, J. Dunn,

LU

factorization of non‐standard forms and direct multiresolution solvers, Appl. Comput. Harmon. Anal., 5 (1998), 156–201

[23]

A. Harten, Multiresolution Representation and Numerical Algorithms: A Brief Review, CAM Report 94‐12, Department of Mathematics, UCLA, 1994.

[24]

L. Kolotilina, A. Yeremin, On a family of two‐level preconditionings of the incomplete block factorization type, Soviet J. Numer. Anal. Math. Modelling, 1 (1986), 293–320

[25]

J. Kovačević and W. Sweldens, Wavelet families of increasing order in arbitrary dimensions, IEEE Trans. Image Process., 9 (2000), pp. 480–496.

Digital Library

[26]

M. Neytcheva, Algebraic Multilevel Iteration Preconditioning Technique—A Matlab Implementation, available online from http://www.netlib.org, 1998.

[27]

Maya Neytcheva, Panayot Vassilevski, Preconditioning of indefinite and almost singular finite element elliptic equations, SIAM J. Sci. Comput., 19 (1998), 1471–1485

Digital Library

[28]

Y. Saad, ILUM: a multi‐elimination ILU preconditioner for general sparse matrices, SIAM J. Sci. Comput., 17 (1996), 830–847

Digital Library

[29]

Y. Saad, Iterative Methods for Sparse Linear Systems, PWS Publishing, Boston, 1996.

[30]

Youcef Saad, Martin Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7 (1986), 856–869

[31]

Yousef Saad, Henk van der Vorst, Iterative solution of linear systems in the 20th century, J. Comput. Appl. Math., 123 (2000), 1–33, Numerical analysis 2000, Vol. III. Linear algebra

Digital Library

[32]

Yousef Saad, Jun Zhang, BILUM: block versions of multielimination and multilevel ILU preconditioner for general sparse linear systems, SIAM J. Sci. Comput., 20 (1999), 2103–2121

Digital Library

[33]

Yousef Saad, Jun Zhang, Enhanced multi‐level block ILU preconditioning strategies for general sparse linear systems, J. Comput. Appl. Math., 130 (2001), 99–118

Digital Library

[34]

Gilbert Strang, Truong Nguyen, Wavelets and filter banks, Wellesley‐Cambridge Press, 1996xxii+490

[35]

Wim Sweldens, The lifting scheme: a construction of second generation wavelets, SIAM J. Math. Anal., 29 (1998), 511–546

Digital Library

[36]

Panayot Vassilevski, On two ways of stabilizing the hierarchical basis multilevel methods, SIAM Rev., 39 (1997), 18–53

Digital Library

[37]

P. Vassilevski, Hybrid

V

‐cycle algebraic multilevel preconditioners, Math. Comp., 58 (1992), 489–512

[38]

P. S. Vassilevski, Nearly Optimal Iterative Methods for Solving Finite Element Elliptic Equations Based on the Multilevel Splitting of the Matrix, Report 1989‐09, ISC, University of Wyoming, Laramie, WY, 1989.

[39]

W. L. Wan, Scalable and Multilevel Iterative Methods, Ph.D. thesis, CAM Report 98‐29, Department of Mathematics, UCLA, 1998.

[40]

H. Yserentant, On the multi‐level splitting of finite element spaces, Numer. Math., 49 (1986), pp. 379–412.

Digital Library

[41]

H. M. Zhou, Wavelet Transforms and PDE Techniques in Image Compression, Ph.D. thesis, CAM Report 00‐21, Department of Mathematics, UCLA, 2000.

Cited By

Acevedo LGarcia VVidal AAlonso P(2009)Partial data replication as a strategy for parallel computing of the multilevel discrete wavelet transformProceedings of the 8th international conference on Parallel processing and applied mathematics: Part I10.5555/1882792.1882800(51-60)Online publication date: 13-Sep-2009
https://dl.acm.org/doi/10.5555/1882792.1882800
Wang YLee JZhang J(2007)A short survey on preconditioning techniques for large-scale dense complex linear systems in electromagneticsInternational Journal of Computer Mathematics10.1080/0020716070135593884:8(1211-1223)Online publication date: 1-Aug-2007
https://dl.acm.org/doi/10.1080/00207160701355938
Acevedo LGarcia VVidal A(2007)Compatibility of Scalapack with the Discrete Wavelet TransformProceedings of the 7th international conference on Computational Science, Part I: ICCS 200710.1007/978-3-540-72584-8_20(152-159)Online publication date: 27-May-2007
https://dl.acm.org/doi/10.1007/978-3-540-72584-8_20
Show More Cited By

Index Terms

On Two Variants of an Algebraic Wavelet Preconditioner
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Linear algebra algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Differential equations
      1. Partial differential equations
    2. Numerical analysis
      1. Computations on matrices

Index terms have been assigned to the content through auto-classification.

Recommendations

A Sparse Approximate Inverse Preconditioner for Nonsymmetric Linear Systems

This paper is concerned with a new approach to preconditioning for large, sparse linear systems. A procedure for computing an incomplete factorization of the inverse of a nonsymmetric matrix is developed, and the resulting factorized sparse approximate ...
An Algebraic Multilevel Preconditioner with Low-Rank Corrections for Sparse Symmetric Matrices

This paper describes a multilevel preconditioning technique for solving sparse symmetric linear systems of equations. This “Multilevel Schur Low-Rank” (MSLR) preconditioner first builds a tree structure $\mathcal{T}$ based on a hierarchical decomposition ...
A Sparse Approximate Inverse Preconditioner for the Conjugate Gradient Method

A method for computing a sparse incomplete factorization of the inverse of a symmetric positive definite matrix A is developed, and the resulting factorized sparse approximate inverse is used as an explicit preconditioner for conjugate gradient ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Scientific Computing

SIAM Journal on Scientific Computing Volume 24, Issue 1

2002

358 pages

ISSN:1064-8275

Issue’s Table of Contents

Copyright © 2002 Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2002

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Acevedo LGarcia VVidal AAlonso P(2009)Partial data replication as a strategy for parallel computing of the multilevel discrete wavelet transformProceedings of the 8th international conference on Parallel processing and applied mathematics: Part I10.5555/1882792.1882800(51-60)Online publication date: 13-Sep-2009
https://dl.acm.org/doi/10.5555/1882792.1882800
Wang YLee JZhang J(2007)A short survey on preconditioning techniques for large-scale dense complex linear systems in electromagneticsInternational Journal of Computer Mathematics10.1080/0020716070135593884:8(1211-1223)Online publication date: 1-Aug-2007
https://dl.acm.org/doi/10.1080/00207160701355938
Acevedo LGarcia VVidal A(2007)Compatibility of Scalapack with the Discrete Wavelet TransformProceedings of the 7th international conference on Computational Science, Part I: ICCS 200710.1007/978-3-540-72584-8_20(152-159)Online publication date: 27-May-2007
https://dl.acm.org/doi/10.1007/978-3-540-72584-8_20
Hawkins SChen K(2005)An Implicit Wavelet Sparse Approximate Inverse PreconditionerSIAM Journal on Scientific Computing10.1137/S106482750342350027:2(667-686)Online publication date: 1-Aug-2005
https://dl.acm.org/doi/10.1137/S1064827503423500
Ford JTyrtyshnikov E(2003)Combining Kronecker Product Approximation with Discrete Wavelet Transforms to Solve Dense, Function-Related Linear SystemsSIAM Journal on Scientific Computing10.1137/S106482750342168925:3(961-981)Online publication date: 1-Jan-2003
https://dl.acm.org/doi/10.1137/S1064827503421689

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents