2012/03/21 by Christian W. Pfrang, Pfrang, Christian W., Percy Deift +3
Mathematics · #60B20 #65F15 #65Y20 #82B44 #Advanced Algebra and Geometry #Advanced Combinatorial Mathematics #Exactly Solvable and Integrable Systems (nlin.SI) #FOS: Mathematics #FOS: Physical sciences #Numerical Analysis (math.NA) #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.1203.4635
openalex publication_date 2012/03/21 · openalex created_date 2024/04/10 · openalex updated_date 2026/07/28
We present the results of an empirical study of the performance of the QR algorithm (with and without shifts) and the Toda algorithm on random symmetric matrices. The random matrices are chosen from six ensembles, four of which lie in the Wigner class. For all three algorithms, we observe a form of universality for the deflation time statistics for random matrices within the Wigner class. For these ensembles, the empirical distribution of a normalized deflation time is found to collapse onto a curve that depends only on the algorithm, but not on the matrix size or deflation tolerance provided the matrix size is large enough (see Figure 4, Figure 7 and Figure 10). For the QR algorithm with the Wilkinson shift, the observed universality is even stronger and includes certain non-Wigner ensembles. Our experiments also provide a quantitative statistical picture of the accelerated convergence with shifts.