Complexity of path-following methods for the eigenvalue problem (Q404275): Difference between revisions

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)].