EDA算法探究--20世纪10个影响最大的算法在EDA领域的应用

21世纪初，科研人员总结了上个世纪对工业界影响最大的10个算法，其中大多数算法都在EDA领域有重要应用。我们今天来看一下，这10大算法，你在大学期间学过哪些？在工作中学过和用到哪些？如果10个算法你全部在工作中应用到，说明你已经对人类一个世纪以来研究的精华掌握得很好了。

10大算法如下：

1. Monte Carlo方法

1946年，在洛斯阿拉莫斯科学实验室工作的John von Neumann，Stan Ulam和Nick Metropolis编制了Metropolis算法，也称为Monte Carlo方法。 Metropolis算法旨在通过模仿随机过程，来得到具有难以控制的大量的自由度的数值问题和具有阶乘规模的组合问题的近似解法。数字计算机是确定性问题的计算的强有力工具，但是对于随机性（不确定性）问题如何当时并不知晓。通过monte Carlo方法，可以在有效的时间内近似得到最优解。

在EDA领域，Monte Carlo算法在电路仿真等多个领域有应用。

2. 线性规划的单纯形方法

1947年，兰德公司的Grorge Dantzig创造了线性规划的单纯形方法。就其广泛的应用而言，Dantzig算法一直是最成功的算法之一。线性规划对于那些要想在经济上站住脚，同时又有赖于是否具有在预算和其他约束条件下达到最优化的能力的工业界，有着决定性的影响(当然，工业中的“实际”问题往往是非线性的；使用线性规划有时候是由于估计的预算，从而简化了模型而促成的)。单纯形法是一种能达到最优解的精细的方法。尽管从理论上可以证明它是指数级而非线性的，但在实践中该算法是高度有效的——它本身说明了有关计算的本质的一些有趣的事情：理论和实践不一定完全一致。

在EDA领域，布局布线工具经常需要用到线性规划或者二次规划求解。

3. Krylov子空间迭代法

1950年，来自美国国家标准局的数值分析研究所的Magnus Hestenes, Eduard Stiefel和Cornelius Lanczos开创了Krylov子空间叠代法的研制。这些算法处理看似简单的求解形为Ax=b的方程的问题。当然隐藏的困难在于A是一个巨型的n*n 矩阵，致使代数解x=b/A 是不容易计算的(确实，矩阵的“相除”不是一个实际上有用的概念)。叠代法——诸如求解形为Kx(k+1)=Kx(k)+b-Ax(k)的方程，其中K 是一个理想地“接近”A 的较为简单的矩阵——导致了Krylov子空间的研究。以俄罗斯数学家NikolaiKrylov命名的Krylov子空间由作用在初始“余量”向量r(0)=b-Ax(0)上的矩阵幂张成的。当 A是对称矩阵时，Lanczos找到了一种生成这种子空间的正交基的极好的方法。对于对称正定的方程组，Hestenes 和Stiefel提出了称为共轭梯度法的甚至更妙的方法。过去的50年中，许多研究人员改进并扩展了这些算法。当前的一套方法包括非对称方程组的求解技巧，像字首缩拼词为GMRES和Bi-CGSTAB那样的算法。(GMRES和Bi-CGSTAB分别首次出现于1986和1992 SIAM journalon Scientific and Statistical computing(美国工业与应用数学学会的科学和统计计算杂志)。

在EDA领域，大部分问题都归结为线性方程组的求解，采用Krylov子空间迭代法是十分高效的算法。我在博士论文研究中，有一年的时间是在开发和改进基于Krylov子空间迭代法的数值算法，最终效果是把GMRES法在边界元素法的迭代次数大大减少，提高了整体运行效率。

4. 矩阵计算的分解方法

1951年，橡树岭国家实验室的A1ston Householder系统阐述了矩阵计算的分解方法。研究证明能把矩阵因子分解为三角、对角、正交和其他特殊形式的矩阵是极其有用的。这种分解方法使软件研究人员能生产出灵活有效的矩阵软件包。这也促进了数值线性代数中反复出现的大问题之一的舍入误差分析问题。(1961年伦敦国家物理实验室的JamesWilkinson基于把矩阵分解为下和上三角矩阵因子的积的LU分解，在美国计算机协会(ACM)的杂志上发表了一篇题为“矩阵逆的直接方法的误差分析”的重要文章。)

在EDA领域，涉及到矩阵分解的算法较多，凡是与矩阵处理相关的计算都需要用到矩阵分解。

5. Fortran最优编译程序

1957年，John Backus在IBM领导一个小组研制Fortran最优编译程序。Fortran的创造可能是计算机编程历史上独一无二的最重要的事件：科学家(和其他人)终于可以无需依靠像地狱那样可怕的机器代码，就可告诉计算机他们想要做什么。虽然现代编译程序的标准并不过分――Fortran I只包含23500条汇编语言指令――早期的编译程序仍然能完成令人吃惊的复杂计算。就像Backus本人在1998年在IEEE annals of theHistory of computing 发表的有关Fortran I，II, III的近代历史的文章中回忆道：编译程序“所产生的如此有效的代码，使得其输出令研究它的编程人员都感到吓了一跳。”

6. 矩阵特征值计算的QR算法

1959—61年，伦敦Ferranti Ltd.的J.G. F. Francis找到了一种称为QR算法的计算特征值的稳定的方法。特征值大概是和矩阵相连在—起的最重要的数了，而且计算它们可能是最需要技巧的。把—个方阵变换为一个“几乎是”上三角的矩阵――意即在紧挨着矩阵主对角线下面的一斜列上可能有非零元素――是相对容易的，但要想不产生大量的误差就把这些非零元素消去，就不是平凡的事了。QR 算法正好是能达到这一目的的方法，基于QR 分解，A可以写成正交矩阵Q 和一个三角矩阵R 的乘积，这种方法叠代地把A=Q(k)R(k)变成A(k+1)==Q(k)R(k) 就加速收敛到上三角矩阵而言多少有点不能指望。20世纪60年代中期QR 算法把一度难以对付的特征值问题变成了例行程序的计算。

在EDA领域，计算矩阵特征值也是一个常见的问题，例如 RCReduction问题。通过QR分解可以把比较困难的直接求解转换为迭代求解，有利于程序实现。

7. 快速排序法

1962：伦敦Elliott Brothers, Ltd.的Tony Hoare提出了快速(按大小)分类法。 把n个事物按数或字母的次序排列起来，表面上看起来是单调平凡的事，它的挑战在于发明一种快速完成排序的方法。Hoare的算法利用了古老的分割开和控制的递归策略来解决问题：挑一个元素作为“主元”、把其余的元素分成“大的”和“小的”两堆(当和主元比较时)、再在每一堆中重复这一过程。尽管可能要做受到严厉责备的做完全部N(N-1)/2 次的比较(特别是，如果你把主元作为早已按大小分类好的表列的第一个元素的话！)，快速排序法运行的平均次数具有O(Nlog(N))的有效性，其优美的简洁性使之成为计算复杂性的著名的例子。

在EDA领域，几乎所有的计算都涉及到排序，当然，并一定都用快速排序。比如DRC检查中，针对二维图形的排序常用的算法是x方向采用一种算法，y方向采用另外一种算法，使得效率最优。

8. 快速Fourier变换

1965年，IBM的T. J. Watson研究中心的James Cooley以及普林斯顿大学和AT＆T贝尔实验室的John Tukey向公众透露了快速Fourier变换(方法)(FFT)。应用数学中意义最深远的算法，无疑是使信号处理实现突破性进展的FFT。其基本思想要追溯到Gauss(他需要计算小行星的轨道)，但是Cooley—Tukey的论文弄清楚了Fourier变换计算起来有多容易。就像快速排序法一样，FFT有赖于用分割开和控制的策略，把表面上令人讨厌的O(N*N)降到令人欢乐的O(Nlog(N)) 。但是不像快速排序法，其执行(初一看)是非直观的而且不那么直接。其本身就给计算机科学一种推动力去研究计算问题和算法的固有复杂性。

9. 整数关系侦查算法

1977年，BrighamYoung大学的HelamanFerguson 和Rodney Forcade提出了整数关系侦查算法。这是一个古老的问题：给定—组实数，例如说x(1),x(2),...,x(n)，是否存在整数a(1),a(2),..,a(n) （不全为零），使得a(1)x(1)+a(2)x(2)+...+a(n)x(n)=0.对于n=2 ，历史悠久的欧几里得算法能做这项工作、计算x(1)/x(2)的分数展开中的各项。如果x(1)/x(2) 是有理数，展开会终止，在适当展开后就给出了“最小的”整数a(1) 和a(2)。欧几里得算法不终止——或者如果你只是简单地由于厌倦计算——那么展开的过程至少提供了最小整数关系的大小的下界。Ferguson和Forcade的推广更有威力，尽管这种推广更难于执行(和理解)。例如，他们的侦查算法被用来求得逻辑斯谛(logistic)映射的第三和第四个分歧点，b(3)=3.544090和 b(4)=3.564407所满足的多项式的精确系数。(后者是120 阶的多项式；它的最大的系数是257^30 。)已证明该算法在简化量子场论中的Feynman图的计算中是有用的。

10. 快速多极算法

1987年，耶鲁大学的Leslie Greengard 和VladimirRokhlin发明了快速多极算法。该算法克服了N体模拟中最令人头疼的困难之一：经由引力或静电力相互作用的N个粒子运动的精确计算(想象一下银河系中的星体，或者蛋白质中的原于)看来需要O(N*N)的计算量——比较每一对质点需要一次计算。该算法利用多极展开(净电荷或质量、偶极矩、四矩，等等)来近似遥远的一组质点对当地一组质点的影响，算法复杂度降到了O(N*logN)。快速多极算法的一个明显优点是具有严格的误差估计，这是许多算法所缺少的性质。

在EDA领域，九十年代中期，多极加速算法成功地应用于电容提取算法中，MIT开发的fastcap程序成为当时的主流算法。

看完上述10大算法，你是否觉得EDA领域的挑战对你足够的吸引力？愿意加入这个充满挑战性的领域吗？