Wavelet-based Preconditioners for Dense Matrices with Non-Smooth Local Features

We present algorithms for the detection of local non-smooth features within a dense matrix and show how, by isolating such features, we are able to use wavelet compression to design preconditioners for the corresponding dense linear system. We illustrate our approach with examples from the solution of elastohydrodynamic lubrication problems and boundary integral equations.This revised version was published online in October 2005 with corrections to the Cover Date.