×

A simple extrapolation method for clustered eigenvalues. (English) Zbl 1480.65085

Summary: This paper introduces a simple variant of the power method. It is shown analytically and numerically to accelerate convergence to the dominant eigenvalue/eigenvector pair, and it is particularly effective for problems featuring a small spectral gap. The introduced method is a one-step extrapolation technique that uses a linear combination of current and previous update steps to form a better approximation of the dominant eigenvector. The provided analysis shows the method converges exponentially with respect to the ratio between the two largest eigenvalues, which is also approximated during the process. An augmented technique is also introduced and is shown to stabilize the early stages of the iteration. Numerical examples are provided to illustrate the theory and demonstrate the methods.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A18 Eigenvalues, singular values, and eigenvectors
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Anderson, DG, Iterative procedures for nonlinear integral equations, J. Assoc. Comput. Mach., 12, 4, 547-560 (1965) · Zbl 0149.11503 · doi:10.1145/321296.321305
[2] Babuška, I., Osborn, J.: Eigenvalue problems. In: Ciarlet, P.G., Lions, J.L. (eds.) Handbook of Numerical Analysis. II: Finite Element Methods (Part 1), pp 641-787. North-Holland, Amsterdam (1991) · Zbl 0875.65087
[3] Bai, Z.Z., Wu, W.T., Muratova, G.V.: The power method and beyond. Appl. Numer. Math. doi:10.1016/j.apnum.2020.03.021 (2020) · Zbl 1460.65038
[4] Brezinski, C.; Redivo-Zaglia, M., Hybrid procedures for solving linear systems, Numer. Math., 67, 1-19 (1994) · Zbl 0797.65023 · doi:10.1007/s002110050015
[5] Brezinski, C.; Redivo-Zaglia, M., The PageRank vector: properties, computation, approximation, and acceleration, SIAM J. Matrix Anal. Appl., 28, 551-575 (2006) · Zbl 1116.65042 · doi:10.1137/050626612
[6] Brezinski, C.; Redivo-Zaglia, M.; Saad, Y., Shanks sequence transformations and Anderson acceleration, SIAM Rev., 60, 3, 646-669 (2018) · Zbl 1395.65001 · doi:10.1137/17M1120725
[7] Colton, D.; Kress, R., Inverse acoustic and electromagnetic scattering theory, Applied Mathematical Sciences, 2nd edn., vol. 93 (1998), Berlin: Springer, Berlin · Zbl 0893.35138 · doi:10.1007/978-3-662-03537-5
[8] Davis, TA; Hu, Y., The University of Florida sparse matrix collection, ACM Trans. Math. Softw., 38, 1, 1-25 (2011) · Zbl 1365.65123
[9] Duersch, JA; Shao, M.; Yang, C.; Gu, M., A robust and efficient implementation of lobpcg, SIAM J. Sci. Comput., 40, 5, C655-C676 (2018) · Zbl 1401.65038 · doi:10.1137/17M1129830
[10] Evans, C.; Pollock, S.; Rebholz, L.; Xiao, M., A proof that Anderson acceleration increases the convergence rate in linearly converging fixed point methods (but not in those converging quadratically), SIAM J. Numer. Anal., 58, 1, 788-810 (2020) · Zbl 1433.65102 · doi:10.1137/19M1245384
[11] Fang, H.; Saad, Y., Two classes of multisecant methods for nonlinear acceleration, Numer. Linear Algebra Appl., 16, 3, 197-221 (2009) · Zbl 1224.65134 · doi:10.1002/nla.617
[12] Golub, GH; Greif, C., An Arnoldi-type algorithm for computing page rank, BIT Numer. Math., 46, 759-771 (2006) · Zbl 1105.65034 · doi:10.1007/s10543-006-0091-y
[13] Golub, GH; Van Loan, CF, Matrix Computations (2013), Baltimore: The Johns Hopkins University Press, Baltimore · Zbl 1268.65037
[14] Golub, GH; Ye, Q., An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems, SIAM J. Sci. Comput., 24, 1, 312-334 (2002) · Zbl 1016.65017 · doi:10.1137/S1064827500382579
[15] Haveliwala, T.H., Kamvar, S.D., Klein, D., Manning, C.D., Golub, G.H.: Computing PageRank using power extrapolation. http://www-sccm.stanford.edu/nf-publications-tech.html. Technical report SCCM03-02, Stanford University, Stanford, CA (2003)
[16] Hecht, F., New development in freefem++, J. Numer. Math., 20, 3-4, 251-265 (2012) · Zbl 1266.68090 · doi:10.1515/jnum-2012-0013
[17] Hu, QY; Wen, C.; Huang, TZ; Shen, ZL; Gu, XM, A variant of the Power-Arnoldi algorithm for computing PageRank, J. Comput. Appl. Math., 381, 113034 (2021) · Zbl 1452.65068 · doi:10.1016/j.cam.2020.113034
[18] Ipsen, ICF, Computing an eigenvector with inverse iteration, SIAM Rev., 39, 2, 254-291 (1997) · Zbl 0874.65029 · doi:10.1137/S0036144596300773
[19] Kamvar, S., Numerical algorithms for personalized search in self-organizing information networks (2010), Princeton: Princeton University Press, Princeton · Zbl 1211.68004 · doi:10.1515/9781400837069
[20] Kamvar, S.D., Haveliwala, T.H., Manning, C.D., Golub, G.H.: Extrapolation methods for accelerating pagerank computations. In: Proceedings of the twelfth international world wide web conference (2003)
[21] Kelley, C., Numerical methods for nonlinear equations, Acta Numer., 27, 207-287 (2018) · Zbl 1429.65108 · doi:10.1017/S0962492917000113
[22] Knyazev, AV, Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method, SIAM J. Sci. Comput., 23, 2, 517-541 (2001) · Zbl 0992.65028 · doi:10.1137/S1064827500366124
[23] Pollock, S., Rebholz, L.G.: Anderson acceleration for contractive and noncontractive operators. IMA J. Numer. Anal. (2020)
[24] Polyak, BT, Some methods of speeding up the convergence of iteration methods, USSR Comput. Math. Math. Phys., 45, 1-17 (1964) · Zbl 0147.35301 · doi:10.1016/0041-5553(64)90137-5
[25] Quillen, P.; Ye, Q., A block inverse-free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems, J. Comput. Appl. Math., 233, 5, 1298-1313 (2010) · Zbl 1186.65044 · doi:10.1016/j.cam.2008.10.071
[26] Sa, CD; He, B.; Mitliagkas, I.; Ré, C.; Xu, P., Accelerated stochastic power iteration, Proc. Mach. Learn. Res., 84, 58-67 (2019)
[27] Sidi, A.: Approximation of largest eigenpairs of matrices and applications to Pagerank computation. http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2004/CS/CS-2004-16
[28] Sidi, A., Vector extrapolation methods with applications to solution of large systems of equations and to PageRank computations, Comput. Math. Appl., 56, 1-24 (2008) · Zbl 1145.65312 · doi:10.1016/j.camwa.2007.11.027
[29] Toth, A.; Kelley, CT, Convergence analysis for Anderson acceleration, SIAM J. Numer. Anal., 53, 2, 805-819 (2015) · Zbl 1312.65083 · doi:10.1137/130919398
[30] Walker, HF; Ni, P., Anderson acceleration for fixed-point iterations, SIAM J. Numer. Anal., 49, 4, 1715-1735 (2011) · Zbl 1254.65067 · doi:10.1137/10078356X
[31] Wilkinson, JH, The algebraic eigenvalue problem (1965), Oxford: Clarendon Press, Oxford · Zbl 0258.65037
[32] Wynn, P., Acceleration techniques for iterated vector and matrix problems, Math. Comput., 16, 79, 301-322 (1962) · Zbl 0105.10302 · doi:10.1090/S0025-5718-1962-0145647-X
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.