The QR algorithm which computes the Schur decomposition of a matrix is by  far the most important approach for solving dense nonsymmetric eigenvalue  problems. Recently a novel parallel QR algorithm has been developed by
 incorporating some modern techniques such as small-bulge multishift and  aggressive early deflation (AED). The novel parallel approach significantly outperforms the pipelined QR algorithm in ScaLAPACK v1.8.0 and earlier versions. But AED becomes a computational bottleneck in the new parallel QR  algorithm. We develop multilevel AED algorithms which indeed decrease the total amount of communications and further improve the performance of the  parallel QR algorithm. The improved version is now available as a part of ScaLAPACK version 2.0. Both performance models and numerical experiments demonstrate the efficiency of the new approach.