TY - JOUR
T1 - Sine transform based preconditioners for symmetric Toeplitz systems
AU - Chan, Raymond H.
AU - Ng, Michael K.
AU - Wong, C. K.
PY - 1996/1/1
Y1 - 1996/1/1
N2 - The optimal circulant preconditioner for a given matrix A is defined to be the minimizer of ∥C - A∥F over the set of all circulant matrices C. Here ∥·∥F is the Frobenius norm. Optimal circulant preconditioners have been proved to be good preconditioners in solving Toeplitz systems with the preconditioned conjugate gradient method. In this paper, we construct an optimal sine transform based preconditioner which is defined to be the minimizer of ∥B - A∥F over the set of matrices B that can be diagonalized by sine transforms. We will prove that for general n-by-n matrices A, these optimal preconditioners can be constructed in O (n2) real operations and in O (n) real operations if A is Toeplitz. We will also show that the convergence properties of these optimal sine transform preconditioners are the same as that of the optimal circulant ones when they are employed to solve Toeplitz systems. Numerical examples are given to support our convergence analysis.
AB - The optimal circulant preconditioner for a given matrix A is defined to be the minimizer of ∥C - A∥F over the set of all circulant matrices C. Here ∥·∥F is the Frobenius norm. Optimal circulant preconditioners have been proved to be good preconditioners in solving Toeplitz systems with the preconditioned conjugate gradient method. In this paper, we construct an optimal sine transform based preconditioner which is defined to be the minimizer of ∥B - A∥F over the set of matrices B that can be diagonalized by sine transforms. We will prove that for general n-by-n matrices A, these optimal preconditioners can be constructed in O (n2) real operations and in O (n) real operations if A is Toeplitz. We will also show that the convergence properties of these optimal sine transform preconditioners are the same as that of the optimal circulant ones when they are employed to solve Toeplitz systems. Numerical examples are given to support our convergence analysis.
UR - http://www.scopus.com/inward/record.url?scp=21844523518&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-21844523518&origin=recordpage
U2 - 10.1016/0024-3795(94)00049-2
DO - 10.1016/0024-3795(94)00049-2
M3 - 21_Publication in refereed journal
VL - 232
SP - 237
EP - 259
JO - Linear Algebra and Its Applications
JF - Linear Algebra and Its Applications
SN - 0024-3795
IS - 1-3
ER -