科学计算 (Scientific Computing)

发表时间：2020-08-09 17:58

常常碰到网友问我，什么是计算数学？什么是科学计算？这篇文章企图阐明数学在“科学计算”里的作用。

首先，什么是科学计算？在这方面有着不同的定义。在我看来，这应该是用数学作为工具，设计有效的算法，然后在计算机上实现。的确，科学计算和计算机科学有着紧密的联系，但不是一回事。科学计算着重于数学的角色，强调数学的作用。通过数学，保证设计方法的有效性，有足够的精确度，足够的稳定性，而且提高效率。

还是通过几个有名的例子来说明问题吧。

例一：快速傅立叶变换 (Fast Fourier transform, FFT)。

我想，这个方法大家都不陌生吧？在很多科学技术领域里，应用的那个部分里，都需要做傅立叶变换，事实上，当今世界上的计算机在运算的时侯，很多都在作快速傅立叶变换。这里，你就可以看到数学对它的贡献了。其实，这仅仅是初等数学，而且还是比较简单的数学。

一维空间：从 0 到 2π 之间，均匀地分布N 个点。

频谱空间：傅立叶级数展开。

傅立叶级数的系数和点空间之间是有关系的。这样说吧，如果你知道了这些点值，就能算出这些系数，反之，知道了这些系数，也能算出那些点值。

计算机在点值和系数的空间来回计算，这是要有代价的。如果已知系数，要算一个点值，这是 N 数量级的工作量；把所有N个点值全算出来，则是 N² 数量级的工作量。反之，如果已知点值，要把所有N个系数全算出来，也是 N² 数量级的工作量。当 N 很大时，这是相当大的计算量，这不，如果 N = 100000，再平方一下，这数字太可怕了，而且，计算机的大量运算会产生误差积累，导致算出的结果不够精确。

能不能把 N²降下来？能。快速傅立叶变换( FFT) 的思想其实很简单：仔细观察公式，发现有很多重复计算。在算点值时，打个比方（纯粹胡说）：第一个点，第四个点，第七个点。。。有重复计算。FFT 把重复计算的部分，一次性算好，然后在第一个点，第四个点，第七个点。。。同时使用。就这么点简单的思想，你只要把它做到极致，一个 N²数量级的工作量就降到了N log N 数量级了，相比于 N，log N 是一个很小的数，几乎等同于常数。这，是一个革命性的创举。

可以这么说，如果没有得益于快速傅立叶变换( FFT)的应用，各种信号处理，电子工程，绝对不会变得像今天这么广泛。FFT 在数学上是一个很简单的东西，这件事情之所以做得非常飘亮，就是在数学上并没有做新的事情，也没有改变原来的公式，思路也是简单的，只是把傅立叶公式算得很快，多快好省干革命。

FFT的第一篇文章，1965年发表在Mathematics of Computation , 这是美国数学学会的顶级杂志，也是非常古老的计算数学杂志。这篇FFT 论文的影响力是巨大的。

例二：快速多极法（fast multi-pole method）

这种方法是用来快速计算 N 个粒子之间两两相互作用的效果。比如，两两粒子间的引力作用。对一个固定的粒子来说，它的运动取决于它和其他所有粒子两两相互作用的效果之和。把这些相互作用都算清楚，需要 N 数量级的工作量。那么，要算好所有 N 个粒子的运动规律，则需要 N² 数量级的工作量。

这次运气不好，和 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! 数量级降到N³数量级。这已经大大提高了计算效率。对一般的线性方程组，这经常是实际计算中唯一可行的方法。不过， N³ 还是实在太大了，数学家希望再进一步降低工作量。对于一些实际应用中的矩阵，有些特殊的性质，比如对称正定矩阵，何不利用一下？应用数学知识可以设计 N 数量级的算法，如果能如愿以赏，的确是美事一桩，故而发明了“多重网格法”。要知道，不是所有的矩阵都能采用多重网格法，矩阵需要满足特殊的性质。因为哪怕A是对角矩阵，求解也需要 N 数量级的计算，再也没有油水可榨了，N数量级已经达到了极限。

多重网格法的主要贡献者是以色列数学家Achi Brandt , 为此，2005 年，他得到了美国工业与应用数学学会(SIAM）和美国计算机学会 (ACM) 共同授予的 “计算科学和工程奖” (Prize in Computational Science and Engineering )，这是个非常了不起的大奖。

向科学家们致以崇高的敬礼！