A Framework for the $MR^3$ Algorithm: Theory and Implementation
Paul R. Willems, Bruno Lang · SIAM Journal on Scientific Computing · 2013
This paper provides a streamlined and modular presentation of the $\mbox{MR}^{3}$ algorithm for computing selected eigenpairs of symmetric tridiagonal matrices, thus disentangling the principles driving $\mbox{MR}^{3}$ and the (recursive) “core” algorithm from the specific (e.g., twisted) decompositions used to represent the matrices at different recursion depths and from the (dqds) transformations converting between them. Our approach allows a modular full proof for the correctness of the $\mbox{MR}^{3}$ algorithm. This proof is based on five requirements concerning the interplay between the core algorithm and its subcomponents. These requirements can also guide in implementing the algorithm, because they expose quantities that can and should be monitored at runtime. Our new implementation XMR, which is based on the above analysis, is described and compared to STEMR from Lapack 3.2.2. Numerical experiments comparing the robustness and performance of both implementations are given.