Sparse Representation of Smooth Linear Operators
Abstract
A wide variety of problems in differential and integral equations require application and inversion of linear operators. For large-scale physical problems, the size of the problem n is such that the work expended by general algorithms-O(n squared) for application of a transformation and O(n cubed) for application of its inverse-is often 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 spaces, 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 fixed width. Algorithms are presented for transforming such locally smooth matrices into matrices which are sparse (to a finite but arbitrarily high accuracy). The resulting sparse representations support fast algorithms for matrix application and inversion, requiring variously O(n), O(n log n), and O(n log squared 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. (kr)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1990
- Accession Number
- ADA228142
Entities
People
- Bradley K. Alpert
Organizations
- Yale University