原文

The Best of the 20th Century: Editors Name Top 10 Algorithms

(二十世纪最佳:编辑列出10大顶级算法)

By Barry A. Cipra

http://www.uta.edu/faculty/rcli/TopTen/topten.pdf

1. 蒙特卡罗方法

1946年:约翰·冯·诺伊曼(John von Neumann),斯坦·乌拉姆(Stan Ulam)和尼克·梅特波利斯(Nick Metropolis)都在洛斯阿拉莫斯科学实验室工作,研究了 Metropolis algorithm,(也称为蒙特卡罗方法),它的目的是获得难以解决的多度数值问题的近似解。 通过模仿随机过程来解决自由和阶乘大小的组合问题。 鉴于数字计算机在确定性计算方面的声誉,它最早的应用之一就是随机数的生成,这很合适。

Monte Carlo method,也称统计模拟方法,是1940年代中期由于科学技术的发展和电子计算机的发明,而提出的一种以概率统计理论为指导的数值计算方法。是指使用随机数(或更常见的伪随机数)来解决很多计算问题的方法。

20世纪40年代,在科学家冯·诺伊曼(John von Neumann)、斯塔尼斯拉夫·乌拉姆(Stanisław Marcin Ulam)和尼古拉斯·梅特罗波利斯(Nicholas Constantine Metropolis)于洛斯阿拉莫斯国家实验室为核武器计划工作时,发明了蒙特卡罗方法。因为乌拉姆的叔叔经常在摩纳哥的蒙特卡洛赌场输钱得名,而蒙特卡罗方法正是以概率为基础的方法。

与它对应的是确定性算法。

蒙特卡罗方法在金融工程学、宏观经济学、生物医学、计算物理学(如粒子输运计算、量子热力学计算、空气动力学计算)、机器学习等领域应用广泛。

2. 单纯形法

simplex method for linear programming.

1947年:兰德公司(RAND Corporation)的乔治·丹茨格(George Dantzig)创建了线性编程的单纯形法。 在预算和其他约束条件下进行优化的能力。 (当然,行业的“实际”问题通常是非线性的;线性规划的使用有时由计算预算决定。)单纯形法是获得最佳答案的一种优雅方法。 尽管从理论上讲容易受到指数延迟的影响,但该算法在实践中非常高效-本身就对计算的本质提出了一些有趣的看法。

单纯形法(simplex algorithm)在数学优化领域中常用于线性规划问题的数值求解。

3. Krylov 子空间迭代方法

Krylov subspace iteration methods.

1950年:美国国家标准局数值分析研究所的 Magnus Hestenes,Eduard Stiefel 和 Cornelius Lanczos 发起了 Krylov 子空间迭代方法的开发。这些算法解决了看似简单的求解形式 Ax=bAx = b。当然,要解决的问题是 AA 是一个巨大的 nnn*n 矩阵,因此代数答案 x=bAx = \frac{b}{A} 不太容易计算。(实际上,矩阵“除法”并不是特别有用迭代方法,例如用理想的“接近” AA 的简单矩阵 KK 求解 Kxi+1=Kxi+bAxiKx_{i+1} = Kx_i + b – Ax_i 形式的方程式,导致了 Krylov 子空间的研究。以俄罗斯数学家尼古拉·克雷洛夫(Nikolai Krylov)的名字命名,克雷洛夫子空间被应用于初始“余数”向量 r0=bAx0r_0 = b – Ax_0 的矩阵的幂所覆盖。 Lanczos 发现了一种在矩阵对称时为此类子空间生成正交基础的巧妙方法。对于对称和正定的系统,Hestenes 和 Stiefel 提出了一种甚至更精细的方法,称为共轭梯度法。在过去的 50 年中,许多研究人员对这些算法进行了改进和扩展。当前的套件包括非对称系统的技术,首字母缩写词是 GMRES 和 Bi-CGSTAB。 (GMRES 和 Bi-CGSTAB 分别于 1986 年和 1992 年在 SIAM 科学和统计计算杂志上首次亮相。)

4. 矩阵计算的分解方法

1951年:橡树岭国家实验室的 Alston Householder 正式确定了矩阵计算的分解方法,将矩阵分解为三角形,对角线,正交和其他特殊形式的能力非常有用。 分解方法使软件开发人员能够生成灵活高效的矩阵包。 它还方便了对舍入误差的分析,舍入误差是数值线性代数的主要缺陷之一。 (1961 年,伦敦国家物理实验室的詹姆斯·威尔金森(James Wilkinson)在 ACM 杂志上发表了一篇开创性的论文,标题为“矩阵求逆的直接方法的误差分析”,它基于矩阵LU分解为低和高的乘积。 上三角因子)。

5. Fortran 优化编译器

1957年:John Backus 领导 IBM 团队开发 Fortran 优化编译器。 Fortran 的创建可能被视为计算机编程历史上最重要的事件:最后,科学家(和其他人)可以告诉计算机他们想要它做什么,而不必陷入机器代码的整个世界。 尽管受现代编译器标准的限制(Fortran I 仅由 23,500 条汇编语言指令组成),但早期的编译器仍然能够执行令人惊讶的复杂计算。 正如 Backus 自己在 1998 年在 IEEE 计算历史年鉴上发表的Fortran I,II 和 III 的近期历史中所回顾的那样,编译器“产生的效率如此之高,以至于其输出会使研究它的程序员感到震惊。”

6. QR 算法

1959–61:J.G.F。 伦敦的 Ferranti Ltd. 的 Francis 找到了一种稳定的计算特征值的方法,称为 QR 算法。 特征值可以说是与矩阵相关的最重要的数字,并且它们可能是最难计算的。 将方阵转换成“几乎”上三角的矩阵相对容易,这意味着在主对角线下方仅包含一个额外的一组非零项。 但是,消除那些最终的非零而不引发大量错误是不平凡的。 QR 算法只是票证。 在 QR 分解的基础上,将 AA 写为正交矩阵 QQ 和上三角矩阵 RR 的乘积,此方法将 Ai=QRA_i = QR 迭代地更改为 Ai+1=RQA_{i+1} = RQ,并用一些钟声将其收敛到上三角形式 。 到1960年代中期,QR算法已将曾经形成的特征值问题转化为常规计算。

7. 快速排序算法

1962 年:伦敦 Elliott Brothers,Ltd. 的 Tony Hoare 提出了 Quicksort。将 N 个事物按数字或字母顺序排列是令人难以置信的平凡。智力的挑战在于设计出如此迅速地做的方式。Hoare 的算法使用了古老的分而治之递归策略来解决该问题:选择一个元素作为 “枢轴”,将其余元素分成成堆的 “大” 和 “小” 元素(与枢轴相比),然后 然后在每个桩上重复此过程。 尽管可能会卡住所有 N(N1)/2N(N–1)/2 个比较(特别是如果您将已经排序的列表中的第一个项目用作数据透视表),但 Quicksort 的平均运行效率为 O(NlogN)O(N log N)。 它的优雅简洁性使 Quicksort 成为计算复杂性的后代。

快速排序(英语:Quicksort),又称划分交换排序(partition-exchange sort),简称快排,一种排序算法。在平均状况下,排序 n 个项目要 O(nlogn)O(nlogn) (大 OO 符号)次比较。在最坏状况下则需要 O(n2)O(n^2) 次比较,但这种状况并不常见。事实上,快速排序 Θ(nlogn)Θ(nlogn) 通常明显比其他算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地达成。

8. 快速傅里叶变换

1965 年:IBM T.J. 沃森研究中心的 James Cooley,普林斯顿大学的约翰·图基 和 AT&T 贝尔实验室推出了快速傅立叶变换技术。FFT 是应用数学中影响最深的算法,它彻底改变了信号处理。基本思想可以追溯到高斯(需要计算小行星的轨道),但是正是 Cooley-Tukey 的论文清楚地表明了可以轻松地进行傅里叶变换。 像 Quicksort 一样, FFT 依靠分而治之的策略将表面上的 O(N2)O(N^2) 琐事减少为 O(NlogN)O(NlogN)。但是,与 Quicksort 不同,实现方式(乍看之下)是非直觉的,并且不那么直接。这本身就为计算机科学提供了动力来研究计算问题和算法的内在复杂性。

快速傅里叶变换(英语:Fast Fourier Transform, FFT),是快速计算序列的离散傅里叶变换(DFT)或其逆变换的方法。傅里叶分析将信号从原始域(通常是时间或空间)转换到频域的表示或者逆过来转换。FFT 会通过把 DFT 矩阵分解为稀疏(大多为零)因子之积来快速计算此类变换。因此,它能够将计算 DFT 的复杂度从只用 DFT 定义计算需要的O(n2)O(n^2),降低到O(nlogn)O(nlogn),其中 nn 为数据大小。

快速傅里叶变换广泛的应用于工程、科学和数学领域。这里的基本思想在1965年才得到普及,但早在1805年就已推导出来。1994年美国数学家吉尔伯特·斯特朗把FFT描述为“我们一生中最重要的数值算法”。

9. 整数关系检测算法

1977 年:杨百翰大学的 Helaman Ferguson 和 Rodney Forcade 提出了整数关系检测算法。问题是一个古老的问题:给定一堆实数,例如 x1,x2,...,xnx_1, x_2, ..., x_n,有一些整数 a1,a2,...,ana_1, a_2, ..., a_n (并非全为 0 )是 a1x1+a2x2+...+anxn=0a_1x_1 + a_2x_2 + ... + a_nx_n = 0 ?对于 n=2n = 2 ,可敬的欧几里得算法执行此任务,计算 x1/x2x_1/x_2 的连续分数展开式中的项。如果 x1/x2x_1/x_2 是有理数,则扩展将终止,并通过适当的拆散,给出“最小”整数 a1 和 a2。如果欧几里得算法没有终止,或者您只是厌倦了计算,那么解开过程至少可以为最小整数关系的大小提供下界。弗格森(Ferguson)和福卡德(Forcade)的概括,虽然难以实施(和理解),但功能更强大。例如,他们的检测算法已用于查找逻辑图的第三和第四分叉点 B3=3.544090B3 = 3.544090B4=3.564407B4 = 3.564407 所满足的多项式的精确系数。 (后一个多项式的阶数为 120120;最大系数为 2573025730。)它也被证明有助于简化量子场论中的费曼图的计算。

10. 快速多极子算法

1987 年:耶鲁大学的 Leslie Greengard 和 Vladimir Rokhlin 发明了快速多极子算法。 该算法克服了多粒子模拟的最大难题之一:准确计算通过重力或静电力相互作用的 N 个粒子运动(想想星系中的恒星,或蛋白质中的原子)的事实似乎需要 O(N2)O(N^2) 个计算—每对粒子一个。 快速多极算法通过 O(N)O(N) 计算获得。它是通过使用多极展开(净电荷或质量,偶极矩,四极等)来估计远距离粒子对局部粒子组的影响。 空间的层次分解用于定义随着距离增加而越来越大的组。 快速多极点算法的独特优势之一是它配备了严格的误差估计,这是许多方法都缺乏的功能。