python - Scipy 稀疏反转或 spsolve 导致 UMFPACK_ERROR_OUT_OF_MEMORY

Question

我正在尝试反转一个大的 (150000,150000) 稀疏矩阵，如下所示:

import scipy as sp
import scipy.sparse.linalg as splu

#Bs is a large sparse matrix with shape=(150000,150000)

#calculating the sparse inverse
iBs=splu.inv(Bs)

导致以下错误消息:

Traceback (most recent call last):
    iBs=splu.inv(Bs)
  File "/usr/lib/python2.7/dist-packages/scipy/sparse/linalg/dsolve/linsolve.py", line 134, in spsolve
autoTranspose=True)
  File "/usr/lib/python2.7/dist-packages/scipy/sparse/linalg/dsolve/umfpack/umfpack.py", line 603, in linsolve
self.numeric(mtx)
  File "/usr/lib/python2.7/dist-packages/scipy/sparse/linalg/dsolve/umfpack/umfpack.py", line 450, in numeric
umfStatus[status]))
RuntimeError: <function umfpack_di_numeric at 0x7f2c76b1d320> failed with UMFPACK_ERROR_out_of_memory

我重新调整了程序以简单地求解线性微分方程组:

import numpy as np

N=Bs.shape[0]

I=np.ones(N)

M=splu.spsolve(Bs,I)

我又遇到了同样的错误

我在一台有 16 GB RAM 的机器上使用这段代码，然后将它移到一台有 32 GB RAM 的服务器上，但仍然无济于事。

有没有人遇到过这种情况？

Answer 1

首先让我说这个问题最好在http://scicomp.stackexchange.com上问那里有大量计算科学和数值线性代数方面的专家。

让我们从基础开始:永远不要反转稀疏矩阵，它完全没有意义。看这个discussion在 MATLAB Central 上，尤其是这个 comment蒂姆·戴维斯。

简而言之:没有用于对矩阵进行数值求逆的算法。每当您尝试对 NxN 矩阵的逆进行数值计算时，您实际上求解了 N 个线性系统，其中 N 个 rhs 向量对应于单位矩阵的列。

换句话说，当你计算

from scipy.sparse import eye
from scipy.sparse.linalg import (inv, spsolve)

N = Bs.shape[0]
iBs = inv(Bs)
iBs = spsolve(Bs, eye(N))

最后两个语句(inv(eye) 和 spsolve(Bs, eye(N)))是等价的。请注意单位矩阵 (eye(N)) 是 not ones 向量 (np.ones(N)) 因为你的问题是错误的假设。

这里的要点是，矩阵求逆在数值线性代数中很少有用:Ax = b 的解不是按 inv(A)*b 计算的，而是通过专门的算法计算的。

针对您的特定问题，对于大型稀疏方程组，没有黑盒 求解器。只有充分了解矩阵问题的结构和属性，您才能选择正确的求解器类别。矩阵的属性反过来又是您要解决的问题的结果。例如。当您通过 FEM 离散化椭圆 PDE 系统时，您最终会得到代数方程的对称正稀疏系统。了解问题的属性后，您就可以选择正确的解决策略。

在您的情况下，您正在尝试使用通用直接求解器，而不对方程重新排序。众所周知，这将在 spsolve 函数(应该是因式分解)的第一阶段生成破坏 iBs 矩阵稀疏性的填充。请。请注意，完整的 double 150000 x 150000 矩阵需要大约 167 GB 的内存。有很多技术可以重新排序方程以减少分解过程中的填充，但您没有提供足够的信息来给您一个明智的提示。

抱歉，您应该考虑在 http://scicomp.stackexchange.com 上重新表述您的问题清楚地说明您要解决的问题，以便提供有关矩阵结构和属性的线索。