Direct solvers

Roughly speaking, the FMM is an algorithm for rapidly determining the vector

f = A u aaaaaaaa(1)

where A is an operator and u is a given vector. It is possible to solve the converse problem of determining u, given f, by combining a fast multiplication algorithm with the use of an "iterative solver" (such as, e.g., GMRES). If A has appropriate spectral properties (as it frequently does when (1) results from rewriting a PDE as a second kind integral equation), only a small number of iterations are required.

More recently, work has been under way for directly inverting the operator in (1), rather than just applying it to a vector. Specifically, given an operator A that satisfies certain properties (see ???), there exist algorithms for rapidly computing an operator B such that

B &asymp A^-1.

Such an algorithm can of course be used to solve the equation (1) directly; but it can also be used to compute spectral decompositions of the operator A, to solve problems in multiscale modelling, etc.

In the context of developing fast numerical methods for solving PDEs, the new direct methods have several advantages over earlier methods based on iterative solvers:

• The CPU time requirement of an iterative solver depends on the number of iterations required, which in turn is held hostage to the spectral properties of the operator. In many cases, a large number of iterations are required, making direct methods considerably faster.
• Iterative methods derive only limited advantage when several equations involving the same system matrix are to be solved (the "multiple right hand sides" environment). Direct methods, in contrast, are very fast in this environment.
• Direct methods are very well suited for determining spectral properties of the operator.

Publications related to direct solvers include:

=== "A fast direct solver for boundary integral equations in two dimensions"
This is where we first presented the algorithm.

=== "A fast direct solver for scattering problems involving elongated structures"
The O(N) direct solver is generally speaking not applicable to high frequency scattering problems. However, it so happens that for elongated scatterers, it is (the importance of this fact to numerical methods was first observed by Chew and Michielssen).

=== "Rapid evaluation of electro-static interactions in multi-phase dielectric media"
Direct solvers are particularly efficient for solving problems involving multiple right hand sides. One situation where this occurs concerns Monte-Carlo, or molecular dynamics, simulations of a system of electrically charged particles in a dielectric medium containing regions with different dielectric constants. Such simulations occur in modelling of macro-molecues in ionic solutions, and in modelling of semi-conductors.

=== "A fast algorithm for the inversion of general Toeplitz matrices".
The fast solver is applicable for inverting matrices whose off-diagonal blocks have low rank. The Fourier representation of a Toeplitz matrix has this property.

=== An O(N) direct algorithm for computing conformal maps via the Kerzman-Stein equation"
The standard formula for evaluating the conformal mapping from a region in the plane to a circle is the so called "Kerzma-Stein" integral equation. The operator in this equation can be directly inverted.

=== "Model reduction for multiscale problems using operator compression"
A hobby-horse of mine is that multiscale modelling should be done by approximating the inverse of the differential operator, rather than by "homogenizing" the operator itself. (The inverse, unlike the differential operator, is very mild-mannered.) This approximation can be performed using the machinery developed for the direct solver.