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

如果一切都失败了,您可能必须尝试以下更有效的实现:MatlabSuite SparsePetSCEigenIntel MKL

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