2

我需要反转 apxp 对称带状粗麻布矩阵 H，它有 7 个对角线。p 可能非常高（=1000 或 10000）。

H^{-1} 可以被认为是带状的，因此，我不需要计算完整的逆矩阵，而是它的近似值。（例如，可以假设有 11 或 13 条对角线。）我正在寻找一种不意味着并行化的方法。

有没有可能在线性时间内用 R 构建这样的算法？ 

4

1 回答 1

1

据我所知，没有线性时间算法。但你并非完全没有希望：

  1. 您的矩阵并没有那么大，因此使用相对优化的实现对于p < 10K. 例如，密集的LU 分解最多需要O(p^3)，p = 1000，这可能需要不到一秒的时间。在实践中，稀疏矩阵的实现应该利用稀疏性获得更好的性能；
  2. 你真的，真的，真的需要计算逆吗？很多时候，显式计算逆可以通过求解等效线性系统来代替；使用迭代求解器（例如共轭梯度）等一些方法，求解线性系统的效率明显更高，因为源矩阵的稀疏模式得以保留，从而减少了工作量；在计算逆时，即使你知道用带状矩阵近似是可以的，仍然会有大量的填充（添加非零值）

综上所述，我建议您为您的矩阵试用R 矩阵包。尝试所有可用的签名并确保您安装了高性能的 BLAS 实现。还尝试重写您的调用以计算逆：

# e.g. rewrite...
A_inverse = solve(A)
x = y * A_inverse
# ... as
x = solve(A, y)

这对于您的目的可能更微妙，但是您应该能够做到这一点的可能性很大，正如包文档中所建议的那样： 

 solve(a, b, ...) ## *the* two-argument version, almost always preferred to
 solve(a)         ## the *rarely* needed one-argument version

如果一切都失败了，您可能必须尝试以下更有效的实现：Matlab、Suite Sparse、PetSC、Eigen或Intel MKL。

于 2016-08-11T09:19:31.870 回答