玻尔百科设想你是一位建筑大师，但你设计的不是建筑，而是计算。在建造一座宏伟的模拟摩天大楼之前，你必须了解材料的成本。你如何衡量所涉及的工作量？在科学计算中，我们的“配方”是算法，我们需要一个标准单位来量化其复杂性。这个根本性挑战——如何客观地衡量和比较算法效率——是设计更快、更强大的计算工具的核心。
本文将介绍浮点运算数（flop count），这是一种简单而深刻的计算“硬通货”。通过学习计算“浮点运算”，你将获得一个分析算法性能的强大视角。我们将探讨这一概念背后的核心原理和机制，从多项式求值等简单示例开始，逐步转向求解线性方程组这一核心问题。你将发现不同的算法策略，例如高斯消元法与稀疏矩阵方法，如何导致截然不同的计算成本。此外，我们还将考察浮点运算数统计的深远应用和跨学科联系，了解它如何塑造从天体物理学到人工智能的整个领域，并如何将抽象算法与计算机硬件的物理极限联系起来。读完本文，你不仅将理解如何计算操作次数，还将明白这项技能如何揭示计算问题求解的深层结构。
设想你是一名厨师，任务是准备一席盛宴。衡量工作量的一种方法是计算你切菜、搅锅或量取配料的次数。这些是你的基本操作。如果一份食谱需要100次这样的操作，而另一份需要10000次，你就能很好地判断哪一份更复杂。你也知道，一个巧妙的技巧——也许是不同的切菜方式或一台能自动搅拌的机器——可以显著减少操作次数，让你更快、更高效地准备宴席。
在科学计算的世界里，我们的“配方”是算法，而我们的“基本操作”是计算机执行的基础计算。为了理解和比较这些算法的效率，我们需要一种方法来计算这些操作。这就是浮点运算数背后简单而深刻的思想。
浮点运算（FLoating-point OPeration，简称flop）是我们计算成本的标准单位。它通常代表对浮点数（可以有小数部分的数，如3.14159或-0.00271）执行的单个基本算术运算。我们将一次加法、一次减法、一次乘法或一次除法计为一次浮点运算。通过统计一个算法所需的浮点运算总数，我们得到了一个标准化的计算成本度量，这个度量独立于运行它的具体计算机。
当然，这是一个模型，就像物理学中任何好的模型一样，它简化了现实以揭示更深层次的真理。在真实的计算机上，一次除法可能比一次加法耗时稍长，但为了一个清晰、通用的框架，我们忽略了这一点。有时，甚至对计数的定义也可能有所不同。例如，考虑一下优美而高效的回代过程，当矩阵已经是整洁的上三角形式时，它被用来求解线性系统。
一种常见的浮点运算计数方法是统计所有必要的乘法、加法和除法，得出的总数恰好是次浮点运算（对于一个的系统）。一个更严谨的会计师可能会坚持计算形式算法中指定的每一次操作，包括可能从零开始的减法。这种更严格的计算得出的总数略有不同，为次浮点运算。这种差异重要吗？对于计算机科学家来说，可能重要。但对我们而言，它揭示了一个更重要的教训：虽然精确的系数可能因我们的假设而异，但主导项保持不变。成本随问题规模呈二次方增长。这种伸缩行为是复杂度分析的灵魂。
在处理庞大的方程组之前，让我们先用一个更熟悉的东西热身：多项式。假设我们想要求值。一种直接的方法是先计算的所有幂（），然后进行乘法运算（），最后将所有项相加。如果你仔细计算操作次数，这种“直接”方法的成本是次浮点运算。
但灵光一现便能揭示一种更优雅的方式。我们可以将多项式重写为嵌套形式：
这就是Horner方法。它看起来像一个简单的代数技巧，但在计算上却有天壤之别。我们从最内层开始——将乘以再加上——然后向外计算。每一步只涉及一次乘法和一次加法。由于有个这样的步骤，总成本仅为次浮点运算。
次浮点运算的差异看似微不足道。但如果你的任务是在信号处理芯片内每秒对这个多项式求值数百万次，这个看似微小的改进将转化为速度和效率上的巨大提升。这是我们第一次清楚地体会到，一个巧妙的视角转变如何能带来一个更优越的算法。
现在我们转向科学和工程中的一个核心问题：求解一个包含个未知数的个线性方程组，紧凑地写作。我们在学校都学过的首选方法是高斯消元法，它系统地将矩阵变换为上三角形式。
如果我们深入观察这个过程对一个通用的“稠密”矩阵（其中大多数元素非零）的操作，我们会发现一个由三个嵌套循环构成的强大结构。外层循环选择一个主元行，中间循环遍历其下所有待修改的行，最内层循环更新这些行中的每个元素。这种三重嵌套是该算法成本的来源。当我们计算浮点运算次数时，发现总数与成正比。一个常见的近似值是次浮点运算。
这种的伸缩性，我们可称之为“立方墙”。如果你将问题规模从翻倍到，操作次数不是翻倍或四倍，而是增加了八倍！一个需要一分钟解决的问题，如果你改进模型，可能需要八分钟，再次改进则可能超过一个小时。
但如果我们的矩阵具有特殊结构呢？我们已经看到，如果是上三角矩阵，我们可以使用回代法，成本仅约为次浮点运算。这是一个巨大的改进——便宜了整整一个数量级。这就是为什么高斯消元法的第二阶段被认为是“容易”的部分。困难的工作，即的部分，在于首先将矩阵化为三角形式。
如果我们的矩阵不仅是三角矩阵，甚至更简单呢？在许多物理问题中——如模拟杆上的热流、建筑物中的振动或电路——方程具有局部特性。一个点的值只直接依赖于其紧邻的点。这产生了稀疏矩阵，其中大部分元素为零。
一个经典的例子是三对角矩阵，其中非零元素只出现在主对角线和相邻的两条对角线上。对这样的矩阵应用通用的高斯消元法将是极其浪费的，因为它会执行无数次与零的运算。一个更聪明的方法是使用一个了解稀疏性的算法。Thomas算法正是这样一种方法：一个为三对角系统量身定制的高斯消元法版本。
通过考虑零元素，三个嵌套循环坍缩为简单的单循环。前向消元和后向回代过程各自需要的操作次数仅与成正比。总成本仅为次浮点运算。
从到的飞跃不仅仅是数量上的改进，而是质的飞跃。它改变了计算上可能实现的范畴。让我们做一个思想实验。假设在你的计算机上求解一个大小为的三对角系统仅需0.016秒。如果你要用一个通用的解法器求解一个同样大小的稠密系统，需要多长时间？成本比率大约是。代入数字，估计时间超过1600秒——将近半小时。通过利用稀疏结构，我们把一个不切实际、需要喝杯咖啡等待的计算，变成了一个瞬时完成的计算。这就是智能算法的力量。
像高斯消元法这样的直接方法，能在可预测的步数内给出精确答案（在机器精度范围内）。但对于真正巨大的稀疏系统，即使是的成本也可能过高，或者我们可能有理由不修改矩阵。这时，我们可以转向一种不同的哲学：迭代方法。
其思想之美在于其简单性：从一个对解的合理猜测开始，然后应用一个规则来迭代地改进这个猜测。每一步都使近似解更接近真实解。
Jacobi方法是一个经典的例子。更新解的第个分量的规则是，重新排列第个方程，并对所有其他分量使用你上一次猜测的值。关键的洞见在于，这样一次迭代的成本不取决于总规模，而取决于矩阵中非零元素的数量。对于一个每行平均有个非零元素的稀疏矩阵，一次完整的迭代成本约为次浮点运算。如果矩阵非常稀疏（），这个成本是极其低廉的。
一个近亲是Gauss-Seidel方法。它遵循同样的原则，但有一个小小的转折：当你计算解向量的新分量时，你会立即在同一次迭代中将其用于剩余分量的计算。这通常有助于解更快地收敛。但这里有一个有趣的事实：如果你只计算浮点运算次数，一次Gauss-Seidel迭代的成本与一次Jacobi迭代完全相同。实际的差异在于收敛速度以及算法在并行计算机上实现的难易程度。
当然，迭代方法也有一个问题：它们真的会收敛到正确的答案吗？幸运的是，我们可以检查一些条件。最简单的之一是严格对角占优，对于许多问题，这个条件保证了收敛。对于一个三对角矩阵，验证这个条件大约需要次浮点运算。与一次Jacobi迭代的约次浮点运算相比，我们看到，在启动一个可能长时间运行的迭代过程之前，检查这个条件是一项非常廉价的保险策略。
我们已经看到了一系列浮点运算数：、、、、。为了理解这一切，我们使用大O表示法。这种表示法捕捉了当问题规模变得非常大时，算法的主要伸缩行为。它告诉我们宏观的图景。因此，和都被描述为（“n阶”）。常数因子对性能很重要，但它们本质上都是线性的。类似地，是（“n平方阶”）。
这种语言有助于将算法划分为广泛的复杂度家族。这个思想是如此基础，以至于它在基础线性代数子程序（BLAS）中被形式化，BLAS是一个标准的计算核心库，构成了大多数科学软件的基石。BLAS分为三个级别：
级别1 (BLAS-1)：向量-向量运算。 这些包括点积或两个向量相加等。它们需要的数据并执行次浮点运算。
级别2 (BLAS-2)：矩阵-向量运算。 这包括矩阵乘以向量。对于一个的矩阵，这需要的数据并执行次浮点运算。
级别3 (BLAS-3)：矩阵-矩阵运算。 经典例子是两个矩阵相乘。这需要的数据（矩阵有个元素），但执行高达次浮点运算。
这个层次结构揭示了最后一个美妙的洞见。最高效的操作是级别3中的操作，并非因为它们在绝对意义上“更快”（它们成本最高！），而是因为它们具有最高的计算与数据访问比。在现代计算机上，将数据从内存移动到处理器通常比算术本身是更大的瓶颈。级别3的操作为它们加载的每一片数据执行大量的计算。它们对数据“咀嚼”很长时间。通过将像高斯消元法这样的复杂算法构造成尽可能多地使用级别3 BLAS操作，我们可以实现令人难以置信的性能。
因此，计算浮点运算次数这个简单的行为，为我们打开了一扇通往算法深层结构的窗户，揭示了蛮力与优雅、可能与不可能之间的区别，并最终将数学的抽象世界与计算机架构的物理现实联系起来。
设想你是一位建筑大师，但你设计的不是建筑，而是计算。在建造一座宏伟的模拟摩天大楼，或一座流畅、优雅的算法之桥之前，你必须了解材料的成本。每根梁、每个接头、每个连接需要多少精力？在计算世界里，我们精力的基本货币是“浮点运算”——一次简单的算术行为，如加法或乘法。“浮点运算计数”的艺术远不止是简单的记账。它是解锁对计算效率深刻理解的钥匙，揭示了优雅算法中隐藏的美丽和笨拙算法中蛮力的粗糙。它是我们窥探问题解决核心的定量透镜，从抽象到天体物理学。
科学计算的中心是一系列强大的工具，其中许多来自线性代数的世界。物理学、工程学和数据科学中的问题常常被转化为矩阵和向量的语言。我们如何操作这些对象决定了我们的计算是在几秒钟内完成还是在几个世纪内完成。
考虑求解线性方程组这个基本任务。像LU或QR分解这样的方法是完成这项工作的主力。如果我们为一个通用的、稠密的矩阵仔细计算操作次数，我们会发现成本与成正比。对于一个小的矩阵，这可能意味着几十次操作。但将问题规模加倍并不会使工作量加倍，而是乘以八！这个立方伸缩定律是一个严厉的警告：对于大问题，一个幼稚的方法很快就会在计算上变得不可行。不同的分解方法，如Householder QR分解，有其特定的成本公式，但对于稠密矩阵，它们通常都具有这种具有挑战性的特性。
这正是算法设计艺术的起点。一位杰出的算法开发者，就像一位聪明的物理学家，会寻找隐藏的对称性和结构。如果矩阵不只是随机数字的组合呢？如果它有特殊形式呢？例如，一个秩一矩阵可以写成两个向量的“外积”，。一个天真的人会先计算的所有个元素，然后将其乘以向量，这个过程的运算次数与成正比。但一个聪明的人，利用乘法的结合律，会将计算为。这个简单的重排改变了计算方式。我们不是构建一个大矩阵，而是计算一个单一的数字（点积），然后缩放一个向量。成本从一个的过程骤降到一个的过程。效率上的这一飞跃是对识别矩阵简单底层结构的回报。
这一原则是一个反复出现的主题。著名的用于寻找特征值（系统的特征振动）的QR算法，是计算策略的多阶段杰作。直接攻击一个稠密矩阵的成本将是高得令人望而却步的。取而代之的是，第一个也是成本最高的阶段是将矩阵转换为一种简单得多的形式——对称矩阵变为三对角矩阵，而一般矩阵则变为“Hessenberg”形式（准三角）。这个初始约简是一个的投资。但它带来了丰厚的回报。后续的迭代QR步骤，现在应用于这个高度结构化的矩阵，成本大大降低——每次迭代仅需甚至。这里的浮点运算计数揭示了一个关键的计算策略教训：识别你计算中成本最高的部分——“主要成本”——并将你的聪明才智集中在那里。其余的都是次要的。
浮点运算计数的实用性远远超出了矩阵运算这个井然有序的世界。考虑寻找复杂方程根的任务，这是从工程到经济学等领域的一个常见问题。我们有各种各样的迭代算法来解决这个问题，每种算法都有其独特的个性。
牛顿法是一个经典方法，它收敛速度快，但每一步都需要计算函数及其导数。Müller法是一个更复杂的近亲，它使用抛物线来逼近函数，并且通常收敛得更快。但这种额外的复杂性是有代价的。仔细的浮点运算计数表明，Müller法单次迭代的成本可能显著高于牛顿法的一次迭代。哪一个更好？答案不仅仅是“每次迭代浮点运算次数更少的那个”。真正的计算效率是每次迭代的成本与达到解所需的迭代次数的乘积。浮点运算计数提供了这个谜题的第一块，迫使我们思考通往解的整个路径，而不仅仅是单一步骤。
现在，让我们进入大规模科学模拟的领域，在这里我们的方程描述了诸如机翼上的气流或电磁波的传播等现象。这些问题在离散化后，通常会产生巨大的线性方程组。如果我们要为一个有一百万个变量的问题处理一个稠密矩阵，仅其存储就需要比任何计算机拥有的内存都多的空间。幸运的是，由物理定律产生的矩阵几乎总是稀疏的——它们几乎所有的元素都是零。相互作用是局部的。
这种稀疏性是大自然的馈赠，我们必须设计能够利用它的算法。像BiCGSTAB（双共轭梯度稳定方法）这样的迭代方法正是为这种情况设计的。当我们计算这种方法一次迭代的浮点运算次数时，我们发现一个优美的结果：成本不与成正比，而是与（矩阵中非零元素的数量）成正比。这完全改变了游戏规则。计算成本现在与物理相互作用的复杂性相关，而不是问题域的纯粹大小。这正是使物理世界的大规模模拟成为可能的原因。
在最宏大的尺度上，浮点运算计数不仅帮助我们选择算法，它还塑造了整个科学学科的架构。
以天体物理学中宏伟的N体问题为例：模拟星系中数百万或数十亿颗恒星的引力之舞。最直接的方法，即直接求和法，是计算每对粒子之间的引力。对于个粒子，这意味着大约次相互作用。对每次两两相互作用的详细浮点运算计数显示，这个数字不大，也许大约是20次浮点运算。但是的伸缩性是致命的。对于一百万颗恒星（），这意味着每个时间步有次相互作用。如果每次相互作用花费20次浮点运算，我们每个步骤就需要次浮点运算。一台每秒能执行一万亿次浮点运算（teraflop，）的超级计算机，仍然需要20秒才能完成一个微小的时间步。模拟一个星系的生命周期变得不可能。在这里，浮点运算计数不仅仅是成本的度量，它是不可行性的证明。它成为推动更先进、分层算法如树形码和快速多极子方法革命性发展的根本动机，这些方法将复杂度从降低到甚至，将不可能变为常规。
最近的一场革命发生在人工智能领域。现代深度学习的成功，特别是在计算机视觉方面，是建立在一个深刻的架构洞见之上的，而浮点运算计数阐明了其重要性。想象一下，试图用一个“全连接”神经网络层来处理图像，其中输出的每个像素都依赖于输入的每个像素。对于一个中等大小的图像，连接的数量——因此，参数和浮点运算的数量——变得天文数字般巨大。卷积神经网络（CNN）通过强制执行从物理学和感知中借鉴的两个原则来提供解决方案：局部连接性（一个输出像素只依赖于一小块输入像素）和权重共享（在整个图像中使用相同的模式检测器）。浮点运算计数的比较是惊人的。用卷积层替换全连接层，操作数量不是减少一小部分，而是减少了几个数量级。随着图像尺寸的增长，参数和浮点运算的节省比例都接近100%。这里的浮点运算计数不仅显示了一种优化，它揭示了使现代深度学习在计算上可行的赋能技术。
到目前为止，我们一直将浮点运算视为抽象的数学单位。但我们的计算运行在由硅和导线构成的物理机器上，这些机器遵守物理定律。这种思维方式的最终，也许也是最深刻的应用，是将我们抽象的浮点运算计数与计算机的具体性能联系起来。这引导我们走向“Roofline模型”，一个解释了计算实际极限的优美概念。
现代处理器有两个关键性能特征：其峰值计算速度（），以每秒浮点运算次数（FLOPs）衡量；以及其内存带宽（），即它从主内存获取数据的速率，以每秒字节数衡量。哪一个是瓶颈？答案取决于算法的*算术强度*（），定义为总浮点运算次数与从内存移动的总字节数之比。它提出了一个简单的问题：对于我们检索的每一个字节的数据，我们执行了多少有用的工作？
考虑求解泊松方程，这是计算物理学的基石。我们可以使用一种“无矩阵”的有限差分法，它使用局部模板动态计算结果。通过巧妙地将问题的一小块加载到处理器快速的本地缓存中，我们可以在获取新数据之前对这些数据进行大量计算。这种策略最大化了数据复用，并导致了高算术强度。或者，我们可以使用一种有限元方法，它涉及将一个巨大的稀疏矩阵乘以一个向量。在最坏的情况下，这涉及到在内存中流式传输，每执行两次浮点运算就要读取一个矩阵元素和一个向量元素，导致算术强度非常低。
Roofline模型告诉我们，可达到的性能是处理器峰值速度和内存系统所允许的性能的最小值：。如果一个算法的算术强度低，它就是“内存受限”的；处理器大部分时间都在等待数据。如果它的强度高，它就是“计算受限”的；处理器是瓶颈。分析表明，巧妙的、缓存分块的、无矩阵的方法在实践中可以快好几倍，不是因为它执行的浮点运算更少，而是因为它与机器的物理现实更和谐。它明白，移动数据通常远比在其上进行计算要昂贵得多。
从计算一个微小矩阵中的算术，到指导星系模拟的架构设计，再到理解超级计算机的物理性能极限，浮点运算数的概念是一条金线。它是一个具有深刻洞察力的工具，教导我们计算中的效率，如同万物一样，来自于对结构、策略以及我们所处世界基本法则的深刻理解。