Name
Abstract | ||
|---|---|---|
The (sequential) algorithm of Multiple Relatively Robust Representations, MRRR, is a more efficient variant of inverse iteration that does not require reorthogonalization. It solves the eigenproblem of an unreduced symmetric tridiagonal matrix T ∈ Rn × n at O(n2) cost. The computed normalized eigenvectors are numerically orthogonal in the sense that the dot product between different vectors is O (n ε), where ε refers to the relative machine precision. This article describes the design of ScaLAPACK's parallel MRRR algorithm. One emphasis is on the critical role of the representation tree in achieving both adequate accuracy and parallel scalability. A second point concerns the favorable properties of this code: subset computation, the use of static memory, and scalability. Unlike ScaLAPACK's Divide & Conquer and QR, MRRR can compute subsets of eigenpairs at reduced cost. And in contrast to inverse iterations which can fail, it is guaranteed to produce a satisfactory answer while maintaining memory scalability. ParEig, the parallel MRRR algorithm for PLAPACK, uses dynamic memory allocation. This is avoided by our code at marginal additional cost. We also use a different representation tree criterion that allows for more accurate computation of the eigenvectors but can make parallelization more difficult. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1644001.1644002 | ACM Trans. Math. Softw. |
Keywords | Field | DocType |
dynamic memory allocation,numerical software,reduced cost,multiple relatively robust representations,inverse iteration,scalapack,parallel computation,memory scalability,symmetric eigenvalue problem,parallel mrrr algorithm,computed normalized eigenvectors,marginal additional cost,accurate computation,static memory,implementation,design,parallel scalability,parallel computer,eigenvectors,tridiagonal matrix | Tridiagonal matrix,Mathematical optimization,C dynamic memory allocation,Algorithm,Theoretical computer science,Machine epsilon,ScaLAPACK,Dot product,Mathematics,Eigenvalues and eigenvectors,Scalability,Inverse iteration | Journal |
Volume | Issue | ISSN |
37 | 1 | 0098-3500 |
Citations | PageRank | References |
11 | 0.69 | 19 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christof Vömel | 1 | 168 | 17.80 |