LU factorization of non-standard forms and direct multiresolution solvers (Q1267269)

This is an expository paper which tries to convince the reader that it may be advantageous to solve large linear systems of equations by transforming to a wavelet coordinate system, neglect then all matrix elements below a certain threshold \(\varepsilon\), perform specialized LU decomposition, forward and backward substitution on all wavelet scales, and transforming back. The algorithms for these decompositions and substitutions are explained in detail. The approach shows some similarity to a multigrid V-cycle -- but constitutes a direct solver (up to the neglections). Possible applications include selfadjoint elliptic equations or equations with pseudodifferential operator. The matrices obtained after discretization may be full. Operation count is mentioned to be \(O(n \ln(1/\varepsilon))\) with \(n\) the order of the system. This linear dependence of the number of operations on \(n\) is visible in the numerical results given (for matrices of orders from 128 to 2048). What does not become clear is a possible interplay between \(\varepsilon\), the number of vanishing moments of the wavelets, the half bandwidth considered, and \(n\). In the numerical examples, the accuracy reached is of the order \(\varepsilon\).