algorithm - 通过增加 A 的大小来测量求解线性系统 Ax=b 的计算复杂度

Question

我有一个线性方程

Ax=b

其中A是非奇异矩阵N×N，x,b是向量N×1 >; A,b 已给出，我想找到 x

很明显x可以通过x=A^(−1)*b找到。我想测量 N 增加时的计算复杂度。

在 MATLAB 中，我使用了代码 x=A\b。我知道 MATLAB 会选择一个最佳算法来找到解决方案。在分析中，我知道当 N 增加时，计算复杂度会随着 N^3 增长。当 N 增加时，如何拟合/测量上述方程的模拟和分析之间的计算复杂度？

Answer 1

根据linear solver flowchart , 对于随机矩阵 A = rand(n) 求解器将使用 LU 分解(本质上是高斯消元法)，因为所有其他算法都需要某种特殊形式的矩阵。

所需操作的数量是 N^3 阶。但这并不能转化为 N^3 运行时间，因为 MATLAB 中的数值线性代数例程 are multithreaded .例如，当对某列进行高斯消元时，行操作可以独立进行，因此可以分布在多个线程之间。

下面是我如何测试线性求解器的运行时间。矩阵大小为 100:10:500。我使用相同的矩阵重复 A\b 500 次(以避免将生成这些矩阵的成本添加到总数中)。

sizes = 100:10:500;
tries = 500;
n = numel(sizes);
time = zeros(1, n);
for j = 1:n
    A = rand(sizes(j));
    b = rand(sizes(j), 1);
    tic 
    for k = 1:tries
        x = A\b;
    end
    time(j) = toc;
end
logsize = log(sizes/sizes(1));
logtime = log(time/time(1));
plot(sizes, logtime./logsize);
axis([sizes(1) sizes(end) 0 4])

我没有查看plot(sizes, time) 并试图弄清楚它是三次方还是什么，而是采用对数比率来直接显示 N 的指数。它在我的机器上看起来像这样，表示大约 N^2 增长。

(正如 Luis Mendo 所指出的，使用 timeit 而不是 tic，toc 会更好，但它在我的旧版本中不可用MATLAB.)