Complexity of path-following methods for the eigenvalue problem

DOI10.1007/S10208-013-9185-5MaRDI QIDQ404275zbMATH OpenOpenAlexFDO

Publication date 4 September 2014

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.2828

approximate zero basin of attraction complexity condition metric condition number theorem eigenvalue problem homotopy method ill-posed problem multihomogeneous polynomial systems Newton method path-following method predictor-corrector strategy Smale \(\gamma\)-theorem

Mathematics Subject Classification ID

General theory of numerical methods in complex analysis (potential theory, etc.) (65E05) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20) Complexity and performance of numerical algorithms (65Y20)

Abstract: A unitarily invariant projective framework is introduced to analyze the complexity of path-following methods for the eigenvalue problem. A condition number, and its relation to the distance to ill-posedness, is given. A Newton map appropriate for this context is defined, and a version of Smale's

g a m m a

-Theorem is proven. The main result of this paper bounds the complexity of path-following methods in terms of the length of the path in the condition metric.

Review text

The article is devoted to analyze the complexity of path-following (or homotopy) methods for solving the eigenvalue problem \[ (\lambda I_n-A)v=0,\quad v\not=0. \] Here \(A\in\mathbb{K}^{n\times n}\), \(I_n\in\mathbb{K}^{n\times n}\) is the identity matrix, \(v\in\mathbb{K}^n\) and \(\lambda\in\mathbb{K}\), where \(\mathbb{K}\) denotes the set of real numbers \(\mathbb{R}\) or complex numbers \(\mathbb{C}\). Usually, the eigenvalue problem is solved by means of QR methods or Krylov subspace methods (see, e.g. [\textit{D. S. Watkins}, The matrix eigenvalue problem. GR and Krylov subspace methods. Philadelphia, PA: Society for Industrial and Applied Mathematics (2007; Zbl 1142.65038)]). It is well known that these algorithms are stable. However, their complexity is not well-understood. On the other hand, there is a number of articles discussing homotopy methods for solving the eigenvalue problem (see, e.g. [\textit{S. H. Lui} et al., SIAM J. Matrix Anal. Appl. 18, No. 2, 312--333 (1997; Zbl 0872.65035)]). Nevertheless, determining the complexity of homotopy methods for eigenvalue problems remains an open problem. In the paper under review, homotopy methods for the eigenvalue problem are analyzed. More precisely, for a eigentriple \((A,\lambda,v)\), a path of problems \[ (\lambda(t) I_n-A(t))v(t)=0,\quad v(t)\not=0,\quad 0\leq t\leq 1, \] is considered. Starting at a known triple \((A(0),\lambda(0),v(0))\), this path is ``followed until an approximation of the output triple \((A(1),\lambda(1),v(1))=(A,\lambda,v)\) is obtained. For this purpose, given a mesh \(0=t_0<t_1<\cdots<t_K=1\), a finite number of triples \(\{(A_k,\lambda_k,v_k):0\leq k\leq K\}\) is computed, where \(A_k:=A(t_k)\) and each \((\lambda_k,v_k)\) is an approximation of \((\lambda(t_k),v(t_k))\) for \(0\leq k\leq K\). The number \(K\) of steps is related to a geometric invariant associated with the solution variety \[ \mathcal{V}:=\{(A,\lambda,v)\in\mathbb{P}(\mathbb{K}^n\times \mathbb{K})\times\mathbb{P}(\mathbb{K}^n):(\lambda I_n-A)v=0 \}, \] where \(\mathbb{P}(\mathbb{E})\) denotes the projective space associated with the vector space \(\mathbb{E}\). To follow a path \(\Gamma(t):=(A(t),\lambda(t),v(t))\) in \(\mathcal{V}\), a finite sequence \(\{(A_k,\lambda_k,v_k): 0\leq k\leq K\}\) as above is computed, using the predictor-corrector strategy defined by \[ (\lambda_{k+1},v_{k+1}):=N_{A(t_{k+1})}(\lambda_k,v_k), \] where \(N_A\) is the Newton operator associated with the map \(F_A(\lambda,v):=(\lambda I_n-A)v\). Let \(\mathcal{W}\subset \mathcal{V}\) be the set of well-posed problems, namely the set of triples \((A,\lambda,v)\) such that \(\lambda\) is a simple eigenvalue of \(A\). Then \(\Sigma':=\mathcal{V} \setminus\mathcal{W}\) is the set of ill-posed problems. A condition number \(\mu(A,\lambda,v)\) is associated to any \((A,\lambda,v)\in\mathcal{W}\): It is defined in terms of the norm of the differential of the local inverse of the projection \(\pi:\mathcal{V}\to \mathbb{P}(\mathbb{K}^{n\times n})\). The first main result of the article is a condition number theorem, which relates the condition number \(\mu\) to the distance to the variety of ill-posed problems. The second main result is a version of the Smale \(\gamma\)-theorem (see [\textit{L. Blum} et al., Complexity and real computation. Foreword by Richard M. Karp. New York, NY: Springer (1997; Zbl 0948.68068)]), which gives an upper bound on the size of the basin of attraction of the Newton method. In the paper under review, an approximate solution theorem is proved, where such a bound for a triple \((A,\lambda, v)\) is expressed as the reciprocal of the condition number \(\mu(A,\lambda, v)\), up to a small constant. Finally, the third main result, called the main result by the author, is an upper bound on the number \(K\) of steps necessary to follow a path \(\Gamma(t)=(A(t),\lambda(t),v(t))\) in \(\mathcal{W}\) in the sense above. It asserts that \[ K\leq C\ell_\mu(\Gamma)+1, \] where \(C\) is a (small) universal constant and \(\ell_\mu(\Gamma)\) is the condition length of \(\Gamma\), namely the length of \(\Gamma\) measured in the Riemannian structure of \(\mathcal{W}\) defined by the condition number. The corresponding metric is called the condition metric [\textit{M. Shub}, Found. Comput. Math. 9, No. 2, 171--178 (2009; Zbl 1175.65060)].

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Complexity of path-following methods for the eigenvalue problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q404275)