×

Solution of Toeplitz normal equations by sine transform based preconditioning. (English) Zbl 0935.65036

The normal equations constructed by a Toeplitz matrix are studied and a suitable preconditioner related to the discrete sine transform is found. New results about the structure of the product of two Toeplitz matrices are given. This allows the conjugate gradient method applied to the normal equations to achieve a superlinear rate of convergence. The proposed preconditioner outperforms the circulant one for the iterative solution of Toeplitz least squares problems. Such a strategy can also be applied to linear systems with nonsymmetric coefficient matrices. The block generalization of the algorithm is discussed which make the new technique applicable to some problems in multichannel signal processing and two-dimensional image restoration. Results and discussion from numerical experiments using MATLAB are given.
Reviewer: K.Georgiev (Sofia)

MSC:

65F20 Numerical solutions to overdetermined systems, pseudoinverses
68U10 Computing methodologies for image processing
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
65F10 Iterative numerical methods for linear systems
65F35 Numerical computation of matrix norms, conditioning, scaling

Software:

Matlab; CGS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ammar, G.; Gragg, W., Superfast solution of real positive definite Toeplitz systems, SIAM J. Matrix Anal. Appl., 9, 61-76 (1988) · Zbl 0658.65022
[2] Bini, D.; Capovani, M., Spectral and computational properties of band symmetric Toeplitz matrices, Linear Algebra Appl., 52, 99-126 (1983) · Zbl 0549.15005
[3] Bini, D.; Di Benedetto, F., A new preconditioner for the parallel solution of positive definite Toeplitz systems, (Proceedings of the Second Annual SPAA (1990), ACM Press: ACM Press Crete, Greece), 220-223
[4] Boman, E.; Koltracht, I., Fast transform based preconditioners for Toeplitz equations, SIAM J. Matrix Anal. Appl., 16, 628-645 (1995) · Zbl 0826.65045
[5] Bunch, J. R., Stability of methods for solving Toeplitz systems of equations, SIAM J. Sci. Stat. Comp., 6, 349-364 (1985) · Zbl 0569.65019
[6] Chan, R. H.; Jin, X. Q., A family of block preconditioners for block systems, SIAM J. Sci. Stat. Comp., 13, 1218-1235 (1992) · Zbl 0760.65027
[7] Chan, R. H.; Nagy, J. G.; Plemmons, R. J., FFT-based preconditioners for Toeplitz-block least squares problems, SIAM J. Numer. Anal., 30, 1740-1768 (1993) · Zbl 0793.65029
[8] Chan, R. H.; Nagy, J. G.; Plemmons, R. J., Circulant preconditioned Toeplitz least squares iterations, SIAM J. Matrix Anal. Appl., 15, 80-97 (1994) · Zbl 0799.65046
[9] Chan, R. H.; Nagy, J. G.; Plemmons, R. J., Displacement preconditioner for Toeplitz least squares iterations, Elec. Trans. Numer. Anal., 2, 44-56 (1994) · Zbl 0809.65038
[10] Chan, R. H.; Ng, K. P., Toeplitz preconditioners for Hermitian Toeplitz systems, Linear Algebra Appl., 190, 181-208 (1993) · Zbl 0783.65042
[11] Chan, R. H.; Ng, M., Conjugate gradient methods for Toeplitz systems, SIAM Rev., 38, 427-482 (1996) · Zbl 0863.65013
[12] Chan, R. H.; Ng, M.; Wong, C. K., Sine transform based preconditioners for symmetric Toeplitz systems, Linear Algebra Appl., 232, 237-260 (1996) · Zbl 0837.65043
[13] Chan, R. H.; Strang, G., Toeplitz equations by conjugate gradients with circulant preconditioner, SIAM J. Sci. Stat. Comp., 10, 104-119 (1989) · Zbl 0666.65030
[14] Chan, T., An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Stat. Comp., 9, 766-771 (1988) · Zbl 0646.65042
[15] Di Benedetto, F., Analysis of preconditioning techniques for ill-conditioned Toeplitz matrices, SIAM J. Sci. Comp., 16, 682-697 (1995) · Zbl 0830.65032
[16] Di Benedetto, F., Iterative solution of Toeplitz systems by preconditioning with the discrete sine transform, (Luk, F., Proceedings of the SPIE Conference on Advanced Signal Processing Algorithms, Architectures, and Implementations, San Diego, CA, vol. 2563 (1995)), 302-312
[17] Di Benedetto, F., Preconditioning of block Toeplitz matrices by sine transforms, SIAM J. Sci. Comp., 18, 499-515 (1997) · Zbl 0871.65032
[18] Di Benedetto, F.; Fiorentino, G.; Serra, S., C.G. preconditioning for Toeplitz matrices, Computers Math. Appl., 25, 35-45 (1993) · Zbl 0782.65063
[19] F. Di Benedetto, S. Serra Capizzano, A unifying approach to abstract matrix algebra preconditioning, Numer. Math. (to appear).; F. Di Benedetto, S. Serra Capizzano, A unifying approach to abstract matrix algebra preconditioning, Numer. Math. (to appear). · Zbl 0930.65050
[20] Golub, G. H.; Van Loan, C., Matrix Computations (1983), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore, MD · Zbl 0559.65011
[21] Hestenes, M. R.; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Standards, 49, 409-435 (1952) · Zbl 0048.09901
[22] Justice, J. H., A Levinson-type algorithm for two-dimensional Wiener filtering using bivariate Szegö polynomials, (Proc. IEEE, 65 (1977)), 882-886
[23] Ku, T. K.; Kuo, C. C.J., On the spectrum of a family of preconditioned block Toeplitz matrices, SIAM J. Sci. Stat. Comp., 13, 948-966 (1992) · Zbl 0756.65048
[24] Ku, T. K.; Kuo, C. C.J., Spectral properties of preconditioned rational Toeplitz matrices: The nonsymmetric case, SIAM J. Matrix Anal. Appl., 14, 521-544 (1993) · Zbl 0773.65019
[25] Levy, B. C.; Adams, M. B.; Willsky, A. S., Solution and linear estimation of 2-D nearest-neighbor models, (Proc. IEEE, 78 (1990)), 627-641
[26] Mertens, L.; Van de Vel, H., A special class of structured matrices constructed with the Kronecker product and its use for difference equations, Linear Algebra Appl., 106, 117-147 (1988) · Zbl 0646.15018
[27] Nagy, J. G.; Plemmons, R. J., Iterative image restoration using FFT-based preconditioners, (Proceedings of The Allerton Conference (1992), University of Illinois: University of Illinois Champaign, Urbana)
[28] Parter, S. V., On the distribution of the singular values of Toeplitz matrices, Linear Algebra Appl., 80, 115-130 (1986) · Zbl 0601.15006
[29] S. Serra, Superlinear PCG methods for symmetric Toeplitz systems, Math. Comp. (to appear).; S. Serra, Superlinear PCG methods for symmetric Toeplitz systems, Math. Comp. (to appear). · Zbl 1043.65066
[30] Sonneveld, P., CGS: A fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Stat. Comp., 10, 115-130 (1989) · Zbl 0666.65029
[31] Tyrtyshnikov, E., Influence of matrix operations on the distribution of eigenvalues and singular values of Toeplitz matrices, Linear Algebra Appl., 207, 225-249 (1994) · Zbl 0813.15005
[32] Tyrtyshnikov, E., A unifying approach to some old and new theorems on distribution and clustering, Linear Algebra Appl., 232, 1-43 (1996) · Zbl 0841.15006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.