计算科学 - 对称正定矩阵的对角线更新 - 吾爱随笔录

计算科学线性代数

2021-12-12 21:35:22

$A$ 是一个对称正定 (SPD) 稀疏矩阵。是一个稀疏对角矩阵。很大（ >10000），中非零的数量通常为 100 ~ 1000。 $n \times n$ $G$ $n$ $n$ $G$

$A$ 在cholesky 形式中被分解为。 $LDL^T$

当变为时如何有效地更新和？ $L$ $D$ $A$ $A+G$

1个回答

CHOLMOD SuiteSparse 包的最新版本（beta 4.4.5）支持修改对称行/列（rank2 更新） $LDL^T$ 分解，使用 matlab（和 C）API。我在我的一个项目中成功使用了它。

你可以用它来制作 $nnz(G)$ 分解的更新。它基于这篇论文。

因此，复杂度将是 $O(nnz(G)*nnz(L))$ . 在哪里 $nnz(L)$ 当对稀疏使用填充减少排列时，可以显着减少 $A$

以下是包所有者给出的一些注释（Tim Davis 教授）：

接口：

LD = ldlrowmod (LD,k) 通过将 A(:,k) 和 A(k,:) 设置为标识的第 k 行/列来删除行/列 k。

LD = ldlrowmod (LD,k,C) 用稀疏列 C 替换 A 的第 k 行/列（必须是标识的第 k 行/列）。

复杂：

行添加/删除最多需要 $O(nnz(L))$ 时间，所以如果 $nnz(L)$ 是 $O(n)$ , 那么时间最多 $O(n)$ .

填充减少排列：

分解用户矩阵很少是一个好主意，例如 $LDL^T$ = A. 相反，我们置换为 $LDL^T$ = $PAP^T$ 以便 $L$ 有非常少的非零。

其它你可能感兴趣的问题