Sampling the eigenvalues of random orthogonal and unitary matrices (Q2020693)

The authors develop an efficient algorithm for sampling the eigenvalues of random matrices distributed according to the Haar measure over the orthogonal or unitary group. Their approach uses a technique of \textit{G. W. Stewart} [SIAM J. Numer. Anal. 17, 403--409 (1980; Zbl 0443.65027)] for sampling the upper Hessenberg form of Haar-distributed matrices, and an algorithm for computing the eigenvalues of an \(n\times n\) upper Hesenberg unitary or orthogonal matrix in \(O(n^2)\) flops. Using the unitary QR algorithm (a special case of a rootfinding algorithm of the second author and others [\textit{J. L. Aurentz} et al., SIAM J. Matrix Anal. Appl. 39, No. 3, 1245--1269 (2018; Zbl 1398.65056)]), their technique samples a factorization of the Hessenberg form and computes the eigenvalues with a core-chasing algorithm. The number of floating point operations required is quadratic in the order of the sampled matrix.