Computing the Maximal Eigenpairs of Large Size Tridiagonal Matrices with sic(1) Number of Iterations

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 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., O(1) number of iterations. Consequently, the total cost for computing the maximal eigenpairs is O(N). The effectiveness of the proposed algorithm is demonstrated by numerical experiments.