TY - JOUR
T1 - Toeplitz preconditioners for Hermitian Toeplitz systems
AU - Chan, Raymond H.
AU - Ng, Kwok-Po
PY - 1993/9/1
Y1 - 1993/9/1
N2 - We propose a new type of preconditioners for Hermitian positive definite Toeplitz systems Anx = b where An are assumed to be generated by functions f that are positive and 2π-periodic. Our approach is to precondition Ãn by the Toeplitz matrix Ãn generated by 1/ƒ. We prove that the resulting preconditioned matrix ÃnAn will have clustered spectrum. When Ãn cannot be formed efficiently, we use quadrature rules and convolution products to construct nearby approximations to Ãn. We show that the resulting approximations are Toeplitz matrices which can be written as sums of {ω}-circulant matrices. As a side result, we prove that any Toeplitz matrix can be written as a sum of {ω}-circulant matrices. We then show that our Toeplitz preconditioners Tn are generalizations of circulant preconditioners and the way they are constructed is similar to the approach used in the additive Schwarz method for elliptic problems. We finally prove that the preconditioned systems TnAn will have clustered spectra around 1.
AB - We propose a new type of preconditioners for Hermitian positive definite Toeplitz systems Anx = b where An are assumed to be generated by functions f that are positive and 2π-periodic. Our approach is to precondition Ãn by the Toeplitz matrix Ãn generated by 1/ƒ. We prove that the resulting preconditioned matrix ÃnAn will have clustered spectrum. When Ãn cannot be formed efficiently, we use quadrature rules and convolution products to construct nearby approximations to Ãn. We show that the resulting approximations are Toeplitz matrices which can be written as sums of {ω}-circulant matrices. As a side result, we prove that any Toeplitz matrix can be written as a sum of {ω}-circulant matrices. We then show that our Toeplitz preconditioners Tn are generalizations of circulant preconditioners and the way they are constructed is similar to the approach used in the additive Schwarz method for elliptic problems. We finally prove that the preconditioned systems TnAn will have clustered spectra around 1.
UR - http://www.scopus.com/inward/record.url?scp=38248999546&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-38248999546&origin=recordpage
U2 - 10.1016/0024-3795(93)90226-E
DO - 10.1016/0024-3795(93)90226-E
M3 - 21_Publication in refereed journal
VL - 190
SP - 181
EP - 208
JO - Linear Algebra and Its Applications
JF - Linear Algebra and Its Applications
SN - 0024-3795
ER -