计算科学 - 求解涉及矩阵乘法的 mxm 对称线性系统与 (n+m) x (n+m) 系统 - 吾爱随笔录

假设 $R$ 和 $D$ 是一个 $n \times m$ 和 $m \times m$ 矩阵。假使，假设 $m \ll n$ 然后 $D$ 是肯定的。我们想解决系统 $(R^T R + D) x = R^T b$ . 这涉及矩阵乘法 $R^T R$ 这是相当昂贵的， $O(m^2 n)$ 在最坏的情况下。

相反，让 $z = R x - b$ ，我们可以尝试解决

[\begin{matrix} D & R^{T} \\ R & - I_{n} \end{matrix}] [\begin{matrix} x \\ z \end{matrix}] = [\begin{matrix} 0 \\ b \end{matrix}]

$\begin{bmatrix} D & R^T \\ R & - I_n \end{bmatrix} \begin{bmatrix} x \\ z \end{bmatrix} = \begin{bmatrix} 0 \\ b \end{bmatrix}$ 在最坏情况下的成本

(n + m)^{3}

$(n+m)^3$ 这似乎比原来的方法更糟糕。但后一个系统有一个很大的身份块。是否有可能比较小的系统更有效地解决较大的系统，例如通过有效的 Cholesky 分解或迭代过程。让我们假设

R

$R$ 通常是密集的，尽管我们可以通过阈值化通过稀疏矩阵来近似它。

我应该补充一点，任何避免直接矩阵乘法的原始问题的解决方案也很有趣。