Introduction
1998年6月17日，为了纪念Mark 1计算机诞生50周年，Lloyd N. Trefethen 在英国曼彻斯特大学举行的“数字分析和计算机-五十年的发展”发表了演讲”Predictions for Scientific Computing Fifty Years From Now”。
1955 年出生的 Lloyd N. Trefethen 是牛津大学教授、英国皇家学会院士，前几年刚卸任美国工业与应用数学学会 (SIAM) 主席的位置，是一个很有国际影响的应用数学家。
本文将围绕着 Prof. Trefethen 20年前的对科学计算趋势的预测，尝试了解科学计算的历史和发展。
数值分析(Numerical analysis)或科学计算(Scientific computing)最早可以回溯到1948年。虽然在那个年代，数值问题是在纸上或通过与当今计算机几乎没有共同点的机械计算器解决的， 但一些至今仍在使用的算法那时就已存在。而随着计算机的迅速发展，科学计算中的算法也随之演进。
- 1940年以前：
- 牛顿迭代法
- 高斯消元法
- 高斯数值积分
- 最小二乘拟合
- Adams和龙格-库塔公式(求解常微分方程的多步法)
- 理查德森外推法
- 1940年-1970年:
- floating point arithmetic
- Fortran
- 有限差分法
- 有限元法
- FFT
- 单纯形法
- Monte-Carlo法
- 正交基/正交函数
- 样条函数
- 1970年-2000年：
- 拟牛顿法
- 自适应法
- 刚性ODE求解器
- 数学软件库
- Matlab
- 多重网格法
- 稀疏矩阵和迭代解法
- 谱方法
- 内点法（求解非线性凸优化问题）
- 小波分析
在Prof. Trefethen 的演讲中，对2000-2048这50年间的预测为：
- 语音和图像的普遍
- 完全自适应的智能数值算法
- “确定性”不复存在
- 更短时间内(O(N^2+ffl) ops)的线性方程求解器
- 多极子算法的发展
- 预条件矩阵、谱方法、数值PDE时间步离散上的研究突破
- 各程序平台的无缝衔接
- 人脑研究的应用于大规模并行计算
- 与自然选择思想相关的创新编程方法
Trefethen’s Predictions
Prof. Trefethen 的前4个预测会相对抽象一些，后几个预测则与具体的数值算法相关。
预测 1: 人类给计算机的“输入”将从 typing 转向 talking ，而计算机的“输出”将由数字(numbers)转向图形(pictures)。
在过去的20年中，图形化界面的面世已发生了巨大变化。1980年左右，我还在斯坦福大学读书时，Xerox公司给我们捐赠过部分早期的Altos工作站，它们带有窗口，图标，鼠标和指针，那时我认为这都是花架子。然而近些年，Altos的后代驱使其他机器灭绝。
得益于算力提升和深度学习的应用，发展迅速的模式识别(语音/图像)印证了这一预测。目前来看，直观的图形化输出仍在发展中，如刚刚结束的2020HPC大会中，数值天气分会场的其中一个述求就是如何将模式产生的数值计算结果实时转化为气象工作者能快速分析预测天气的气象图。数字化的理念，也是为了让上次应用的工程师们远离计算的细节，使得机器更加“人性化”。
预测 2: 数值计算将更具有自适应性、迭代性、灵活性和智能化，且算力惊人。
自适应计算是计算机时代的荣耀之一。高斯求积法是两个世纪前发明的，但是自适应求积法直到1960年代才问世。自适应ODE求解器很快出现，并将大多数常微分方程求解器变成了黑匣子的使用。偏微分方程尚未有黑匣子求解器，但趋势是朝这个方向发展。
对于一些常见的偏微分方程，得益于有限元法等算法的发展，现在已经有通用的分析软件，如Abaqus、Ansys和MSC等。
随着时间的流逝，由计算机智能管理的适应性变得越来越广泛。计算机不像人那样聪明，但计算机可以比我们更快地探索各种可能性。我们将告诉机器我们想要什么，而机器是一个位于数值方法百科全书上的智能控制系统，以难以理解的速度进行处理计算，直至达到所需的精度。物理现实的大部分内容将在我们眼前实时模拟，其影响远远超出了1950年的先驱们所能想象的范围，甚至会觉得使用“计算”这个词过于保守。当所有的计算都智能化的时候，如果一切都嵌入控制循环中，则数学格局将发生变化。如今天对我们意义重大的一个区别是线性和非线性问题之间的区别（广义上讲，线性问题可以一次解决，但非线性问题需要迭代），五十年后，若所有东西都被嵌入一个迭代循环中，这种差异将逐渐消失。出于同样的原因，当今正问题和反问题之间的巨大区别也将消失。
未来的高度智能化计算中，数学模型中的差异将可以被忽略，如计算机自动化地处理线性或非线性问题，正或反问题。
预测 3: 数值计算给出的结果并不具有“确定性”。
五十年后，在规定的精度下，尽管可以计算得到正确的答案，但如果你第二次进行此计算时，你将不确定是否会完全准确地复制这个计算结果。我不确定如何消除这种“确定性”的损失。在过去的五十年中，要传达给科学家和工程师的好消息是，要求数值计算的准确性是不合理的。在接下来的五十年中，他们将学会也不要求重复性。
随着复杂系统智能化的发展，重复计算并期望得到完全一模一样的计算结果是不现实的。这一点大家在机器学习的训练过程中可能会深有感受，我们不确定哪一组参数能取得较好的精度，且相同的参数是否在下一次的训练中依然保持这个精度。但大家并不会因此就放弃这类算法。
预测 4: 浮点运算的重要性不会降低。
五十年的变化很多，但仍能预测到一些连续性：我相信会持续的一件事是浮点运算。当然，细节会发生变化，尤其是字长将继续从16位扩展到32位，再到64位扩展到128位，甚至更多，这是因为计算序列变得越来越长，需要包容更多的误差传播，更高的准确性。但是我相信浮点算术的两个定义特征将继续存在：相对而不是绝对值，以及所有中间量的取整。
在数值分析社区之外，有些人认为浮点算术不符合时代特性，注定要在1950年代随着计算机功能越来越复杂而被淘汰。但即使计算机快到以进行任意符号计算，我们必须认识到：实际上，大多数数值问题都无法用符号方式解决，你必须进行近似，而浮点运算是有史以来最好的通用近似思想。
预测 5: 线性方程组的求解复杂度将降低至O(N^2 + \epsilon)。
计算机上，矩阵计算(如计算逆矩阵，行列式、求解线性方程组和求特征值/奇异值)所需的计算量基本为O(N^3)，而计算的输入量为O(N^2)。Strassen在1968年表明可以突破O(N^3)的计算量。他设计了一种递归算法，其运行时间为O(N^(log(2.7)))，大约为O(N^2.81)，随后由Coppersmith，Winograd和其他人进行了改进，使指数降低到2.376。但算法中涉及的常数太大，以至于它们实际性不好，对科学计算的影响很小。因此，许多数值分析领域的研究者认为加速矩阵计算只能得到理论，而没有实际应用。对于该领域中最突出的未解决问题，这是一种奇怪的态度！当然，可能有某些原因导致无法找到实用的算法，但是我们目前还不知道这一点。 复杂度为O((N^2)(log N)) 或 O((N^2)(log_2 N))的“矩阵快速求逆”是有可能的。 1985年，我与犹他大学的Peter Alfeld打赌，10年内将有人能证明：对于任何\epsilon > 0，矩阵算法的复杂度均为O(N^2 + \epsilon)。很遗憾并没有，我给Alfeld一张100美元的支票。但我们将赌约续到了2005年，如有必要我会接着续下去。我认为五十年应该足够长，也许有一天早晨，运气不错，会有个爆炸性地突破。
很遗憾Prof. Trefethen的打赌还没有赢，但近些年GPU的发展，矩阵计算的加速算法重新得到关注，虽然目前的侧重点是并行计算，但不排除会有创新性的结论出现。
预测 6: 多极子(multipole)算法将广泛应用。
共轭梯度法和Lanczos算法是在1950年左右发明的，它们的故事很奇怪。如今，我们毫无疑问地知道这些方法的优点：它们是矩阵迭代算法，对于某些矩阵，迭代使O(N^3)的计算复杂度降低到O(N^2)甚至更好。尽管“O”中隐藏有常量，但是当N大时，这些方法有时比高斯消去法及其相关方法要快得多。令人好奇的是，Hestenes, Stiefel, Lanczos 以及其他人都没有看到这种情况的到来。在1950年代，对于这些迭代算法而言，N太小而没有竞争力，但是所有数学理论都很完备。这些人知道迭代算法的收敛特性，足以预测最终随着机器的增长，迭代算法将击败直接求解算法。但是他们似乎没有做出这个预测。1960年有人对数值分析领域写了类似本文的文章，却根本没有提到共轭梯度法或Lanczos算法。考虑到这段历史，我提到了多极方法，用这种方法表示与Rokhlin和Greengard的最新算法有关的N体问题和积分方程有关的方法。时代变了，现在我们都渐近地思考。在1980年代发明多极子算法时，在2维问题中具有竞争力，但在3维问题却没有。但是Rokhlin和Greengard立即看到多极子算法将计算复杂度从O(N^2)减少到O(N)或O(N(log N))。那么从长远来看，他们怎么会不赢呢？所以他们会的。多极子算法的成功将成为一个普遍趋势。随着时间的流逝，大规模的数值计算甚至更多地依赖于近似算法，即使对于原则上可以在有限数量的步骤中精确解决的问题也是如此。近似算法比精确算法更稳定，而且奇怪的是，它们通常也更快。
在解决电大尺寸目标的电磁辐射与散射问题时，快速多层多极子算法是目前最好的算法，该算法将计算复杂度和存储量都降低到O(N(log N))。
预测 7: (i) 预条件矩阵、(ii) 谱方法、(iii) 数值PDE时间步离散上的研究突破。
这里的三个预测是示例。预条件矩阵至关重要，但这方面的研究仍是一片原始森林 —— 所以当然有改进的地方了！ PDE的谱方法处于相似的状态 —— 十分强大但还无法进行不同模型应用间的推广。关于时间步离散，对于ODE而言已经发展成熟，但对于PDE而言，仍然没有以一般的方式解决。时至今日，CFL条件仍限制着工程领域和科学计算：只能使用比我们期望的更小的时间步长，因此求解大规模的矩阵问题时代价昂贵，而另外一些物理量也因为数值上太难处理而被舍弃。 CFL条件的限制不会消失，但我们可以设计出新的武器与之抗衡。
预条件矩阵的研究现在是大型稀疏线性系统迭代法求解研究的重点。PDE时间步离散步长若可以增大，整体计算量将会减少，那么每一个时间步，就可以考虑更复杂更精确的数学物理模型。
预测 8: 无缝互操作的平台将会得到实现。
大家总是抱怨为什么要从白板到解决方案需要那么多人为干预？为什么必须为网格生成器编写一个计算机程序，为离散化编写另一个计算机程序，而为线性代数编写又一个计算机程序，这需要在整个过程中都需要接口，而人为错误的机会却又是重复的？为什么将符号和数值计算分开？为什么我们的想法和工具不能融合在一起形成一个无缝的互操作系统？好吧，当然可以，而且到达那里仅仅是一个工程问题。从现在开始的五十年里，人类将从这些中间步骤中消失了。网格和求解器将耦合在一起，人类在做科学的过程中将越来越少地看到实际数字。
和EDA领域的软件一样，用户都想要能有一个能快速上手的全家桶式的通用平台，这个工程问题需要大量的人力开发投入。
预测 9: 大规模并行计算的问题将被与人脑有关的思想吹开。
信息革命正在进行中。我们不知道它将带我们去何方，但旅程已经开始。相比之下，了解人类和其他高等动物的大脑如何工作的革命尚未到来。关于我们的科学前景的另一个事实是，大规模并行计算的问题已陷入僵局。几十年来，似乎似乎很清楚，最终，串行计算机必须在光速和原子大小的限制下运行，这时功率的进一步提高将通过大规模并行性实现。然而，如今的并行计算是一项笨拙的业务，陷入通信问题的困扰，远远没有十年前每个人所期望的那样先进。我相信并行计算的梦想将会实现。很难避免这样的思想：如果并行计算和人脑都在议程上，那么存储中的两次革命将以某种方式联系在一起。大脑研究人员将做出发现，这些发现将改变我们关于并行计算的想法。或并行计算的研究人员将进行发现，从而发现大脑的秘密；或者，这两个领域可能会同时发生变化，也许是在惊人的五到十年的剧变中。剧变可能从明天开始，或者可能不会在下一代开始。但是它注定会发生，到2048年，我希望并行计算和对大脑的理解将比现在有无与伦比的进步，并且彼此之间的联系会更加紧密。
借鉴生物神经系统信息处理模式和结构的计算理论、体系结构、芯片设计以及应用模型与算法的类脑计算领域或许会是突破之一。
预测 10: 人们的编程方式将被基因组和自然选择相关的思想所影响。
基因程序和计算机程序奇怪地相似。两者都是绝对精确的数字代码，我们所知的其他任何代码都不像这两个代码那样复杂，基因组的大小与智人的基因数量级大致相同（3 \ Theta 10 9核苷酸）。操作系统的大小（Windows 98为2 \ Theta 10 9位）。随着一代人的工程师成长为基因组学专家，以数字方式思考地球生命的演变，我们的计算机编程方法将发生变化。传统上，计算机程序是用不同于生物学程序的方式编写的。循环中有一个程序员，是一种智能，它使计算机程序具有生物学程序所缺乏的逻辑结构（更不用说注释卡了！）。但是，值得注意的是，如今，大型软件系统太大了，任何人都无法详细了解它，更不用说对其进行机械分析或验证了，事实上，工业软件设计的过程似乎已经接近自然发展的趋势。关于数学逻辑的选择。在像Microsoft这样的地方，软件是通过无休止的实验和测试，编码和纠正过程生成的，在此过程中，单个人的智能似乎不像以前那样重要。操作系统是从一代发展到下一代的，它们虽然不是完美的，但它们可以工作。对于计算机科学家来说，该过程似乎令人讨厌，但它是可伸缩且不可阻挡的。
大型软件系统中逻辑过于复杂以致于人们无法进行详细的了解分析，也许可以考虑将其作为一个整体，通过大量实验测试，让其间的数学逻辑进行物竞天择，进行编码和纠正。Prof. Trefethen版本的AI编程思想。
Prof. Trefethen提到，他的预测中不那么具体和技术的部分有一个共同的主题：人类将会从循环中移除。
- 通过语音和图形与计算机进行交互：在这种发展中，人类将越来越少接粗数字，计算机仍然可以使用数字，但是很少会向我们展示，因为总所周知，人类不擅长计算。
- 由智能控制系统管理的自适应计算：此处的重点恰恰是将人从循环中删除。人类负责提供所需使用的算法，FFT或GMRES，但不会被要求干预细节。
- 无缝的互操作平台：又是一个使人脱离细节参与的过程。到2048年，我们将不需要将网格数据器输入到求解器。
- 自然选择相类比的全新编程方法：不再人类程序员，而更多取决于自动探索和选择。正如人类在数字上不可靠一样，他们也不擅长编程。
I find I have envisioned a frightening future, a future in which humans, though still the taskmasters of computers, are no longer much involved in the details of getting the tasks done. Fifty years from now, it is hard to imagine that our machines will still be dim enough to benefit much from our assistance.
20年前和“人工智能替代人类”类似的顾虑。
Summary:
Prof. Trefethen的未来50年预测已经过去近一半，可以对工程和学术上的发展趋势有一个整体的对比。
References:
Trefethen L N. Predictions for scientific computing fifty years from now[J]. 1998.
