A multiscale wavelet solver with \(O(n)\) complexity (Q1903813)

The biorthogonal wavelets recently constructed by [\textit{S. Dahlke} and \textit{I. Weinreich} [Constructive Approximation 9, No. 2-3, 237-262 (1993; Zbl 0777.34015)] open new possibilities for the development of rapid and highly accurate solution procedures for ordinary and partial differential equations. The authors show that their construction leads to an almost perfectly diagonal stiffness matrix when the wavelet-Galerkin method is applied to a certain class of problems. This trivializes the task of inverting the stiffness matrix, allowing us to solve such problems in \(O(n)\) time. Numerical results demonstrate that the biorthogonal wavelet algorithm is superior to the more conventional approach.