Efficient Robust Multi-Shift Triangular Solves

Abstract. Eigenvectors for a matrix in real Schur form can be computed by solving many quasi-triangular linear systems of the form (TλI)x=b. If eigenvalues are clustered, then overflow may occur. Previously proposed algorithms update off-diagonal blocks with xGEMM, but the diagonal blocks may become a bottleneck. Our improvements include (1) minimal scaling behaviour, (2) underflow protection of scaling factors, (3) efficient overflow protection logic. We present performance results for KNL and Broadwell.


  • Angelika Schwarz, Umeå University, Sweden, angies@cs.umu.se
  • Mirko Myllykoski, Umeå University, Sweden, mirkom@cs.umu.se
  • Carl Christian Kjelgaard Mikkelsen, Umeå University, Sweden, spock@cs.umu.se
  • Lars Karlsson, Umeå University, Sweden, larsk@cs.umu.se