Rank-revealing decomposition of symmetric indefinite matrices via block anti-triangular factorization

详细信息    查看全文

• 作者：Nicola Mastronardi^a ; ¹ ; ^{n.mastronardi@ba.iac.cnr.it" class="auth_mail" title="E-mail the corresponding author} ; Paul Van Dooren^b ; ² ; ^{paul.vandooren@uclouvain.be" class="auth_mail" title="E-mail the corresponding author}
• 关键词：65F30 ; 65F35 ; 15A23
• 刊名：Linear Algebra and its Applications
• 出版年：2016
• 出版时间：1 August 2016
• 年：2016
• 卷：502
• 期：Complete
• 页码：126-139
• 全文大小：501 K

文摘

We present an algorithm for computing a symmetric rank-revealing decomposition of a symmetric n×n$n\times n$ matrix A, as defined in the work of Hansen & Yalamov [9]: we factorize the original matrix into a product A=QMQ^T$A=QM{Q}^T$, with Q orthogonal and M symmetric and in block form, with one of the blocks containing the dominant information of A, such as its largest eigenvalues. Moreover, the matrix M is constructed in a form that is easy to update when adding to A a symmetric rank-one matrix or when appending a row and, symmetrically, a column to A  : the cost of such an updating is O(n²)$O(n^2)$ floating point operations.

The proposed algorithm is based on the block anti-triangular form of the original matrix M, as introduced by the authors in [11]. Via successive orthogonal similarity transformations this form is then updated to a new form $A=\hat{Q}\hat{M}{\hat{Q}}^T$, whereby the first k   rows and columns of $\hat{M}$ have elements bounded by a given threshold τ   and the remaining bottom right part of $\hat{M}$ is maintained in block anti-triangular form. The updating transformations are all orthogonal, guaranteeing the backward stability of the algorithm, and the algorithm is very economical when the near rank deficiency is detected in some of the anti diagonal elements of the block anti-triangular form. Numerical results are also given showing the reliability of the proposed algorithm.