时间戳

首页 > 解决方案 > 如何优化三对角矩阵的特征值/向量计算

python - 如何优化三对角矩阵的特征值/向量计算

问题描述

我正在尝试优化我对三对角矩阵的特征值/向量的计算。我的代码目前运行大约需要 30 秒，我需要它运行得更快，大约 1 秒。我目前正在使用scipy.sparse.linalg.eigsh方法来查找特征值/向量，但我相信应该有其他更快的方法。我将在下面发布我的代码，以便更容易看到我想要做什么。非常欢迎任何建议，如果有任何不清楚的地方，请告诉我。

    H = (dx**-2)*diags([-1, 2, -1], [-1, 0, 1], shape=(N, N))
    H = sp.lil_matrix(H)
    H[0,0]=0.5*H[0,0]
    H[N-1,N-1]=0.5*H[N-1,N-1]
    lam, phi = eigsh(H, 400, which="SM")

标签： pythonnumpyscipy

解决方案

您不太可能找到一种简单的方法来将此计算速度提高 30 倍。从这篇文章的时间安排中可以看出，即使是 Google 令人印象深刻的优化jax库也只能比scipy. 由于 SVD 等价eigsh于对称矩阵，我们可以预期加速比eigsh充其量是大致相同的。

所以即使是谷歌也无法加快这个计算速度，至少以传统方式是这样。

然而，对于非常大的稀疏矩阵，有专门的随机算法可以在适当的情况下以更大的因子加速处理。其中一个有一个sklearn实现：sklearn.utils.extmath.randomized_svd。（我相信是基于这里描述的算法，也可能和sklearn.decomposition.TruncatedSVDwhen一样algorithm='randomized'。）

这是您的示例的略微修改版本，展示了如何使用它：

from scipy.sparse import diags, lil_matrix
from scipy.sparse.linalg import eigsh

from sklearn.utils.extmath import randomized_svd

N = 3200
k = 400
dx = 1.0

H = (dx**-2)*diags([-1, 2, -1], [-1, 0, 1], shape=(N, N))
H = lil_matrix(H)
H[0, 0] = 0.5*H[0, 0]
H[N-1, N-1] = 0.5*H[N-1, N-1]
# lam, phi = eigsh(H, k, which="SM")

U, s, V = randomized_svd(H, k)

在这里，s包含奇异值（在此等同于特征值），U并且V包含奇异向量（在此等同于特征向量）。理论上，ifH是一个对称矩阵，U应该与 相同V.T。我没有发现这个例子的情况，这让我有点困惑......但我还是会继续发布这个，因为这实际上会在大约一秒钟内运行，所以可能是一个解决方案为你。

但是，还有一个更大的警告。您要传递which="SM"给eigsh，据我了解，这意味着您要的是 400 个最小的特征值。这真的是你想要的吗？在我知道的几乎所有应用程序中，您都需要 400 个最大的特征值。如果实际上您确实想要 400 个最小的特征值，那么这将行不通，因为它依赖于这样一个事实，即使用随机矩阵投影更容易哄出最大的特征值。

结果是，您将需要对此进行测试以查看它是否确实提供了您可以使用的结果。但这是一个有趣的可能解决方案，考虑到你到目前为止所说的关于你的问题的内容。

推荐阅读