有人建议我应该尝试从数学这里发布这个问题

背景

我正在研究 C# 中的数值线性代数包。我正在尝试实现各种“主要旋转”方法来解决优化问题（特别是线性互补问题，但我认为类似的方案用于线性和二次规划）。这些方法需要能够将列向量与矩阵的“主要关键变换”相乘。

矩阵的主枢轴变换 (PPT)$M$定义为：

$$PM^'P^T = \left (\begin{array}{cc} M_{\alpha\alpha}^{-1} &\ -M_{\alpha\alpha}^{-1} M_{\alpha\beta} \\ M_{\beta\alpha}M_{\alpha\alpha}^{-1} &\ M_{\beta\beta} - M_{\beta\alpha} M_{\alpha\alpha}^{-1}M_{\alpha\beta} \end{array} \right )$$

在哪里$\alpha$是一组旋转的行/列索引，并且$\beta$是一组未透视的行/列索引。 $P$是一个置换矩阵，它将旋转和非旋转的行/列保持在一起，以使上面的块矩阵形式更清晰。 $M_{\alpha\beta}$是一个子矩阵$M$与中的行$\alpha$和中的列$\beta$, 和其他子矩阵$M$定义类似。还，$M_{\alpha\alpha}^{-1} = (M_{\alpha\alpha})^{-1}$并不是$(M^{-1})_{\alpha\alpha}$

...

主枢轴方法的每次迭代都会从$\alpha$到$\beta$或反之。这种单一的旋转操作可以表示为矩阵的低秩更新。假设我们正在旋转索引$r$并使用$M^'$表示更新的矩阵：

$$\begin{matrix} M_{rr}^' & = & & \frac{1}{M_{rr}} & \\ \\ \\ M_{ir}^' & = & & \frac{M_{ir}}{M_{rr}}, & (i \neq r) \\ \\ \\ M_{ri}^' & = & & \frac{-M_{ri}}{M_{rr}}, & (i \neq r) \\ \\ \\ M_{ij}^' & = & M_{ij} - & \frac{M_{ir} * M_{ri}}{M_{rr}}, & (i \neq r, j \neq r) \end{matrix}$$

这就是我目前正在做的事情。不幸的是，这基本上是在计算$M_{\alpha\alpha}^{-1}$使用类似高斯消除的方法。我有一些测试用例，即使在小问题上，即使使用双精度浮点，结果也会出现数值问题。为了帮助解决这个问题，如果我从$\alpha$（也就是说，如果我取消一个索引），我使用上述方案一次使用一个主元从头开始重新计算矩阵。但这使得我的 Principal Pivot 算法很慢。

题

我知道有合理的方法来计算产品$M_{\alpha\alpha}^{-1} z$对于一些列向量$z$无需计算$M_{\alpha\alpha}^{-1}$直接（如LU分解或QR分解）。我可以从当前的枢轴集（$\alpha$)，并且可能会得到一个非常强大的方法。但是随后枢轴算法的每次迭代都需要$O(n^3)$; 这太慢了。我可以对 LU 或 QR 分解进行低秩更新，但由于大多数算法一次只旋转一个索引，因此在几次迭代后我失去了这些分解方案的大部分好处。我只能每隔几次迭代执行一次完全分解，但问题是我应该多久执行一次？而且它仍然会很慢。

有没有更聪明的事情可以做？我想我基本上需要找到主要子矩阵的分解。有没有关于这个主题的文献？还有其他解决问题的方法吗？