矩阵求逆时间

Question

我在Matlab中生成了一个对称（Toeplitz）矩阵。

• 对于3200x3200的矩阵，求逆时间为5.8秒
• 对于5000x5000的矩阵，求逆时间为70.7秒
• 对于7200x7200的矩阵，求逆时间为1700秒

请问有人能告诉我这种指数增长的原因吗？我已经学习到需要N^3次操作来找到逆，但仍无法理解。

实际上，我正在使用MoM构建矩阵，对于9800x9800的矩阵大小，我得到了“内存不足”的错误。那么这个问题的解决方案是什么呢？

谢谢。

- user2790773

---

可能您正在使用的内存过多，导致操作系统不得不使用交换空间（swap）。 - Oliver Charlesworth

一个7200x7200的矩阵只需要消耗大约400MB的内存。MATLAB的求逆命令会大幅增加内存使用量吗？ - MrAzzaman

测量更广泛的矩阵大小的执行时间。绘制执行时间与大小的图形。图中的不连续性可能是内存层次结构对计算的影响：缓存效应（每个缓存级别一个效应），以及如@OliCharlesworth所建议的，从RAM交换到磁盘（内存层次结构中倒数第二步）。 - High Performance Mark

Answer 1

你似乎发现了一些可能的原因，例如：

1. 考虑到矩阵的结构，你并不总是得到最坏情况下的计算成本
2. 你的时间测量不足
3. 慢速计时不是计算本身的结果

我自己进行了快速测试，目前看起来它的行为类似于O(N^3)，比指数函数要平缓一些。

mySize = (1:10:100).^2;
timings = [];
for isize=mySize 
    disp(isize)
    M = rand(isize);
    tic
    inv(M);
    t= toc;
    timings = [timings;t];
end


plot(mySize,timings)
hold all
plot(mySize,mySize.^1.5/mean(mySize.^1.5)*mean(timings))

- Dennis Jaheruddin

---

我修复了代码并运行了它。你为什么要添加一个 n^1.5 的参考线？在我的电脑上完全匹配 n^3。 - Daniel

@DanielR 我假设 N 代表矩阵中的行数。如果它代表元素的数量，那么确实应该是 ^3。很高兴听到它匹配得很好。 - Dennis Jaheruddin

你说得对，由于某些原因，在我的电脑上匹配的是n^3，应该是n^1.5。 - Daniel