Saving flops in LU based shift-and-invert strategy

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:234

Article

Grigori, Laura²  Wakam, Desire Nuentsa³  Xiang, Hua^1,2 

[1] Wuhan Univ, Sch Math & Stat, Wuhan 430072, Peoples R China

[2] Univ Paris 11, INRIA Saclay Ile France, Rech Informat Lab, F-91405 Orsay, France

[3] INRIA, IRISA, F-35042 Rennes, France

关键词: Shift-and-invert;    Eigenvalue;    Divide and conquer;    LU factorization;   

DOI  :  10.1016/j.cam.2010.04.003

来源: Elsevier

【 摘 要 】

The shift-and-invert method is very efficient in eigenvalue computations, in particular when interior eigenvalues are sought. This method involves solving linear systems of the form (A - sigma 1)z = b. The shift a is variable, hence when a direct method is used to solve the linear system, the LU factorization of (A I) needs to be computed for every shift change. We present two strategies that reduce the number of floating point operations performed in the LU factorization when the shift changes. Both methods perform first a preprocessing step that aims at eliminating parts of the matrix that are not affected by the diagonal change. This leads to about 43% and 50% flops savings respectively for the dense matrices. (C) 2010 Elsevier B.V. All rights reserved.

【 授权许可】

Free