Multiple-rank modification of symmetric eigenvalue problem

Abstract

Rank-1 modifications applied k-times (k > 1) often are performed to achieve a rank-k modification. We propose a rank- k modification for enhancing computational efficiency. As the first step toward a rank- k modification, an algorithm to perform a rank-2 modification is proposed and tested. The computation cost of our proposed algorithm is in O(n2) where n is the cardinality of the matrix of interest. We also propose a general rank-k update algorithm based on the Sturm Theorem, and compare our results to those of the direct eigenvalue decomposition and of a perturbation method. Keywords: Eigenvalue decomposition, Modification, Secular equation, Positive semi-definite matrices