A preconditioner for systems with symmetric Toeplitz blocks

S. Salapaka, A. Peirce, M. Dahleh

Research output: Contribution to journalConference article

Abstract

This paper proposes and studies the performance of a preconditioner used in the preconditioned conjugate gradient method for solving a class of symmetric positive definite systems, Apx = b, which we call Lower Rank Extracted Systems (LRES). These systems correspond to integral equations with convolution kernels defined on a union of many line segments in contrast to only one line segment in the case of Toeplitz systems. The p × p matrix, Ap, is shown to be a principal submatrix of a larger N × N Toeplitz matrix, AN. The preconditioner is provided in terms of the inverse of a 2N × 2N circular matrix constructed from the elements of AN. The preconditioner is shown to yield clustering in the spectrum of preconditioned matrix similar to the clustering results in iterative algorithms used to solve Toeplitz systems. The analysis further demonstrates that the computational expense to solve LRE systems is reduced to O(N log N).

Original languageEnglish (US)
Pages (from-to)4039-4044
Number of pages6
JournalProceedings of the IEEE Conference on Decision and Control
Volume5
StatePublished - Dec 1 2001
Externally publishedYes
Event40th IEEE Conference on Decision and Control (CDC) - Orlando, FL, United States
Duration: Dec 4 2001Dec 7 2001

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Fingerprint Dive into the research topics of 'A preconditioner for systems with symmetric Toeplitz blocks'. Together they form a unique fingerprint.

  • Cite this