Abstract
We propose two block preconditioners for Toeplitz-block matrices (i.e. each block is Toeplitz), intended to be used in conjunction with conjugate gradient methods. These preconditioners employ and extend existing circulant preconditioners for point Toeplitz matrices. The two preconditioners differ in whether the point circulant approximation is used once or twice, and also in the cost per step. We discuss efficient implementation of these two preconditioners, as well as some basic theoretical properties (such as preservation of symmetry and positive definiteness). We report results of numerical experiments, including an example from active noise control, to compare their performance.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. Bunch, Stability of methods for solving Toeplitz systems of equations, SIAM J. Sci. Stat. Comp. 6 (1985) 349–364.
R. Chan, Circulant preconditioners for Hermitian Toeplitz systems, SIAM J. Matrix Anal. Appl. 10 (1989) 542–550.
R. Chan and X. Jin, A family of block preconditioners for block systems, SIAM J. Sci. Stat. Comp., to appear.
R. Chan, X. Jin and M. Yeung, The circulant operator in the Banach algebra of matrices, Lin. Alg. Appl. 149 (1991) 41–53.
R. Chan, J.G. Nagy and R.J. Plemmons, Circulant preconditioned Toeplitz least squares iterations, Tech. Report, Dept. of Comp. Sci., Wake Forest Univ. (Nov. 1991).
R. Chan, J.G. Nagy and R.J. Plemmons, FFT-based preconditioners for Toeplitz-block least squares problems, SIAM J. Numer. Anal., to appear.
R. Chan and G. Strang, Toeplitz equations by conjugate gradients with circulant preconditioner, SIAM J. Sci. Statist. Comput. 10 (1989) 104–119.
T.F. Chan, An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput. 9 (1988) 766–771.
T.F. Chan and J.A. Olkin, Preconditioners for Toeplitz-block matrices,SIAM Conf. on Linear Algebra, San Francisco (1990).
T. Huckle, Circulant and skew-circulant matrices for solving Toeplitz matrix problems, SIAM J. Matrix Anal., to appear.
Ta-Kang Ku and C.C. Jay Kuo, Design and analysis of Toeplitz preconditioners IEEE Trans. Acoust. Speech Signal Processes, to appear.
Ta-Kang Ku and C.C. Jay Kuo, Spectral properties of preconditioned rational Toeplitz matrices: The nonsymmetric case, SIAM J. Matrix Anal. 14 (1993) 521–545.
N. Levinson, The Wiener rms error criterion in filter design and prediction, J. Math. Phys. 25 (1947) 261–278.
C. Van Loan,Computational Frameworks for the Fast Fourier Transform (Society for Industrial and Applied Mathematics, 1992).
J. Nagy, Toeplitz least squares computations, PhD thesis, North Carolina State University, Raleigh, NC (1991).
J.G. Nagy and R.J. Plemmons, Some fast Toeplitz least squares algorithms,Proc. SPIE Conf. on Advanced Signal Processing Algorithms, Architectures and Implementations II, San Diego, CA, vol. 1566 (July 1991).
J.A. Olkin, Linear and nonlinear deconvolution problems, PhD thesis, Rice University, Houston, TX (May 1986).
G. Strang, A proposal for Toeplitz matrix calculations, Stud. Appl. Math. 74 (1986) 171–176.
E.E. Tyrtyshnikov, Optimal and super-optimal circulant preconditioners, SIAM J. Matrix Anal., to appear.
E.E. Tyrtyshnikov, Constructive approach to develop vectorized and fast algorithms for special kind matrices, Sov. J. Numer. Anal. Math. Modelling 3 (1988) 409–430.
Author information
Authors and Affiliations
Additional information
Communicated by G.H. Golub
Research supported by SRI International and by the Army Research Office under contract DAAL03-91-G-0150 and by the Office of Naval Research under contract N00014-90-J-1695.
Rights and permissions
About this article
Cite this article
Chan, T.F., Olkin, J.A. Circulant preconditioners for Toeplitz-block matrices. Numer Algor 6, 89–101 (1994). https://doi.org/10.1007/BF02149764
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02149764