# Approximate multiplication in adaptive wavelet methods

Open Mathematics (2013)

• Volume: 11, Issue: 5, page 972-983
• ISSN: 2391-5455

top

## Abstract

top
Cohen, Dahmen and DeVore designed in [Adaptive wavelet methods for elliptic operator equations: convergence rates, Math. Comp., 2001, 70(233), 27–75] and [Adaptive wavelet methods II¶beyond the elliptic case, Found. Comput. Math., 2002, 2(3), 203–245] a general concept for solving operator equations. Its essential steps are: transformation of the variational formulation into the well-conditioned infinite-dimensional l 2-problem, finding the convergent iteration process for the l 2-problem and finally using its finite dimensional approximation which works with an inexact right-hand side and approximate matrix-vector multiplication. In our contribution, we pay attention to approximate matrix-vector multiplication which is enabled by an off-diagonal decay of entries of the wavelet stiffness matrices. We propose a more efficient technique which better utilizes actual decay of matrix and vector entries and we also prove that this multiplication algorithm is asymptotically optimal in the sense that storage and number of floating point operations, needed to resolve the problem with desired accuracy, remain proportional to the problem size when the resolution of the discretization is refined.

## How to cite

top

Dana Černá, and Václav Finěk. "Approximate multiplication in adaptive wavelet methods." Open Mathematics 11.5 (2013): 972-983. <http://eudml.org/doc/269779>.

@article{DanaČerná2013,
abstract = {Cohen, Dahmen and DeVore designed in [Adaptive wavelet methods for elliptic operator equations: convergence rates, Math. Comp., 2001, 70(233), 27–75] and [Adaptive wavelet methods II¶beyond the elliptic case, Found. Comput. Math., 2002, 2(3), 203–245] a general concept for solving operator equations. Its essential steps are: transformation of the variational formulation into the well-conditioned infinite-dimensional l 2-problem, finding the convergent iteration process for the l 2-problem and finally using its finite dimensional approximation which works with an inexact right-hand side and approximate matrix-vector multiplication. In our contribution, we pay attention to approximate matrix-vector multiplication which is enabled by an off-diagonal decay of entries of the wavelet stiffness matrices. We propose a more efficient technique which better utilizes actual decay of matrix and vector entries and we also prove that this multiplication algorithm is asymptotically optimal in the sense that storage and number of floating point operations, needed to resolve the problem with desired accuracy, remain proportional to the problem size when the resolution of the discretization is refined.},
author = {Dana Černá, Václav Finěk},
journal = {Open Mathematics},
keywords = {Adaptive methods; Wavelets; Matrix-vector multiplication; adaptive wavelet method; Galerkin method; wavelet stiffness matrix; approximate matrix-vector multiplication; decay of matrix entries; quasi-sparse matrix; algorithm},
language = {eng},
number = {5},
pages = {972-983},
title = {Approximate multiplication in adaptive wavelet methods},
url = {http://eudml.org/doc/269779},
volume = {11},
year = {2013},
}

TY - JOUR
AU - Dana Černá
AU - Václav Finěk
TI - Approximate multiplication in adaptive wavelet methods
JO - Open Mathematics
PY - 2013
VL - 11
IS - 5
SP - 972
EP - 983
AB - Cohen, Dahmen and DeVore designed in [Adaptive wavelet methods for elliptic operator equations: convergence rates, Math. Comp., 2001, 70(233), 27–75] and [Adaptive wavelet methods II¶beyond the elliptic case, Found. Comput. Math., 2002, 2(3), 203–245] a general concept for solving operator equations. Its essential steps are: transformation of the variational formulation into the well-conditioned infinite-dimensional l 2-problem, finding the convergent iteration process for the l 2-problem and finally using its finite dimensional approximation which works with an inexact right-hand side and approximate matrix-vector multiplication. In our contribution, we pay attention to approximate matrix-vector multiplication which is enabled by an off-diagonal decay of entries of the wavelet stiffness matrices. We propose a more efficient technique which better utilizes actual decay of matrix and vector entries and we also prove that this multiplication algorithm is asymptotically optimal in the sense that storage and number of floating point operations, needed to resolve the problem with desired accuracy, remain proportional to the problem size when the resolution of the discretization is refined.
LA - eng
KW - Adaptive methods; Wavelets; Matrix-vector multiplication; adaptive wavelet method; Galerkin method; wavelet stiffness matrix; approximate matrix-vector multiplication; decay of matrix entries; quasi-sparse matrix; algorithm
UR - http://eudml.org/doc/269779
ER -

## References

top
1. [1] Černá D., Finěk V., Construction of optimally conditioned cubic spline wavelets on the interval, Adv. Comput. Math., 2011, 34(2), 219–25 http://dx.doi.org/10.1007/s10444-010-9152-5 Zbl1210.65209
2. [2] Cohen A., Dahmen W., DeVore R., Adaptive wavelet methods for elliptic operator equations: convergence rates, Math. Comp., 2001, 70(233), 27–75 http://dx.doi.org/10.1090/S0025-5718-00-01252-7 Zbl0980.65130
3. [3] Cohen A., Dahmen W., DeVore R., Adaptive wavelet methods II¶beyond the elliptic case, Found. Comput. Math., 2002, 2(3), 203–245 http://dx.doi.org/10.1007/s102080010027 Zbl1025.65056
4. [4] Dahmen W., Wavelet and multiscale methods for operator equations, In: Acta Numer., 6, Cambridge University Press, Cambridge, 1997, 55–228 Zbl0884.65106
5. [5] DeVore R.A., Nonlinear approximation, In: Acta Numer., 7, Cambridge University Press, Cambridge, 1998, 51–150 Zbl0931.65007
6. [6] Dijkema T.J., Schwab Ch., Stevenson R., An adaptive wavelet method for solving high-dimensional elliptic PDEs, Constr. Approx., 2009, 30(3), 423–455 http://dx.doi.org/10.1007/s00365-009-9064-0 Zbl1205.65313
7. [7] Stevenson R., Adaptive solution of operator equations using wavelet frames, SIAM J. Numer. Anal., 2003, 41(3), 1074–1100 http://dx.doi.org/10.1137/S0036142902407988 Zbl1057.41010
8. [8] Stevenson R., On the compressibility operators in wavelet coordinates, SIAM J. Math. Anal., 2004, 35(5), 1110–1132 http://dx.doi.org/10.1137/S0036141002411520 Zbl1087.47012

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.