invariant subspace; Grassmann manifold; cubic convergence; symmetric eigenproblem; inverse iteration; Rayleigh quotient; Newton method; global convergence
Abstract :
[en] We propose a Newton-like iteration that evolves on the set of fixed dimensional subspaces of R-n and converges locally cubically to the invariant subspaces of a symmetric matrix. This iteration is compared in terms of numerical cost and global behavior with three other methods that display the same property of cubic convergence. Moreover, we consider heuristics that greatly improve the global behavior of the iterations.
Disciplines :
Mathematics
Author, co-author :
Absil, P.-A.
Sepulchre, Rodolphe ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation
Van Dooren, P.
Mahony, R.
Language :
English
Title :
Cubically convergent iterations for invariant subspace computation
Publication date :
2004
Journal title :
SIAM Journal on Matrix Analysis and Applications
ISSN :
0895-4798
eISSN :
1095-7162
Publisher :
Siam Publications, Philadelphia, United States - Pennsylvania
[AbsOS] P.-A. ABSIL, Invariant Subspace Computation: A Geometric Approach, Ph.D. thesis, Faculté des Sciences Appliquées, Université de Liège, Liège, Belgium, 2003.
[ADM+02] R. L. ADLER, J.-P. DEDIEU, J. Y. MARGULIES, M. MARTENS, AND M. SHUB, Newton's method on Riemannian manifolds and a geometric model for the human spine, IMA J. Numer. Anal., 22 (2002), pp. 359-390.
[AH02] P.-A. ABSIL, U. HELMKE AND K. HÜPER, Well-posedness and regularity properties of the Grassman-Rayleigh quotient iteration, Found. Comput. Math., submitted.
[AMS02] P.-A. ABSIL, R. MAHONY, AND R. SEPULCHRE, Riemannian geometry of Grassmann manifolds with a view on algorithmic computation, Acta Appl. Math., 80 (2004), pp. 199-220 (manuscript available from http://www.montefiore.ulg.ac. be/systems/Publi/Grass-geom.htm).
[AMSV02] P.-A. ABSIL, R. MAHONY, R. SEPULCHRE, AND P. VAN DOOREN, A Grassmann-Rayleigh quotient iteration for computing invariant subspaces, SIAM Rev., 44 (2002), pp. 57-73.
[BBM02a] K. BRAMAN, R. BYERS, AND R. MATHIAS, The multishift QR algorithm. Part I: Maintaining well-focused shifts and level 3 performance, SIAM J. Matrix Anal. Appl., 23 (2002), pp. 929-947.
[BBM02b] K. BRAMAN, R. BYERS, AND R. MATHIAS, The multishift QR algorithm. Part II: Aggressive early deflation, SIAM J. Matrix Anal. Appl., 23 (2002), pp. 948-973.
[BD89] Z. BAI AND J. DEMMEL, On a block implementation of Hessenberg QR iteration, Intl. J. High Speed Comput., 1 (1989), pp. 97-112; also available online as LAPACK Working Note 8 from http://www.netlib.org/lapack/lawns/lawn08. ps and http://www.netlib.org/lapack/lawnspdf/lawn08.pdf.
[Bra03] J. BRANDTS, The Riccati algorithm for eigenvalues and invariant subspaces of matrices with inexpensive action, Linear Algebra Appl., 358 (2003), pp. 335-365.
[BS89] S. BATTERSON AND J. SMILLIE, The dynamics of Rayleigh quotient iteration, SIAM J. Numer. Anal., 26 (1989), pp. 624-636.
[Cha84] F. CHATELIN, Simultaneous Newton's iteration for the eigenproblem, Comput. Suppl., 5 (1984), pp. 67-74.
[Dem87] J. W. DEMMEL, Three methods for refining estimates of invariant subspaces, Computing, 38 (1987), pp. 43-57.
[DF01] L. DIECI AND M. J. FRIEDMAN, Continuation of invariant subspaces, Numer. Linear Algebra Appl., 8 (2001), pp. 317-327.
[DMW83] J. J. DONGARRA, C. B. MOLER, AND J. H. WILKINSON, Improving the accuracy of computed eigenvalues and eigenvectors, SIAM J. Numer. Anal., 20 (1983), pp. 23-45.
[DP03] I. S. DHILLON AND B. N. PARLETT, Orthogonal eigenvectors and relative gaps, SIAM J. Matrix Anal. Appl., 25 (2004), pp. 858-899.
[DS83] J. E. DENNIS AND R. B. SCHNABEL, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice Hall Ser. Comput. Math., Prentice Hall, Englewood Cliffs, NJ, 1983.
[DS00] J.-P. DEDIEU AND M. SHUB, Multihomogeneous Newton method, Math. Comp., 69 (2000), pp. 1071-1098.
[EAS98] A. EDELMAN, T. A. ARIAS, AND S. T. SMITH, The geometry of algorithms with orthogonality constraints, SIAM J. Matrix Anal. Appl., 20 (1998), pp. 303-353.
[EW96] S. EISENSTAT AND H. WALKER, Choosing the forcing terms in an inexact Newton method, SIAM J. Sci. Comput., 17 (1996), pp. 16-32.
[Fat98] J.-L. FATTEBERT, A block Rayleigh quotient iteration with local quadratic convergence, Electron. Trans. Numer. Anal., 7 (1998), pp. 56-74.
[FGP94] J. FERRER, M. I. GARCÍA, AND F. PUERTA, Differentiate families of subspaces, Linear Algebra Appl., 199 (1994), pp. 229-252.
[FSV98] D. R. FOKKEMA, G. L. G. SLEIJPEN, AND H. A. VAN DER VORST, Accelerated inexact Newton schemes for large systems of nonlinear equations, SIAM J. Sci. Comput., 19 (1998), pp. 657-674.
[GV96] G. H. GOLUB AND C. F. VAN LOAN, Matrix Computations, 3rd ed., The Johns Hopkins University Press, Baltimore, MD, 1996.
[HM94] U. HELMKE AND J. B. MOORE, Optimization and Dynamical Systems, Springer-Verlag, London, 1994.
[Ips97] I. C. F. IPSEN, Computing an eigenvector with inverse iteration, SIAM Rev., 39 (1997), pp. 254-291.
[JS01] Z. JIA AND G. W. STEWART, An analysis of the Rayleigh-Ritz method for approximating eigenspaces, Math. Comp., 70 (2001), pp. 637-647.
[Kny01] A. V. KNYAZEV, Toward the optimal preconditioned eigensolver: locally optimal block preconditioned conjugate gradient method, SIAM J. Sci. Comput., 23 (2001), pp. 517-541.
[LE02] E. LUNDSTRÖM AND L. ELDÉN, Adaptive eigenvalue computations using Newton's method on the Grassmann manifold, SIAM J. Matrix Anal. Appl., 23 (2002), pp. 819-839.
[LST98] R. LÖSCHE, H. SCHWETLICK, AND G. TIMMERMAN, A modified block Newton iteration for approximating an invariant subspace of a symmetric matrix, Linear Algebra Appl., 275/276 (1998), pp. 381-400.
[MA03] R. MAHONY AND P.-A. ABSIL, The continuous-time Rayleigh quotient flow on the sphere, Linear Algebra Appl., 368 (2003), pp. 343-357.
[Not02] Y. NOTAY, Combination of Jacobi-Davidson and conjugate gradients for the partial symmetric eigenproblem, Numer. Linear Algebra Appl., 9 (2002), pp. 21-44.
[Not03] Y. NOTAY, Convergence analysis of inexact Rayleigh quotient iteration, SIAM J. Matrix Anal. Appl., 24 (2003), pp. 627-644.
[NW99] J. NOCEDAL AND S. WRIGHT, Numerical optimization, Springer Ser. Oper. Res., Springer-Verlag, New York, 1999.
[Par80] B. N. PARLETT, The Symmetric Eigenvalue Problem, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1980; republished by SIAM, Philadelphia, 1998.
[PK69] B. N. PARLETT AND W. KAHAN, On the convergence of a practical QR algorithm, in Information Processing 68 (Proc. IFIP Congress, Edinburgh, 1968), Vol. 1: Mathematics, Software, North-Holland, Amsterdam, 1969, pp. 114-118.
[PP73] B. N. PARLETT AND W. G. POOLE, A geometric theory for the QR, LU and Power Iteration, SIAM J. Numer. Anal., 10 (1973), pp. 389-412.
[PS95] R. D. PANTAZIS AND D. B. SZYLD, Regions of convergence of the Rayleigh quotient iteration method, Numer. Linear Algebra Appl., 2 (1995), pp. 251-269.
[PW79] G. PETERS AND J. H. WILKINSON, Inverse iteration, ill-conditioned equations and Newton's method, SIAM Rev., 21 (1979), pp. 339-360.
[PW94] C. C. PAIGE AND M. WEI, History and generality of the CS decomposition, Linear Algebra Appl., 208/209 (1994), pp. 303-326.
[RR02] A. C. M. RAN AND L. RODMAN, A class of robustness problems in matrix analysis, in Interpolation Theory, Systems Theory and Related Topics, The Harry Dym Anniversary Volume, D. Alpay, I. Gohberg, and V. Vinnikov, eds., Oper. Theory Adv. Appl. 134, Birkhäuser, Basel, 2002, pp. 337-383.
[SE02] V. SIMONCINI AND L. ELDÉN, Inexact Rayleigh quotient-type methods for eigenvalue computations, BIT, 42 (2002), pp. 159-182.
[Shu86] M. SHUB, Some remarks on dynamical systems and numerical analysis, in Proceedings VII ELAM, L. Lara-Carrero and J. Lewowicz, eds., Equinoccio, U. Simón Bolívar, Caracas, Venezuela, 1986, pp. 69-91.
[Smi94] S. T. SMITH, Optimization techniques on Riemannian manifolds, in Hamiltonian and Gradient Flows, Algorithms and Control, A. Bloch, ed., Fields Inst. Commun. 3, AMS, Providence, RI, 1994, pp. 113-136.
[Smi97] P. SMIT, Numerical Analysis of Eigenvalue Algorithms Based on Subspace Iterations, Ph.D. thesis, CentER, Tilburg University, Tilburg, The Netherlands, 1997.
[Ste73] G. W. STEWART, Error and perturbation bounds for subspaces associated with certain eigenvalue problems, SIAM Rev., 15 (1973), pp. 727-764.
[SV96] G. L. G. SLEIJPEN AND H. A. VAN DER VORST, A Jacobi-Davidson iteration method for linear eigenvalue problems, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 401-425.
[Wat82] D. S. WATKINS, Understanding the QR algorithm, SIAM Rev., 24 (1982), pp. 427-440.
[WE91] D. S. WATKINS AND L. ELSNER, Convergence of algorithms of decomposition type for the eigenvalue problem, Linear Algebra Appl., 143 (1991), pp. 19-47.
