计算机在点值和系数的空间来回计算，这是要有代价的。如果已知系数，要算一个点值，这是 N 数量级的工作量；把所有N个点值全算出来，则是 N2数量级的工作量。反之，如果已知点值，要把所有N个系数全算出来，也是 N2数量级的工作量。当 N 很大时，这是相当大的计算量，这不，如果 N = 100000，再平方一下，这数字太可怕了，而且，计算机的大量运算会产生误差积累，导致算出的结果不够精确。
能不能把 N2 降下来？能。快速傅立叶变换( FFT) 的思想其实很简单：仔细观察公式，发现有很多重复计算。在算点值时，打个比方（纯粹胡说）：第一个点，第四个点，第七个点。。。有重复计算。FFT 把重复计算的部分，一次性算好，然后在第一个点，第四个点，第七个点。。。同时使用。就这么点简单的思想，你只要把它做到极致，一个 N2 数量级的工作量就降到了N log N 数量级了，相比于 N，log N 是一个很小的数，几乎等同于常数。这，是一个革命性的创举。
FFT的第一篇文章，1965年发表在Mathematics of Computation , 这是美国数学学会的顶级杂志，也是非常古老的计算数学杂志。这篇FFT 论文的影响力是巨大的。
例二：快速多极法（fast multi-pole method）
这种方法是用来快速计算 N 个粒子之间两两相互作用的效果。比如，两两粒子间的引力作用。对一个固定的粒子来说，它的运动取决于它和其他所有粒子两两相互作用的效果之和。把这些相互作用都算清楚，需要 N 数量级的工作量。那么，要算好所有 N 个粒子的运动规律，则需要 N2数量级的工作量。
这次运气不好，和 FFT 不同，我们似乎找不到明显的重复运算 (除了两两相互作用只需算一次，这只能减少一半运算量，没法在数量级上减少)。但这难不倒数学家。数学家们发现，一个粒子和距离它较远的一堆粒子的相互作用，不用两两算清楚，只需要算这个粒子和这一堆粒子（看成一个大粒子）的相互作用，也就八九不离十了。当然，误差是多少，一堆粒子到底可以多大，如何定义 “较远”，这些都要分析清楚。这次没有办法像 FFT 一样得到和原来公式一样的数学效果，但是，如果给定能容忍的误差，比如千分之一，则上述的办法只需要 N log N 数量级的工作量。实际上，如果把算法和分析再做得精细些，工作量能降到 N 数量级。这种方法叫做“快速多极法”。
快速多极法的发明，归功于耶鲁大学的 V. Rokhlin和 L. Greengard。1985 年，他们发表在 Journal of Computational Physics 的一篇文章中，首创性地提出和分析了快速多极法。和FFT 类似，这个方法也在科学和工程中得到广泛的应用。因为这个工作，这两位数学家得到了美国数学学会 2001 年的一个重量级奖项 (the Leroy P. Steele Prize)。这项奖通常都是授予纯粹数学家的，应用数学家极少得到该奖，这也说明了快速多极法在数学和应用中的双重重要性。
例三：多重网格法（multigrid method）
怎样解大型的线性方程组
Ax = b
A是 N x N矩阵，b 是向量。这个问题看上去十分简单，用中学学到的Cramer’s Rule 就能得到解。不过，用Cramer’s Rule 的计算量是 N 的阶乘（N!）的数量级。当矩阵很大的时候，比如， N=1000， N! 是个非常庞大的数，不信你在计算器上摁一摁，会发现计算器都无法显示出这么庞大的结果。不管今天的计算机有多快，都无法在短时间内实现这样的计算。所以，Cramer’s Rule 在解大型的线性方程组时，只有理论上的意义，没有实际意义，纸上谈兵也。
用高斯消除法（Gaussian elimination）求解，可以将工作量从 N! 数量级降到N3数量级。这已经大大提高了计算效率。对一般的线性方程组，这经常是实际计算中唯一可行的方法。不过， N3还是实在太大了，数学家希望再进一步降低工作量。对于一些实际应用中的矩阵，有些特殊的性质，比如对称正定矩阵，何不利用一下？应用数学知识可以设计 N 数量级的算法，如果能如愿以赏，的确是美事一桩，故而发明了“多重网格法”。要知道，不是所有的矩阵都能采用多重网格法，矩阵需要满足特殊的性质。因为哪怕A是对角矩阵，求解也需要 N 数量级的计算，再也没有油水可榨了，N数量级已经达到了极限。
多重网格法的主要贡献者是以色列数学家Achi Brandt , 为此，2005 年，他得到了美国工业与应用数学学会(SIAM）和美国计算机学会 (ACM) 共同授予的 “计算科学和工程奖” (Prize in Computational Science and Engineering )，这是个非常了不起的大奖。
Thank you very much for the link, which looks amazing :)
I have put this link at the end of my article. If you are interested in Fourier series and Gibbs phenomenon, there is a review paper that you might be interested:
Swarm system are examples of decentralized systems, which depends on interaction and communications between each pair of entities. 快速多极法 is a good fit. Unfortunately, I could not show off here due to the nature of work.
