当我试图计算一个非常大的图的邻接矩阵的特征值时，我得到的，可以被描述为垃圾。特别地，由于图是四正则的，所以特征值应该在$[-4，4]$中，但它们显然不是。我使用了Matlab（通过MATLink），也遇到了同样的问题，所以这显然是一个超越数学的问题。问题是：处理它的最佳方法是什么？我确信MATLAB和Mathematica使用了古老的EISPAK代码，因此可能会有更新/更好的
稠密矩阵的特征值方法通常首先将矩阵转换为Hessenberg形式，这将导致三对角矩阵。之后，应用移位QR算法的一些变体，如凸起追逐，迭代减少非对角线元素，在这些元素变得足够小的位置拆分矩阵。
但我想提请大家注意的是，第一步及其破坏结构的后果。例如，不能保证三对角矩阵仍然是对称的。这也适用于所有进一步的步骤，如果它们不是针对对称矩阵明确定制的。
但这里更相关的是，这一步骤忽略了图的所有连通性或非连通性，并可能在转换反转时连接所有节点，尽管权重很小。
图的每个m连通分量给出一个特征值4，其特征向量在分量的节点处为1，其他为0。这些本征空间的所有维度都是1。矩阵的任何小扰动首先去除该分离并将它们连接到维度为m的本征空间中，然后将其作为多重本征值进行扰动。然后，这可以在半径为4*(1e-15)^(1/m)的复平面中围绕原始值4产生近似规则的m尖星。即使对于中等大小的CCD_ 5，这也给出了与真实特征值的显著偏差。
因此，总之，使用稀疏方法，因为这些方法通常会首先将矩阵重新排序为尽可能对角，这应该根据分量给出块对角结构。然后，特征值方法将自动分别对所有块进行处理，避免了上述混合。如果可能的话，使用对称矩阵的方法，或者设置相应的选项/标志（如果存在）。