A unifying approach to the construction of circulant preconditioners

被引：15

作者：

Oseledets, Ivan ^{[1
]}

Tyrtyshnikov, Eugene ^{[1
]}

机构：

[1] Russian Acad Sci, Inst Numer Math, Moscow 119991, Russia

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 2006年 / 418卷 / 2-3期

基金：

俄罗斯基础研究基金会;

关键词：

matrix approximations; preconditioners; superlinear convergence; circulants; Toeplitz matrices; low-rank matrices; skeleton decomposition; spectral clusters; spectral distributions;

D O I：

10.1016/j.laa.2006.02.037

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The main result is the "black dot algorithm" and its fast version for the construction of a new circulant preconditioner for Toeplitz matrices. This new preconditioner C is sought directly as a solution to one of possible settings of the approximation problem A approximate to C + R, where A is a given matrix and R should be a "low-rank" matrix. This very problem is a key to the analysis of superlinear convergence properties of already established circulant and other matrix-algebra preconditioners. In this regard, our new preconditioner is likely to be the best of all possible circulant preconditioners. Moreover, in contrast to several "function-based" circulant preconditioners used for "bad" symbols, it is constructed entirely from the entries of a given matrix and performs equally as the best of the known or better than those for the same symbols. (c) 2006 Elsevier Inc. All rights reserved.

引用

页码：435 / 449

页数：15

共 15 条

[1]

Bebendorf M, 2000, NUMER MATH, V86, P565, DOI 10.1007/s002110000192

[2]

Bebendorf M, 2000, CH CRC RES NOTES MAT, V414, P45

[3]

Chan R.H., 2001, CONT MATH, V281, P175

[4]

Chan RH, 2000, SIAM J MATRIX ANAL A, V22, P647, DOI 10.1137/S0895479899362521

[5] AN OPTIMAL CIRCULANT PRECONDITIONER FOR TOEPLITZ-SYSTEMS [J].

CHAN, TF .

SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1988, 9 (04) :766-771

[6] SOLUTION OF LINEAR-EQUATIONS WITH RATIONAL TOEPLITZ MATRICES [J].

DICKINSON, BW .

MATHEMATICS OF COMPUTATION, 1980, 34 (149) :227-233

[7] A theory of pseudoskeleton approximations [J].

Goreinov, SA ;

Tyrtyshnikov, EE ;

Zamarashkin, NL .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1997, 261 :1-21

[8]

GOREINOV SA, 2001, CONT MATH, V280, P47

[9] SPECTRAL PROPERTIES OF PRECONDITIONED RATIONAL TOEPLITZ MATRICES - THE NONSYMMETRIC CASE [J].

KU, TK ;

KUO, CCJ .

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1993, 14 (02) :521-544

[10] A preconditioning proposal for ill-conditioned Hermitian two-level Toeplitz systems [J].

Noutsos, D ;

Capizzano, SS ;

Vassalos, P .

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS, 2005, 12 (2-3) :231-239

← 1 2 →