Premium
Matrix‐free constructions of circulant and block circulant preconditioners
Author(s) -
Yang Chao,
Ng Esmond G.,
Penczek Pawel A.
Publication year - 2004
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.346
Subject(s) - circulant matrix , eigenvalues and eigenvectors , mathematics , preconditioner , matrix (chemical analysis) , multiplication (music) , linear system , block (permutation group theory) , algorithm , fast fourier transform , combinatorics , mathematical analysis , quantum mechanics , composite material , physics , materials science
A framework for constructing circulant and block circulant preconditioners ( C ) for a symmetric linear system Ax = b arising from signal and image processing applications is presented in this paper. The proposed scheme does not make explicit use of matrix elements of A . It is ideal for applications in which A only exists in the form of a matrix vector multiplication routine, and in which the process of extracting matrix elements of A is costly. The proposed algorithm takes advantage of the fact that for many linear systems arising from signal or image processing applications, eigenvectors of A can be well represented by a small number of Fourier modes. Therefore, the construction of C can be carried out in the frequency domain by carefully choosing the eigenvalues of C so that the condition number of C T AC can be reduced significantly. We illustrate how to construct the spectrum of C in a way that allows the smallest eigenvalues of C T AC to overlap with those of A extremely well while making the largest eigenvalues of C T AC several orders of magnitude smaller than those of A . Numerical examples are provided to demonstrate the effectiveness of the preconditioner on accelerating the solution of linear systems arising from image reconstruction applications. Copyright © 2004 John Wiley & Sons, Ltd.