  An algorithm for the direct inversion of the linear systems arising from
Nystrom discretization of integral equations on one-dimensional domains is
described. The method typically has O(N) complexity when applied to boundary
integral equations (BIEs) in the plane with non-oscillatory kernels such as
those associated with the Laplace and Stokes' equations. The scaling
coefficient suppressed by the "big-O" notation depends logarithmically on the
requested accuracy. The method can also be applied to BIEs with oscillatory
kernels such as those associated with the Helmholtz and Maxwell equations; it
is efficient at long and intermediate wave-lengths, but will eventually become
prohibitively slow as the wave-length decreases. To achieve linear complexity,
rank deficiencies in the off-diagonal blocks of the coefficient matrix are
exploited. The technique is conceptually related to the H and H^2 matrix
arithmetic of Hackbusch and co-workers, and is closely related to previous work
on Hierarchically Semi-Separable matrices.

Numerical Analysis