How long does it take to compute the eigenvalues of a random, symmetric matrix?
How long does it take to compute the eigenvalues of a random, symmetric matrix?
复制标题
计算随机对称矩阵的特征值需要多长时间？
DOI：
10.14288/1.0319078
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Govind Menon
中科院分区：
文献类型：
--
作者：
C. Pfrang;P. Deift;Govind Menon
我们介绍了一项关于QR算法的性能（有或没有移位）和随机对称矩阵的TODA算法的实证研究的结果。随机矩阵是从六个合奏中选择的，其中四个位于Wigner类中。对于所有三种算法，我们都会观察到Wigner类内随机矩阵的通用时间统计的一种普遍性。对于这些合奏，发现归一化通气时间的经验分布被发现塌陷在仅取决于算法的曲线上，但不依赖于矩阵的大小或放气公差，前提是矩阵大小足够大（请参见图4，图7和图7和图10）。对于具有威尔金森转移的QR算法，观察到的普遍性甚至更强，并且包括某些非构造集合。我们的实验还提供了随着变化加速收敛的定量统计图。
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.