使用稀疏 PD 矩阵的逆计算二次形式,比较使用逆矩阵与使用 Cholseky 分解

计算科学 线性求解器 稀疏矩阵 矩阵分解
2021-11-27 21:41:08

我需要评估以下二次形式:

xTA1y, 在哪里A是一个稀疏的正定矩阵,x,y是稀疏向量。

现在假设我都免费获得A1和 Cholesky 分解A=LDLT. 我知道评估仍然会更快xTA1y使用 Cholesky 分解,而不是直接。

你能把每个备选方案的计算复杂度(+参考)联系起来吗?

1个回答

这取决于矩阵。如果A=αI,您需要少做一次操作A1与 Cholesky 因子相比。通常,Cholesky 因子版本更快的原因是它更稀疏,但这高度依赖于矩阵。我想,很难得到正式的结果。