algorithm - 向量乘法算法

Question

设A,B是 R^n 空间的矩阵，b属于 R^n。描述一种快速算法来计算 A^-2*B*A^-3*b。该算法将进行多少次计算？

这是我用于数值分析的考试题。我尝试过强制算法，但我相信答案更具数学性。

我们还没有讨论过大 O 符号，所以这个问题严格要求算法的动作。你会如何回答这个问题？

标签： algorithmmatrix-multiplicationnumerical-analysis

Answer 1

我会从右到左解决问题，在处理 A 的逆时使用线性求解器，在处理 B 时使用矩阵乘法：

x1 = linsolve(A, b)
x2 = linsolve(A, x1)
x3 = linsolve(A, x2)
y = B*x3
z1 = linsolve(A,y)
result = linsolve(A,z1)

您可以通过将 A 的 LU 分解保留在内存中来减少操作数的常数乘数，但除非您在 A 和 B 上获得更多结构，否则二次复杂度似乎是您可以达到的最佳目标。