计算科学 - 有效地解决低秩线性参数系统？ - 吾爱随笔录

计算科学线性求解器

2021-12-09 18:11:54

我有大量的系统形式：

$Ax=b_i$

解决大量此类问题 $b_i\;1\leq i \leq k$ 但是哪里 $A$ 是固定的（A 是等级 $p$ 一般——即非稀疏、非 PSD——矩阵）。

我可以使用 LU 分解单独解决它们（成本 $O(p^3)$ ) 但想知道是否有更有效的方法来获取所有 $k$ 解向量 $x^*_i$ 比解决这些 $k$ 系统独立？

的典型值范围 $p$ , $k$ 我正在考虑在 10-100 之间（通常，我期待 $k\approx p$ ）。

一个指向所提出的任何方法的 c++ 实现的指针也将不胜感激。

最好的祝福，

3个回答

首先，您需要对第一个方程组使用 LU 分解。这是一 $\Theta(p^3)$ 手术。但是由于您没有更改矩阵系数而仅更改 RHS 向量，因此您可以重用因子 L 和 U 来“解决”新系统 $\Theta(p^2)$ 操作。

算法：

如果你事先知道所有右手边，你可以将它们组合成一个矩阵并求解 $AX=B$ . 可以在代表最先进技术的 LAPACK 库中找到此例程（在 C 和 Fortran 中）。

如果 $k\gg p$ 计算逆矩阵然后将每个右手边与它相乘可能更有效（比使用 Paul 的标准处理方式）。这更好地向量化（和并行化），并且可以忽略计算逆时的小初始开销。与案例不同 $k\le p$ . 例如，如果 $k=p$ 那么算术运算的开销是 50%，矢量化的增益可能不足以弥补这一点。

如果 $k<p$ 那么可能值得使用通过记录 Krylov 子空间方法（例如 GMRES）的迭代而获得的“子空间回收”方法之一。如果 $k\approx p$ 或者 $k>p$ 我认为应该很简单地证明这些子空间回收方法不会有效。

其它你可能感兴趣的问题