Premium
Fast wavelet transforms and numerical algorithms I
Author(s) -
Beylkin G.,
Coifman R.,
Rokhlin V.
Publication year - 1991
Publication title -
communications on pure and applied mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.12
H-Index - 115
eISSN - 1097-0312
pISSN - 0010-3640
DOI - 10.1002/cpa.3160440202
Subject(s) - mathematics , algorithm , wavelet , operator (biology) , class (philosophy) , matrix (chemical analysis) , numerical analysis , differential operator , pure mathematics , computer science , mathematical analysis , artificial intelligence , biochemistry , chemistry , materials science , repressor , transcription factor , composite material , gene
A class of algorithms is introduced for the rapid numerical application of a class of linear operators to arbitrary vectors. Previously published schemes of this type utilize detailed analytical information about the operators being applied and are specific to extremely narrow classes of matrices. In contrast, the methods presented here are based on the recently developed theory of wavelets and are applicable to all Calderon‐Zygmund and pseudo‐differential operators. The algorithms of this paper require order O ( N ) or O ( N log N ) operations to apply an N × N matrix to a vector (depending on the particular operator and the version of the algorithm being used), and our numerical experiments indicate that many previously intractable problems become manageable with the techniques presented here.