Top Eigenpairs of Large Scale Matrices

Abstract

This paper is devoted to the study of an extended global algorithm on computing the top eigenpairs of a large class of matrices. Three versions of the algorithm are presented that includes a preliminary version for real matrices, one for complex matrices, and one for large scale sparse real matrix. Some examples are illustrated as powerful applications of the algorithms. The main contributions of the paper are two localized estimation techniques, plus the use of a machine learning inspired approach in terms of a modified power iteration. Based on these new tools, the proposed algorithm successfully employs the inverse iteration with varying shifts (a very fast “cubic algorithm”) to achieve a superior estimation accuracy and computation efficiency to existing approaches under the general setup considered in this work.

Keywords

Matrix eigenpair / extended global algorithm / localized estimation technique / top eigenpair / large sparse matrix

References

[1] Chen M.F. (2005). Eigenvalues, Inequalities, and Ergodic Theory. London: Springer.

[2] Chen M.F. (2016). Efficient initials for computing maximal eigenpair. Front. Math. China 11(6): 1379-1418.

[3] Chen M.F. (2017a). Global algorithms for maximal eigenpair. Front. Math. China 12(5): 1023-1043.

[4] Chen M.F. (2017b). Trilogy on computingmaximal eigenpair. In: YueW., eds.Li, Q. L., Jin, S.,Ma, Z., “Queueing Theory and Network Applications”. QTNA 2017. LectureNotes in Comput. Sci., Vol. 10591. Cham:Springer,312-329.

[5] Chen M.F. (2018). Hermitizable, isospectral complex matrices or differential operators. Front. Math. China 13(6): 1267-1311.

[6] Chen M.F., Jia Z.G. and Pang H.K. (2021). Computing top eigenpairs of Hermitizable matrix. Front. Math. China 16(2): 345-379.

[7] Chen M.F., Li Y.S. (2019). Improved global algorithms for maximal eigenpair. Front.Math. China 14(6): 1077-1116.

[8] Lei Q., Zhong K., Dhillon I.S. (2016). Coordinate-wise power method. Proc. Advances in Neural Information Processing Systems, 2056-2064.

[9] Press W.H. et al. (2007). Numerical Recipes—The Art of Scientific Computing, 3rd ed. Cambridge Univ. Press.

[10] Varga R.S. (2004). Geršgorin and His Circles. Springer.

[11] Wang J.L., Wang W.R., Garber D., Srebro N. (2018). Efficient coordinate-wise leading eigenvector computation. Proc. Algorithmic Learning Theory, PMLR, 806-820.

[12] Xu Z.Q. (2018). Gradient descent meets shift-and-invert preconditioning for eigenvector computation. Proc. Advances in Neural Information Processing Systems, 31: 2825-2834.