ABSTRACT Sparse Representation of Smooth Linear Operators

: A wide variety of problems in differentll and integral equations require a-plication and inversion of linear operators. or large-scale physical problems, t le size of the problem n is such that the work ex pended by general algorithms-O(n) for application of a transformation and 0(n) for application of its inverse-is of-ten prohibitive. Several methods have been devised in recent years to reduce these complexities by exploiting the structure of particular problems. This thesis puts earlier methods into a unified framework by developing new wavelet-like bases for 2[0, 1], and otheispaces, which lead to efficient algorithms for operator application and inversion. It is based on the observation that in many cases of interest, while the matrices involved are dense, their elements vary smoothly as a function of their indices, except along a collection of bands of fixe" width. Algorithms are presented for transforming such locally smooth ma ces into matrices which are sparse (to a finite but arbitrarily high accura,. The resulting sparse representations support fast algorithms for matr application and inversion, requiring variously 0(n), 0(n log n), and 0(n log n) operations. Programs have been developed applying these techniques to the solution of second-kind integral equations with non-oscillatory kernels. Numerical results are presented to demonstrate the effectiveness of the approach. ( 7