@Article{VanZee:2014:RTB,
  author =       "Van Zee, Field G.  and Robert A. van de Geijn and 
                  Gregorio Quintana-Ort\'{i}",
  title  =       "Restructuring the Tridiagonal and Bidiagonal QR Algorithms for
                  Performance",
  journal =      "{ACM} Transactions on Mathematical Software",
  accepted =     "2 October 2013",
  volume =       40,
  number =       3,
  year    =      2014,
  month   =      apr,
  pages =        "18:1--18:34",
  url =          "http://doi.acm.org/10.1145/2535371",
  abstract =     "
                  We show how both the tridiagonal and bidiagonal QR
                  algorithms can be restructured so that they become rich
                  in operations that can achieve near-peak performance on
                  a modern processor. The key is a novel, cache-friendly
                  algorithm for applying multiple sets of Givens rotations
                  to the eigenvector/singular vector matrix. This algorithm
                  is then implemented with optimizations that (1) leverage
                  vector instruction units to increase floating-point
                  throughput, and (2) fuse multiple rotations to decrease
                  the total number of memory operations. We demonstrate
                  the merits of these new QR algorithms for computing the
                  Hermitian eigenvalue decomposition (EVD) and singular
                  value decomposition (SVD) of dense matrices when all 
                  eigenvectors/singular vectors are computed. The approach yields
                  vastly improved performance relative to the traditional
                  QR algorithms for these problems and is competitive with
                  two commonly used alternatives---Cuppen’s Divide and
                  Conquer algorithm and the Method of Multiple Relatively
                  Robust Representations---while inheriting the more
                  modest $O(n)$ workspace requirements of the original QR
                  algorithms. Since the computations performed by the
                  restructured algorithms remain essentially identical to
                  those performed by the original methods, robust numerical
                  properties are preserved.",
}