计算科学 - 从 Householders 反射器有效地计算投影矩阵 - 吾爱随笔录

从 Householders 反射器有效地计算投影矩阵

计算科学线性代数拉帕克矩阵分解投影

2021-12-16 02:10:01

设其中。 $A \in \mathbb{R}^{m \times n}$ $m \geq n$

设和是应用 LAPACK方法的结果（右上三角形为 R，对角线下方为 Householders 反射器）。 $B$ $\tau$ dgeqrfp

您将如何使用反射器和在与 A 的列所跨越的空间正交的空间上执行任何矩阵的投影？ $\tau$

一种方法是建立所有 Householder 变换 where and in matlab's notation。然后我们可以计算因子。 $H_i = I - \tau v_i v_i^t$ $v_i[1:i] = 0$ $v_i[i+1:m] = B[i+1:m]$ $Q = H_n ... H_1$

那么投影仪是。 $P_{A^\bot} = QQ^t$

你知道更有效的方法吗？

1个回答

幸运的是，LAPACK 提供了处理分解 [dgeqrf]因子的例程。要找到任意正交的空间上的投影，您需要形成。这里有两个选项： $\mathbf Q$ $\mathbf A = \mathbf Q \mathbf R$ $\mathbf B$ $\mathrm {range}(\mathbf A)$ $\mathbf C = \left(\mathbf I - \mathbf Q \mathbf Q^T\right) \mathbf B$

(1) 你可以制成表格，然后使用 [dgemm] 的两个调用计算，首先使用转置，然后不使用。您可以通过覆盖，但您可能需要一个临时值来表示中间值。 $\mathbf Q$ $\mathbf C$ $\mathbf Q$ $\mathbf A$ $\mathbf Q^T \mathbf B$

(2) 使用两个调用 [dormqr]，它可以应用或的动作而不显式地形成它。您可能仍然需要一个临时代表。 $\mathbf Q^T$ $\mathbf Q$ $\mathbf Q^T \mathbf B$

我希望（2）更准确一点，因为它直接与户主格式一起使用。但是，如果 (1) 对于大型问题更快（因为优化 [dgemm] 比 [dormqr] 更容易），我不会感到惊讶。特别是如果你有多个的，你可以在其中摊销预先制表的成本。 $\mathbf B$ $\mathbf Q$

编辑：我应该澄清一下，在一次操作中（乘以或乘以），我不希望 [dorgqr] 后跟 [dgemm] 击败对 [dormqr] 的一次调用。实际上，[dorgqr] 是与 [dormqr] 相同的家庭累加算法，它一个乘法以可预测/可利用的方式填写）。在这种情况下，我认为 (1) 可能更快的原因更多是因为您需要应用两次，这让您有机会摊销/重用计算 $\mathbf Q$ $\mathbf Q^T$ $\mathbf Q \mathbf I$ $\mathbf Q \mathbf I$ $\mathbf Q$ $\mathbf Q$ 跨多个 [dgemm] 调用（这几乎是您能找到的最快的操作）。我们不需要挂在上的事实进一步帮助了我们，这意味着我们可以重用/破坏来存储（而在一般情况下，您可能更喜欢 [dormqr]因为它会让不受干扰）。 $\mathbf R$ $\mathbf A$ $\mathbf Q$ $\mathbf R$

其它你可能感兴趣的问题

上一篇求解具有 TE 模式的 Neumann 边界条件的 2D 矩形波导 PDE 下一篇如何将 Aasen 算法的输出提取为可用形式？