×

The structured distance to normality of Toeplitz matrices with application to preconditioning. (English) Zbl 1245.65036

An explicit formula for computing the distance in Frobenius norm to a given Toeplitz matrix is presented for generalized Hermitian Toeplitz and particular circulant matrices. The minimization problem for computing the closest \(\{e^{i\varphi }\}\)-circulant matrix is closely related to a minimization problem for finding suitable preconditiers. Some applications where systems with Toeplitz matrices are preconditioned by \(\{e^{i\varphi }\}\)-circulant matrices are presented, theoretical and numerical results provide information on the performance of these preconditioners.

MSC:

65F08 Preconditioners for iterative methods
15B05 Toeplitz, Cauchy, and related matrices
65F10 Iterative numerical methods for linear systems
15B57 Hermitian, skew-Hermitian, and related matrices

Software:

tpls; smt
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Fischer, On Fourier-Toeplitz methods for separable elliptic problems, Mathematics of Computation 28 pp 349– (1974) · Zbl 0277.65065 · doi:10.1090/S0025-5718-1974-0415995-2
[2] Grenander, Toeplitz Forms and Their Applications (1984) · Zbl 0611.47018
[3] Modern Signal Processing (1985)
[4] Redivo-Zaglia M Rodriguez G A MATLAB structured matrices toolbox 2009
[5] Reichel, Mathematics in Signal Processing II pp 575– (1990)
[6] Rodriguez, Fast solution of Toeplitz- and Cauchy-like least squares problems, SIAM Journal on Matrix Analysis and Applications 28 pp 724– (2006) · Zbl 1157.65355 · doi:10.1137/050629148
[7] Davis, Circulant Matrices (1994)
[8] Ng, Iterative Methods for Toeplitz Systems (2004) · Zbl 1059.65031
[9] Farenick, Normal Toeplitz matrices, SIAM Journal on Matrix Analysis and Applications 17 pp 1037– (1996) · Zbl 0870.15015 · doi:10.1137/S0895479895287080
[10] Gu, Commutation relations for Toeplitz and Hankel matrices, SIAM Journal on Matrix Analysis and Applications 24 pp 728– (2003) · Zbl 1040.15013 · doi:10.1137/S0895479800377320
[11] Ito, Every normal Toeplitz matrix is either of type I or of type II, SIAM Journal on Matrix Analysis and Applications 17 pp 998– (1996) · Zbl 0870.15014 · doi:10.1137/S0895479895293156
[12] Henrici, Bounds for iterates, inverses, spectral variation and field of values of non-normal matrices, Numerische Mathematik 4 pp 24– (1962) · Zbl 0102.01502 · doi:10.1007/BF01386294
[13] Higham, Applications of Matrix Theory pp 1– (1989)
[14] László, An attainable lower bound for the best normal approximation, SIAM Journal on Matrix Analysis and Applications 15 pp 1035– (1994) · Zbl 0827.15037 · doi:10.1137/S0895479892232303
[15] Noschese, The structured distance to normality of an irreducible real tridiagonal matrix, Electronic Transactions on Numerical Analysis 28 pp 65– (2007) · Zbl 1171.65037
[16] Noschese, The structured distance to normality of banded Toeplitz matrices, BIT 49 pp 629– (2009) · Zbl 1178.15016 · doi:10.1007/s10543-009-0231-2
[17] Ruhe, Closest normal matrix finally found!, BIT 27 pp 585– (1987) · Zbl 0636.15017 · doi:10.1007/BF01937278
[18] Causey RL On closest normal matrices 1964
[19] Chan, An optimal circulant preconditioner for Toeplitz systems, SIAM Journal on Scientific and Statistical Computing 9 pp 766– (1988) · Zbl 0646.65042 · doi:10.1137/0909051
[20] Chan, An Introduction to Iterative Toeplitz Solvers (2007) · Zbl 1146.65028 · doi:10.1137/1.9780898718850
[21] Strela, Which circulant preconditioner is better?, Mathematics of Computation 65 pp 137– (1996) · Zbl 0847.65029 · doi:10.1090/S0025-5718-96-00682-5
[22] Chan, Circulant preconditioners for complex Toeplitz matrices, SIAM Journal on Numerical Analysis 30 pp 1193– (1993) · Zbl 0787.65017 · doi:10.1137/0730062
[23] Chan, Toeplitz preconditioners for Hermitian Toeplitz systems, Linear Algebra and its Applications 190 pp 181– (1993) · Zbl 0783.65042 · doi:10.1016/0024-3795(93)90226-E
[24] Potts, Preconditioners for ill-conditioned Toeplitz matrices, BIT 39 pp 513– (1999) · Zbl 0938.65067 · doi:10.1023/A:1022322820082
[25] Chan, The circulant operator in the Banach algebra of matrices, Linear Algebra and its Applications 149 pp 41– (1991) · Zbl 0717.15017 · doi:10.1016/0024-3795(91)90324-P
[26] Chan, Circulant preconditioners for Toeplitz matrices with positive continuous generating functions, Mathematics of Computation 58 pp 233– (1992) · Zbl 0744.65025 · doi:10.1090/S0025-5718-1992-1106960-1
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.