Computing the Maximal Eigenpairs of Large Size Tridiagonal Matrices with $\mathcal{O}(1)$ Number of Iterations

Abstract

In a series of papers, Chen [4–6] developed some efficient algorithms for computing the maximal eigenpairs for tridiagonal matrices. The key idea is to explicitly construct effective initials for the maximal eigenpairs and also to employ a self-closed iterative algorithm. In this paper, we extend Chen's algorithm to deal with large scale tridiagonal matrices with super-/sub-diagonal elements. By using appropriate scalings and by optimizing numerical complexity, we make the computational cost for each iteration to be $\mathcal{O}$($N$). Moreover, to obtain accurate approximations for the maximal eigenpairs, the total number of iterations is found to be independent of the matrix size, i.e., $\mathcal{O}$($1$) number of iterations. Consequently, the total cost for computing the maximal eigenpairs is $\mathcal{O}$($N$). The effectiveness of the proposed algorithm is demonstrated by numerical experiments.