线性代数/主题：计算行列式的速度

线性代数
← 主题：克莱姆法则	主题：计算行列式的速度	主题：射影几何 →

用于计算行列式的排列展开公式对于证明定理很有用，但使用行操作的方法对于找到大型矩阵的行列式要好得多。我们可以通过考虑计算机算法设计人员所使用的算术运算次数来使该陈述精确。

算法的速度是通过找到计算机在输入数据集大小增长时所花费的时间如何增长来衡量的。例如，如果我们将输入数据集的大小增加十倍，从一个 $1000$ 行矩阵到一个 $10,000$ 行矩阵，或者从 $10,000$ 到 $100,000$ ？算法所花费的时间是增加了十倍，还是一百倍，还是一千倍？也就是说，算法所花费的时间与数据集的大小成正比，还是与该大小的平方成正比，还是与该大小的立方成正比等等？

回想一下用于行列式的排列展开公式。

{\begin{array}{rl}{\begin{vmatrix}t_{1,1}&t_{1,2}&\ldots &t_{1,n}\\t_{2,1}&t_{2,2}&\ldots &t_{2,n}\\&\vdots \\t_{n,1}&t_{n,2}&\ldots &t_{n,n}\end{vmatrix}}&=\displaystyle \sum _{{\text{permutations }}\phi }\!\!\!\!t_{1,\phi (1)}t_{2,\phi (2)}\cdots t_{n,\phi (n)}\left|P_{\phi }\right|\\&={\begin{aligned}&t_{1,\phi _{1}(1)}\cdot t_{2,\phi _{1}(2)}\cdots t_{n,\phi _{1}(n)}\left|P_{\phi _{1}}\right|\\&\quad +t_{1,\phi _{2}(1)}\cdot t_{2,\phi _{2}(2)}\cdots t_{n,\phi _{2}(n)}\left|P_{\phi _{2}}\right|\\&\quad \vdots \\&\quad +t_{1,\phi _{k}(1)}\cdot t_{2,\phi _{k}(2)}\cdots t_{n,\phi _{k}(n)}\left|P_{\phi _{k}}\right|\end{aligned}}\end{array}}

有 $n!=n\cdot (n-1)\cdot (n-2)\cdots 2\cdot 1$ 个不同的 $n$ -排列。对于任何大小的数字 $n$ ，这是一个很大的值；例如，即使 $n$ 只有 $10$ ，那么展开式有 $10!=3,628,800$ 项，所有这些项都是通过将 $n$ 个条目相乘得到的。这是一个非常大的乘法次数（例如，(Knuth 1988) 认为 $10!$ 步是一个粗略的实际计算极限）。阶乘函数的增长速度快于平方函数。它比立方函数、四次方函数或任何多项式函数的增长速度都快。（我们可以通过注意到阶乘函数中前两个因子的乘积为 $n\cdot (n-1)$ ，对于较大的 $n$ ，它近似于 $n^{2}$ ，然后乘以更多因子会使它变得更大。同样的论点适用于立方函数等等。）因此，一个被编程为使用排列展开公式的计算机，它执行的操作次数大于或等于行数的阶乘，随着其输入数据集的增长，将会花费很长时间。

相比之下，行减少方法所花费的时间并没有那么快。这段行减少代码片段是用 FORTRAN 语言编写的。矩阵存储在 $N\!\times \!N$ 数组 A 中。对于每个 ROW 从 $1$ 到 $N$ ，程序中未显示的部分已经找到了主元条目 $A(ROW,COL)$ 。现在程序进行行主元操作。

-PIVINV\cdot \rho _{ROW}+\rho _{i}

(这段代码片段仅供说明，不完整。但是，分析包括所有测试和子情况的完成版本会更复杂，但最终结论基本相同。)

PIVINV=1.0/A(ROW,COL) DO 10 I=ROW+1, N DO 20 J=I, N A(I,J)=A(I,J)-PIVINV*A(ROW,J) 20 CONTINUE 10 CONTINUE最外层循环（未显示）遍历 $N-1$ 行。对于每一行，嵌套的 $I$ 和 $J$ 循环（如上图所示）对位于主元条目下方和右侧的 A 中的条目执行算术运算。假设主元位于预期位置，即 $COL=ROW$ 。那么，在主元下方和右侧有 $(N-ROW)^{2}$ 个条目。平均而言，ROW 将是 $N/2$ 。因此，我们估计算术运算将执行约 $(N/2)^{2}$ 次，也就是说，其运行时间与方程数量的平方成正比。考虑到未显示的外循环，我们估计算法的运行时间与方程数量的立方成正比。

找到计算行列式的最快算法是当前研究的主题。已知的算法在第二和第三次幂之间运行。

这些速度估计有助于我们了解算法的运行速度。运行时间与数据集大小成正比的算法速度很快，运行时间与数据集大小的平方成正比的算法速度较慢，但通常非常实用，而运行时间与数据集大小的立方成正比的算法对于不太大的输入数据仍然具有合理的运行速度。但是，运行时间（大于或等于）数据集大小的阶乘的算法对于任何可观大小的输入都不实用。

除了这里讨论的两种方法之外，还有其他方法用于计算行列式。这些超出了我们的范围。尽管如此，这两种计算行列式方法的对比表明，尽管在原则上它们给出相同的答案，但在实践中，我们的目标是选择速度更快的那个。

练习

大多数这些问题都假定可以访问计算机。

问题 1

计算机系统生成随机数（当然，这些只是伪随机数，因为它们是由算法生成的，但它们通过了随机性的许多合理统计测试）。

用随机数填充一个 $5\!\times \!5$ 数组（例如，在范围 $[0..1)$ 中）。看看它是否奇异。重复这个实验几次。奇异矩阵是常见的吗还是罕见的吗（从这个意义上讲）？
计时你的计算机代数系统找到十个 $5\!\times \!5$ 随机数数组的行列式。找到每个数组的平均时间。对 $15\!\times \!15$ 数组、 $25\!\times \!25$ 数组和 $35\!\times \!35$ 数组重复上一步。（请注意，当数组奇异时，有时可以很快地发现它是奇异的，例如，如果第一行等于第二行。根据你对第一步的回答，你认为奇异系统在你的平均值中起着重要作用吗？
绘制输入大小与平均时间的关系图。