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

From MaRDI portal
Importer (talk | contribs)
Changed an Item
ReferenceBot (talk | contribs)
Changed an Item
Property / cites work
 
Property / cites work: Smale's fundamental theorem of algebra reconsidered / rank
 
Normal rank
Property / cites work
 
Property / cites work: Rayleigh quotient iteration fails for nonsymmetric matrices / rank
 
Normal rank
Property / cites work
 
Property / cites work: Rayleigh Quotient Iteration for Nonsymmetric Matrices / rank
 
Normal rank
Property / cites work
 
Property / cites work: A continuation method to solve polynomial systems and its complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: Convexity Properties of the Condition Number / rank
 
Normal rank
Property / cites work
 
Property / cites work: Convexity Properties of the Condition Number II / rank
 
Normal rank
Property / cites work
 
Property / cites work: Smale’s 17th problem: Average polynomial time to compute affine and projective solutions / rank
 
Normal rank
Property / cites work
 
Property / cites work: The complexity and geometry of numerically solving polynomial systems. / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complexity of Bezout's theorem. VII: Distance estimates in the condition metric / rank
 
Normal rank
Property / cites work
 
Property / cites work: COMPLEXITY AND REAL COMPUTATION: A MANIFESTO / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fast computation of zeros of polynomial systems with bounded degree under finite-precision / rank
 
Normal rank
Property / cites work
 
Property / cites work: On a problem posed by Steve Smale / rank
 
Normal rank
Property / cites work
 
Property / cites work: Heights of varieties in multiprojective spaces and arithmetic Nullstellensatze / rank
 
Normal rank
Property / cites work
 
Property / cites work: A simple application of the homotopy method to symmetric eigenvalue problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fixed points, zeros and Newton's method / rank
 
Normal rank
Property / cites work
 
Property / cites work: Adaptive step-size selection for homotopy methods to solve polynomial equations / rank
 
Normal rank
Property / cites work
 
Property / cites work: Multihomogeneous Newton methods / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some open problems in random matrix theory and the theory of integrable systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Probability That a Numerical Analysis Problem is Difficult / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3328651 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5689624 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4356576 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Homotopy method for generalized eigenvalue problems \(Ax=\lambda Bx\) / rank
 
Normal rank
Property / cites work
 
Property / cites work: Numerical Solution of a Class of Deficient Polynomial Systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Homotopy Method for the Large, Sparse, Real Nonsymmetric Eigenvalue Problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4128900 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimal and nearly optimal algorithms for approximating polynomial zeros / rank
 
Normal rank
Property / cites work
 
Property / cites work: How long does it take to compute the eigenvalues of a random symmetric matrix? / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the worst-case arithmetic complexity of approximating zeros of polynomials / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complexity of Bezout's Theorem I: Geometric Aspects / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complexity of Bezout’s Theorem IV: Probability of Success; Extensions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complexity of Bezout's theorem. V: Polynomial time / rank
 
Normal rank
Property / cites work
 
Property / cites work: Matrix Algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3998482 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4337625 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Matrix Eigenvalue Problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5674306 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Note on matrices with a very ill-conditioned eigenproblem / rank
 
Normal rank

Revision as of 23:32, 8 July 2024

scientific article
Language Label Description Also known as
English
Complexity of path-following methods for the eigenvalue problem
scientific article

    Statements

    Complexity of path-following methods for the eigenvalue problem (English)
    0 references
    0 references
    4 September 2014
    0 references
    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)].
    0 references
    eigenvalue problem
    0 references
    path-following method
    0 references
    multihomogeneous polynomial systems
    0 references
    approximate zero
    0 references
    condition metric
    0 references
    homotopy method
    0 references
    complexity
    0 references
    predictor-corrector strategy
    0 references
    condition number theorem
    0 references
    ill-posed problem
    0 references
    Smale \(\gamma\)-theorem
    0 references
    basin of attraction
    0 references
    Newton method
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references