Fast wavelet transforms and numerical algorithms I

Communications on Pure and Applied Mathematics - Tập 44 Số 2 - Trang 141-183 - 1991
Gregory Beylkin1,2, Ronald R. Coifman2, Vladimir Rokhlin2
1Schlumberger-Doll Research, Ridgefield, CT 06897.
2Yale University

Tóm tắt

AbstractA 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.

Từ khóa


Tài liệu tham khảo

Alpert B. andRokhlin V. A Fast Algorithm for the Evaluation of Legendre Expansions Yale University Technical Report YALEU/DCS/RR‐671 1989.

10.1137/0909044

Coifman R. andMeyer Y. Nonlinear Harmonic Analysis Operator Theory and P.D.E. Ann. Math. Studies E. Stein ed. Princeton 1986

10.1002/cpa.3160410705

Greengard L., 1987, A fast algorithm for particle simulations, J. Comp. Phys., 73, 325, 10.1016/0021-9991(87)90140-9

Mallat S., 1988, Review of Multifrequency Channel Decomposition of Images and Wavelet Models, Technical Report, 412

Meyer Y., 1985, Principe d'incertitude, bases Hilbertiennes et algèbres d'opérateurs, Séminaire Bourbaki, 662

10.1017/CBO9780511662294.012

O'Donnel S. T. andRokhlin V. A Fast Algorithm for the Numerical Evaluation of Conformation Mappings Yale University Technical Report YALEU/DSC/RR‐554 1987 SIAM J. Sci. Stat. Comp. 1989 pp.475–487.

Stromberg J. O., A modified Haar system and higher order spline systems, Conf. in Harmonic Analysis in honor of Antoni Zygmund, 475

Thông tin
Thông tin xuất bản

Communications on Pure and Applied Mathematics

Tập 44 Số 2

141-183

Thông tin tác giả