A MULTISCALE WAVELET SOLVER WITH O(N) COMPLEXITY

摘要

In this paper, we use the biorthogonal wavelets recently constructed by Dahlke and Weinreich to implement a highly efficient procedure for solving a certain class of one-dimensional problems, (partial derivative(2l)/partial derivative x(2l))u = f, I is an element of Z, I > 0. For these problems, the discrete biorthogonal wavelet transform allows us to set up a system of wavelet-Galerkin equations in which the scales are uncoupled, so that a true multiscale solution procedure may be formulated. We prove that the resulting stiffness matrix is in fact an almost perfectly diagonal matrix (the original aim of the construction was to achieve a block diagonal structure) and we show that this leads to an algorithm whose cost is O(n). We also present numerical results which demonstrate that the multiscale biorthogonal wavelet algorithm is superior to the more conventional single scale orthogonal wavelet approach both in terms of speed and in terms of convergence. (C) 1995 Academic Press, Inc. [References: 14]