Optimal rank matrix algebras preconditioners

详细信息    查看全文

• 作者：F. Tudisco^a ; ^{tudisco@mat.uniroma2.it} ; C. Di Fiore^a ; ¹ ; E.E. Tyrtyshnikov^b ; ²
• 关键词：65F05 ; 65F10 ; 65F15 ; 65F50 ; 65T50
• 刊名：Linear Algebra and its Applications
• 出版年：2013
• 出版时间：1 January, 2013
• 年：2013
• 卷：438
• 期：1
• 页码：405-427
• 全文大小：404 K

文摘

When a linear system is solved by means of iterative methods (mainly CG and GMRES) and the convergence rate is slow, one may consider a preconditioner and move to the preconditioned system . The use of such preconditioner changes the spectrum of the matrix defining the system and could result into a great acceleration of the convergence rate. The construction of optimal rank preconditioners is strongly related to the possibility of splitting as , where is a small perturbation and is of low rank (Tyrtyshnikov, 1996) . In the present work we extend the black-dot algorithm for the computation of such splitting for circulant (see Oseledets and Tyrtyshnikov, 2006 ), to the case where is in , for several known low-complexity matrix algebras . The algorithm so obtained is particularly efficient when is Toeplitz plus Hankel like. We finally discuss in detail the existence and the properties of the decomposition when is Toeplitz, also extending to the -circulant and Hartley-type cases some results previously known for circulant.