计算科学 - 删除或添加行和列后的矩阵行列式 - 吾爱随笔录

计算科学线性代数

2021-12-13 22:44:31

在量子力学中，N 个电子的波函数由一个行列式给出。我正在研究蒙特卡洛算法。在每个 Monte Carlo 步骤中，我需要添加或移除一个电子，这意味着在我的矩阵中添加或移除一行和一列。

我使用高斯消元来计算上三角矩阵。添加一行和一列很简单，可以在增长的时间内完成。中删除最后一行和最后一列也是可行的。对于第 i 行，除了重新计算从 i 到 n-1 的枢轴之外，我没有看到其他可能性，这需要时间。 $O(n^2)$ $O(n^2)$ $O(n^3)$

有人看到另一个可能吗？

1个回答

如果旋转的变化是一个问题，那么是的，据我所知，没有明显的解决方案。但是，您可以考虑切换到QR 分解。该分解的初始计算成本是 LU 的两倍，但它可以在中以稳定的方式更新。有关算法，请参见 Golub 和 Van Loan矩阵计算，或https://www.mathworks.com/help/matlab/ref/qrupdate.html和https://docs.scipy.org/doc/scipy/reference/generated/scipy .linalg.qr_update.html用于实现。不幸的是，代码不在 Lapack 中。 $O(n^3)$ $O(n^2)$

如果您的矩阵恰好是对称正定矩阵，那么还有一些方法可以更新其 Cholesky 因式分解，以便更便宜地保持对称性。

两个因式分解至少揭示了. 如果需要，跟踪的符号可能会很棘手，但它应该被唯一确定，因为每个 QR 只做一些 Householder ( ) 或 Givens ( ) 更新。 $|\det A|$ $\det(Q)$ $\det=-1$ $\det=1$

其它你可能感兴趣的问题