  The QR algorithm is one of the three phases in the process of computing the
eigenvalues and the eigenvectors of a dense nonsymmetric matrix. This paper
describes a task-based QR algorithm for reducing an upper Hessenberg matrix to
real Schur form. The task-based algorithm also supports generalized eigenvalue
problems (QZ algorithm) but this paper concentrates on the standard case. The
task-based algorithm adopts previous algorithmic improvements, such as
tightly-coupled multi-shifts and Aggressive Early Deflation (AED), and also
incorporates several new ideas that significantly improve the performance. This
includes, but is not limited to, the elimination of several synchronization
points, the dynamic merging of previously separate computational steps, the
shortening and the prioritization of the critical path, and experimental GPU
support. The task-based implementation is demonstrated to be multiple times
faster than multi-threaded LAPACK and ScaLAPACK in both single-node and
multi-node configurations on two different machines based on Intel and AMD
CPUs. The implementation is built on top of the StarPU runtime system and is
part of the open-source StarNEig library.
