A direct multilevel method based on multiresolution LU factorization is introduced, which, for a large class of elliptic operators, is capable of solving the corresponding linear system of algebraic equations, or computing the inverse operator, in O(N) operations. This method is somewhat similar to algebraic multigrid, in that projections between fine and coarse grids are performed directly on the matrix. We compute these projections using wavelet transforms, since such transforms are orthogonal.
We first introduce our approach within the context of multigrid. We then show how the wavelet transform may be used to construct the direct method, and give numerical results which verify the cost estimates. Finally, we show that our method also applies to integral operators which arise from strictly elliptic problems, since such operators have a sparse representation in the wavelet system of coordinates.