Parallel Homotopy Algorithm for the Symmetric Tridiagonal Eigenvalue Problem
Let \((\lambda_ i(1),x_ i(1))\) denote the eigenpairs of a real \(n\times n\) symmetric tridiagonal matrix \(\mathbf A\). Given a simpler (possibly diagonal) matrix \(\mathbf D\) whose eigenpairs \((\lambda_ i(0),x_ i(0))\) are known, the first author and \textit{N. H. Rhee} [Numer. Math. 55, No. 3, 265-280 (1989; Zbl 0653.65025)] have shown how to construct smooth, disjoint homotopy curves \((\lambda_ i(t),x_ i(t))\) connecting the eigenpairs of \(\mathbf D\) with those of \(\mathbf A\). The algorithm of Li and Rhee suffers from instability when the eigenvalues of \(\mathbf A\) are not well-separated, and it is the purpose of this paper to present an improvement for that case as well as to present a natural parallel implementation with minimal interprocessor communication. Instability in Li and Rhee's algorithm occurs when the eigenvalues cluster together. The authors present here a method for detection of clusters through use of Sturm sequences. When a cluster is detected, subspace iteration is used to stabilize Li and Rhee's method. The resulting algorithm does not slow down in the presence of clusters. Parallel implementation of the algorithm on an NCUBE with \(p\) processors is accomplished by first constructing \(\mathbf D\) from tridiagonal blocks of \(\mathbf A\) of size \(n/p\). The eigenpairs of each block are computed using sequential algorithms on each processor and the resulting set of eigenpairs sorted. Starting from the sorted eigenpairs, each processor follows its own homotopy curves independently using the stabilized Li-Rhee algorithm. Numerical examples comparing the homotopy method with EISPACK routines IMTQL2 and also BISECT+TINVIT are presented. Surprisingly, the sequential homotopy method shows some advantage over the more traditional methods. The parallel homotopy method illustrates excellent performance compared with the other methods for large numbers of processors as well as excellent efficiency compared with sequential homotopy on a single processor.
- Applying parallel computer systems to solve symmetric tridiagonal eigenvalue problems
- A parallel iterative method for solving symmetric tridiagonal extreme eigenpair problems
- A parallel continuation algorithm for nonlinear eigenvalue problems
- Parallel implementation of semiempirical quantum methods for the Intel platforms
- The orthogonal Rayleigh quotient iteration (ORQI) method
- Generic movement of eigenvalues for equivariant self-adjoint matrices
- Parallel homotopy algorithm for symmetric large sparse eigenproblems
- Homotopy method for the numerical solution of the eigenvalue problem of self-adjoint partial differential operators
- Continuation methods for the computation of zeros of Szegő polynomials
- scientific article; zbMATH DE number 4092657 (Why is no real title available?)
- A PARALLEL ALGORITHM FOR HOUSEHOLDER'S TRID1AGONALIZATION OF A SYMMETRIC MATRIX
- Homotopy-Determinant Algorithm for Solving Nonsymmetric Eigenvalue Problems
- A Robust, Parallel Homotopy Algorithm for the Symmetric Tridiagonal Eigenproblem
- scientific article; zbMATH DE number 1330402 (Why is no real title available?)
- An Algorithm for Symmetric Tridiagonal Eigenproblems: Divide and Conquer with Homotopy Continuation
This page was built for publication: Parallel Homotopy Algorithm for the Symmetric Tridiagonal Eigenvalue Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4713426)
