Multiscale Computation with Interpolating Wavelets

Abstract

Multiresolution analyses based upon interpolets, interpolating scaling functions introduced by Deslauriers and Dubuc, are particularly well-suited to physical applications because they allow exact recovery of the multiresolution representation of a function from its sample values on a finite set of points in space. We present a detailed study of the application of wavelet concepts to physical problems expressed in such bases. The manuscript describes algorithms for the associated transforms which, for properly constructed grids of variable resolution, compute correctly without having to introduce extra grid points. We demonstrate that for the application of local homogeneous operators in such bases, the non-standard multiply of Beylkin, Coifman and Rokhlin also proceeds exactly for inhomogeneous grids of appropriate form. To obtain less stringent conditions on the grids, we generalize the non-standard multiply so that communication may proceed between non-adjacent levels. The manuscript concludes with timing comparisons against naive algorithms and an illustration of the scale-independence of the convergence rate of the conjugate gradient solution of Poisson's equation using a simple preconditioning, suggesting that this approach leads to an O(n) solution of this equation.

33 pages, figures available at http://laisla.mit.edu/muchomas/Papers/nonstand-figs.ps . Updated: (1) figures file (figs.ps) now appear with the posting on the server; (2) references got lost in the last submission

References in corpus (3)

• Multiresolution analysis of electronic structure: semicardinal and wavelet bases
• Linear Scaling Solution of the Coulomb problem using wavelets
• The Hopgrid algorithm: multilevel synthesis of multigrid and wavelet theory

Cited by in corpus (10)

• Multiresolution analysis of electronic structure: semicardinal and wavelet bases
• Real-space local polynomial basis for solid-state electronic-structure calculations: A finite-element approach
• Three real-space discretization techniques in electronic structure calculations
• Electron transport through an interacting region: The case of a nonorthogonal basis set
• The solution of multi-scale partial differential equations using wavelets
• Multiresolution analysis for efficient, high precision all-electron density-functional calculations
• Robust ab initio calculation of condensed matter: transparent convergence through semicardinal multiresolution analysis
• Wavelets for Density-Functional Theory and Post-Density-Functional-Theory Calculations
• Beyond Wavelets: Exactness theorems and algorithms for physical calculations
• An application of interpolating scaling functions to wave packet propagation