The equations we consider in this book are primarily Fredholm integral equations of the second kind on bounded domains in the Euclidean space. These equations are used as mathematical models for a multitude of physical problems and cover many important applications, such as radiosity equations for realistic image synthesis [18, 85, 244] and especially boundary integral equations [12, 177, 203], which themselves occur as reformulations of other problems, typically originating as partial differential equations. In practice, Fredholm integral equations are solved numerically using piecewise polynomial collocation or Galerkin methods, and when the order of the coefficient matrix (which is typically full) is large, the computational cost of generating the matrix as well as solving the corresponding linear system is large. Therefore, to enhance the range of applicability of the Fredholm equation methodology, it is critical to provide alternate algorithms which are fast, efficient and accurate. This book is concerned with this challenge: designing fast multi scale methods for the numerical solution of Fredholm integral equations.

The development and use of multi scale methods for solving integral equations is a subject of recent intense study. The history of fast multi scale solutions of integral equations began with the introduction of multi scale Galerkin (Petrov–Galerkin) methods for solving integral equations, as presented in [28, 64, 68, 88, 94, 95, 202, 260, 261] and the references cited therein. Most noteworthy is the discovery in [28] that the representation of a singular integral operator by compactly supported orthonormal wavelets produces numerically sparse matrices. In other words, most of their entries are so small in absolute value that, to some degree of precision, they can be neglected without affecting the overall accuracy of the approximation. Later, the papers [94, 95] studied Petrov–Galerkin methods using periodic multi scale bases constructed from refinement equations for periodic elliptic pseudodifferential equations, and in this restricted environment, stability, convergence and matrix compression were investigated.