Python 中稀疏矩阵的 LDL 分解

Question

假设我有一个稀疏对称实不定矩阵A，大小为N=150,000。该矩阵是在算法的每次迭代时生成的，具有相同的结构（非零元素的位置）但值不同。我需要在每次迭代中求解几个 Ax=b 形式的系统，并计算矩阵惯性（正、负和零特征值的数量）。从现有文献来看，使用矩阵 A 的 LDL.T 分解似乎是一种很有前途的方法。

A 是一个 KKT 矩阵，其形式如下：

|--------+-----|
| | |
|哈 | GT |
| | |
|--------+-----|
| G | 0 |
|--------+-----|

H主要是对角线，G是矩形，由沿对角线重叠的矩形块组成（通过状态方程组的离散化获得）。

我正在使用Python。我尝试过使用 numpy 包、cvxopt 包来实现密集和稀疏实现，但是分解对于我的目标来说太慢了。

有没有人推荐一个 python 包/方法来解决这样的（中等）大小问题？ 例如，多前沿直接求解器/因子分解器的良好实现？ 有什么方法可以充分利用矩阵结构从一次迭代到下一次迭代都是相同的事实吗？ 有什么跳出框框的想法吗？

Answer 1

其他人可能会遇到稍微不同的问题，所以首先了解一些背景信息。 具体来说，如果 A 是对称正定的，则可以简单地进行乔列斯基分解，然后从对角线上分离出来。为此，存在大量软件支持。 对于准定矩阵，这是不可能的，因此提问者询问 LDL 分解，这是 Cholesky 的推广。

QDLDL 软件包提供了 C 语言的 LDL 实现。 它是众所周知的 OSQP 二次凸优化求解器的一部分。 https://github.com/osqp/qdldl。 还有一个 python 界面：https://github.com/osqp/qdldl-python，可以通过 PIP 安装

 pip install qdldl

求解线性系统Ax=b可以通过以下方式实现：

import qdldl
F = qdldl.Solver(A)
x = F.solve(b)

但是，当稀疏模式仍然存在时，QDLDL 还允许仅更新 A 中的特定值。 在这些情况下，符号分解阶段只需完成一次。计算成本大大降低。

F.update(A_new)

从研究的角度来看，如果您能够提供有关线性系统解决方案的应用和背景的背景，我将不胜感激。