Analysis of a novel preconditioner for a class of p ‐level lower rank extracted systems

This paper proposes and studies the performance of a preconditioner suitable for solving a class of symmetric positive definite systems, Âx = b , which we call p ‐ level lower rank extracted systems ( p ‐ level LRES ), by the preconditioned conjugate gradient method. The study of these systems is motivated by the numerical approximation of integral equations with convolution kernels defined on arbitrary p ‐dimensional domains. This is in contrast to p ‐level Toeplitz systems which only apply to rectangular domains. The coefficient matrix, Â , is a principal submatrix of a p ‐level Toeplitz matrix, A , and the preconditioner for the preconditioned conjugate gradient algorithm is provided in terms of the inverse of a p ‐level circulant matrix constructed from the elements of A . The preconditioner is shown to yield clustering in the spectrum of the preconditioned matrix which leads to a substantial reduction in the computational cost of solving LRE systems. Copyright © 2006 John Wiley & Sons, Ltd.