Multiple-rank Modification of Symmetric Eigenvalue Problem
This work addresses computational efficiency in updating eigenvalues after multiple-rank modifications, which is relevant for numerical linear algebra applications, but the improvements are incremental and limited to specific scenarios.
The paper proposes a rank-k modification algorithm for symmetric eigenvalue problems, achieving O(n^1.5) computation cost for rank-2 modifications, and generalizes to rank-k using the modified Sturm Theorem, showing improved efficiency over direct eigenvalue decomposition and perturbation methods.
Rank-1 modifications in k-times (k > 1) often are performed to achieve rank-k modification. We propose a rank- k modification for enhancing computational efficiency. As the first step towards a rank- k modification, an algorithm to perform rank-2 modification is proposed and tested. The computation cost of our proposed algorithm is in O(n^1.5). We also propose a general rank- k update algorithm based upon the modified Sturm Theorem, and compare our results from those of the direct eigenvalue decomposition and of a perturbation method.