时间戳

首页 > 解决方案 > scipy.sparse.linalg.eigsh中LM和移位反转模式之间违反直觉的速度差异？

sparse-matrix - scipy.sparse.linalg.eigsh中LM和移位反转模式之间违反直觉的速度差异？

问题描述

我正在尝试使用 scipy.sparse.linalg.eigsh 找到 Python 中稀疏 Hermitian 矩阵列表的最小（如最负数，而不是最低量级）几个特征值。矩阵约为 1000x1000，列表长度约为 500-2000。此外，我知道所有矩阵的特征值的上限和下限——分别称它们为eig_UB和eig_LB。

我试过两种方法：

  1. 使用 sigma= eig_LB的移位反转模式。
  2. 从每个矩阵的对角线中减去eig_UB（从而将最小的特征值转换为最大幅度的特征值），使用默认 eigsh 设置对生成的矩阵进行对角化（无移位反转模式并使用 which='LM'），然后将eig_UB添加到得到的特征值。

两种方法都有效且结果一致，但方法 1 的速度大约快 2-2.5 倍。这似乎违反直觉，因为（至少按照我对 eigsh 文档的理解）移位反转模式从对角线中减去 sigma，反转矩阵，然后找到特征值，而默认模式直接找到最大幅度的特征值。有谁知道什么可以解释性能差异？

另一条信息：我已经检查过，移位反转产生的矩阵（即，如果 M 是原始矩阵，则为 (M-sigma*identity)^(-1)）不再稀疏，这似乎就像它应该使找到它们的特征值需要更长的时间。

标签： sparse-matrixeigenvaluearpack

解决方案

这可能已经解决了。正如https://arxiv.org/pdf/1504.06768.pdf中所指出的，您实际上不需要反转移位的稀疏矩阵，然后在某些 Lanczos 类型的方法中重复应用它——您只需要重复求解一个逆问题 (M-sigma*identity)*v(n+1)=v(n) 生成向量序列 {v(n)}。对于 LU 分解后的稀疏矩阵，可以快速完成这个逆问题。

推荐阅读