解决*稀疏*上三角系统

Question

如果我想解决一个完整的上三角系统,我可以打电话linsolve(A,b,'UT').但是稀疏矩阵目前不支持此功能.我怎么能克服这个？

Answer 1

编辑由于您需要的是三角求解过程，也称为向后/向前替换，\因此您可以使用普通的 MATLAB 反斜杠运算符：

x = U\b

正如原始答案中提到的，MATLAB 会识别出您的矩阵是三角形的事实。为了确定这一点，您可以将性能与SuiteSparsecs_usolve中的过程进行比较。它是用 C 实现的 mex 函数，用于计算上三角稀疏矩阵的稀疏三角解（也有类似的函数：、和）。cs_lsolvecs_utsolvecs_ltsolve

您可以查看本机 MATLAB 和稀疏 Cholesky 分解上下文中的性能比较。cs_l(t)solve从本质上讲，MATLAB 性能良好。唯一的陷阱是如果你想解决转置系统

x = U'\b

MATLAB 无法识别这一点并显式创建 的转置U。在这种情况下，您应该cs_utsolve显式调用。

原始答案如果您的系统是对称的并且您只存储上三角矩阵部分（这就是我在您的问题中完全理解的方式），并且如果 Cholesky 分解适合您，则chol处理对称矩阵（如果您的矩阵是正定的）。对于不定矩阵，您可以使用ldl。两者都处理稀疏存储并处理对称矩阵部分。

较新的 matlab 版本使用cholmod 和 suitesparse来实现这一点。这是迄今为止我所知道的性能最好的乔列斯基分解。在 matlab 中，它也使用并行 BALS 进行并行化。

从上述函数获得的因子是上三角矩阵 L，使得

A=LL'

您现在所需要做的就是执行前向和后向替换，这既简单又便宜。在 matlab 中，这是在反斜杠运算符中自动完成的

x=L'\(L\b)

矩阵可以是稀疏的，matlab 会识别出它是上/下三角矩阵。您还可以将此调用与使用乔列斯基分解获得的因子的前向替换一起使用。