TY - JOUR
T1 - Recursive-Based PCG Methods for Toeplitz Systems with Nonnegative Generating Functions
AU - Ng, Michael K.
AU - Sun, Hai Wei
AU - Jin, Xiao Qing
N1 - Department of Mathematics, The University of Hong Kong, Pokfulam Road, Hong Kong ([email protected]). The research of this author was supported in part by Hong Kong Research Grants Council grants HKU 7132/00P and HKU 7130/02P, and HKU CRCG grants 10202720, 10203501, and 10203907.
Department of Applied Mathematics, Guangdong University of Technology, Guangzhou 510090, People’s Republic of China. The research of this author was supported by Guangdong Provincial Natural Science Foundation of China grant 974176, Natural Science Foundation of China grant 19971018, and HKRGC grant CUHK 4207/97P.
Faculty of Science and Technology, University of Macau, Macau, China. The research of this author was supported by UM Research grants RG009/98-99S/JXQ/FST and RG010/99-00S/JXQ/FST.
Publisher Copyright:
© 2003 Society for Industrial and Applied Mathematics.
PY - 2003/1
Y1 - 2003/1
N2 - In this paper, we consider the solutions of symmetric positive definite, but ill-conditioned, Toeplitz systems Anx = b. Here we propose to solve the system by the recursive-based preconditioned conjugate gradient method. The idea is to use the inverse of Am (the principal submatrix of An) with the Gohberg-Semencul formula as a preconditioner for An. The inverse of Am can be generated recursively by using the formula until m is small enough. The construction of the preconditioners requires only the entries of An and does not require the explicit knowledge of the generating function f of An. We show that if f is a nonnegative, bounded, and piecewise continuous even function with a finite number of zeros of even order, the spectra of the preconditioned matrices are uniformly bounded except for a fixed number of outliers. Hence the conjugate gradient method, when applied to solving the preconditioned system, converges very quickly. Numerical results are included to illustrate the effectiveness of our approach.
AB - In this paper, we consider the solutions of symmetric positive definite, but ill-conditioned, Toeplitz systems Anx = b. Here we propose to solve the system by the recursive-based preconditioned conjugate gradient method. The idea is to use the inverse of Am (the principal submatrix of An) with the Gohberg-Semencul formula as a preconditioner for An. The inverse of Am can be generated recursively by using the formula until m is small enough. The construction of the preconditioners requires only the entries of An and does not require the explicit knowledge of the generating function f of An. We show that if f is a nonnegative, bounded, and piecewise continuous even function with a finite number of zeros of even order, the spectra of the preconditioned matrices are uniformly bounded except for a fixed number of outliers. Hence the conjugate gradient method, when applied to solving the preconditioned system, converges very quickly. Numerical results are included to illustrate the effectiveness of our approach.
KW - Toeplitz matrices
KW - Gohberg–Semencul formula
KW - recursive-based method
KW - preconditioned conjugate gradient method
KW - preconditioners
UR - http://www.scopus.com/inward/record.url?scp=0141940605&partnerID=8YFLogxK
U2 - 10.1137/S1064827500378155
DO - 10.1137/S1064827500378155
M3 - Journal article
AN - SCOPUS:0141940605
SN - 1064-8275
VL - 24
SP - 1507
EP - 1529
JO - SIAM Journal on Scientific Computing
JF - SIAM Journal on Scientific Computing
IS - 5
ER -