Efficient Solutions to Lower Rank Extracted Systems

This presentation proposes efficient numerical solutions to a class of symmetric positive definite linear systems Ax=b, called Lower Rank Extracted Systems (LRES). These systems appear in a wide range of scientific and engineering models such as in image reconstruction in image processing, in the modeling of interacting cracks, in the modeling of tabular mining excavations, the modeling of planar array antennae in the field of telecommunications.

These systems appear in the numerical modeling of convolution type integral equations defined on arbitrary domains. This is in contrast to the Toeplitz systems which considers only rectangular domains. We compute their solution using a recursive method called the Preconditioned Conjugate Gradient Method (PCGM). Our contribution lies in prescribing a preconditioning matrix and proving that it achieves a substantial reduction in the computational expense. In the case of integral equations defined on one dimensional domains, we have proved that our approach reduces the computational from O(N^2) to O(N log N) operations where N is the size of the coefficient matrix A. We have generalized this approach to solve convolution type integral equations defined on a class of higher dimensional domains called the p-dimensional Lower Rank Extracted Systems (p-d LRES). The method that we propose is shown to yield clustering in the spectrum of the preconditioned matrix which leads to a substantial reduction in the computational expense.