玻尔百科在科学计算中，许多基本问题——从模拟星系到设计新药——都受到“二次方缩放诅咒”的困扰。这一计算障碍，即计算量随系统规模的平方（）增长，长期以来限制了研究的范围，使得大规模模拟的成本高得令人望而却步。本文旨在应对这一关键挑战，探索近线性复杂度算法的世界，这些数学捷径已将不可能变为常规。您将理解这些强大方法背后的基本原理，并见证其带来的变革性影响。首先，“原理与机制”一章将解构二次方问题，并揭示快速傅里叶变换和层次化方法所提供的优雅解决方案。随后，“应用”部分将展示这些算法如何成为从基因组学到计算电磁学等领域不可或缺的工具，开启了新的发现前沿。
要领会近线性算法的天才之处，我们必须首先面对它们旨在屠戮的恶龙：二次方缩放的诅咒。这个怪物源于一个简单、看似无害的想法：要理解一个系统，你必须考虑每个部分如何与其他所有部分相互作用。
想象你是一位天文学家，任务是模拟一个包含一百万颗恒星的星系。每颗恒星都通过引力作用于其他所有恒星。要计算单颗恒星所受的合力，你必须将其他 999,999 颗恒星的引力相加。要让整个星系在时间上前进一小步，你必须对所有一百万颗恒星重复此计算。总计算次数大约是一百万乘以一百万，即 ——一万亿次相互作用。一台现代计算机可能需要数小时或数天才能完成这单一步骤。要模拟星系长达数十亿年的宏伟舞蹈，根本是不可能的。
这就是二次方缩放问题，通常表示为 复杂度。计算量随元素数量 的平方增长。这个问题并非引力所独有。在科学界模拟具有长程相互作用的系统时，它无处不在。计算复杂蛋白质中的静电力、模拟设备中的磁场、或分析音乐厅的声学特性，都会导致相同的数学结构：系统中的每一点都影响其他所有点。
当我们将这些物理问题转化为线性代数的语言时，情况同样严峻。这些系统通常由矩阵方程 描述。矩阵 包含了每个元素如何与所有其他元素相互作用的信息。对于 个元素，这个矩阵的大小是 。如果所有相互作用都很重要，就像引力或电磁学那样，这个矩阵就是稠密的——几乎没有零元素。仅仅存储这个矩阵就需要 的内存，对于 ，这大约是 8 TB。使用高斯消元法等直接方法求解该系统需要 次操作，即使是迭代方法，每一步通常也需要耗费 的矩阵向量乘积。几十年来，这堵“二次墙”限制了科学家们敢于梦想解决的问题的规模。
二次墙上的第一道主要裂缝来自数学领域一个美丽的发现，一条如此深刻的捷径，以至于现在它支撑着大部分现代技术。关键在于注意到，这些 问题中有些具有特殊的、规则的结构。它们是卷积。
想象一下对图像应用模糊效果。新图像中每个像素的颜色是旧图像中其邻近像素的加权平均值，并且处处使用相同的加权模式（即“核”）。这就是一个卷积。直接计算的复杂度是 ，其中 是像素数量。然而，卷积定理提供了一个不可思议的替代方案：实数空间中的卷积等同于傅里叶空间中简单的逐元素相乘。
这意味着你可以获取你的数据（图像）和你的相互作用规则（模糊核），将它们都转换到频域，然后将它们相乘——这个操作只需要 的时间——最后再将结果转换回来。问题在于，用于此转换的工具——离散傅里叶变换（DFT）——本身就是一个 的过程。真正的革命是快速傅里叶变换（FFT）的发明，这是一个惊人的算法，它仅用 的时间就能计算出相同的变换。
FFT 是如何实现这一魔力的？它使用了一种称为分治的策略。为了计算一个大小为 的序列的变换，FFT 巧妙地将其分解为两个大小为 的问题，递归地解决它们，然后用额外的 工作量将结果合并。这个过程的递推关系式看起来像是 。如果你将其画成一棵树，你会发现每一层递归的工作量是相同的，大约是 。在问题变得微不足道之前，你需要下降的层数大约是 。因此，总工作量是每层的工作量乘以层数：。这个对数因子增长得非常缓慢，以至于在所有实际应用中，该算法感觉几乎是线性的。
FFT 是一次范式转变，但它有一个主要限制：它要求数据存在于规则的、结构化的网格上，就像图像中的像素一样。然而，我们的恒星散布在宇宙中，完全不考虑整齐的笛卡尔网格。我们需要一个新的想法。
下一个伟大的突破并非来自数学恒等式，而是源于一种深刻的物理直觉：远处物体的影响可以被近似。
让我们回到我们的星系模拟。从地球上，你无法分辨仙女座星系中的单个恒星；你看到的是它们汇集在一起、模糊不清的光。仙女座星系对我们太阳系的引力可以非常精确地计算出来，方法是将其数十亿颗恒星视为一个位于其质心的单一点质量。你不需要累加十亿个单独的力。
这就是快速多极子方法（FMM）和层次矩阵（-Matrices）的核心思想。我们可以将所有相互作用分为两类：
为了系统化地做到这一点，我们构建一个层次结构。想象一下将你所有的粒子放入一个大盒子中。然后，你将那个盒子分成八个更小的子盒子（在三维空间中），并不断递归地划分盒子，直到每个最小的盒子只包含一个或几个粒子。这就创建了一个名为八叉树的数据结构。
现在，为了计算某个粒子上的力，你“遍历”这棵树。对于树中的任何给定盒子，你问一个简单的问题：这个盒子是否足够远？这个规则被称为容许性条件：如果一个盒子的大小与其到我们粒子的距离相比很小，那么它就“足够远”。如果是，我们就不再看盒子内部。取而代之的是，我们对盒子内整个粒子簇使用一个近似。在物理学中，这个近似是一个多极子展开——对该粒子簇产生的场的紧凑描述，就好像它是一个位于簇中心的更复杂的单一源。如果盒子不够远，我们就查看其内部更小的子盒子，并重复这个问题。最终，我们到达了邻近粒子的层次，这时我们直接进行计算。
通过用一个单一、高效的近似来取代大量的单个远场计算，总计算成本从 骤降至 甚至 。
同样是层次化近似的思想，可以被转换成线性代数的语言，从而产生了层次矩阵（或 -矩阵）的优美结构。回想一下边界元法（BEM）模拟中那个稠密的 矩阵。我们可以根据我们的粒子层次树将这个矩阵划分为块。
“低秩”是什么意思？它意味着整个矩阵块中的信息是冗余的。一个大的 块，本应包含 个数字，可以被精确地表示为一个高的、瘦的 矩阵和一个短的、宽的 矩阵的乘积，其中 是秩，且远小于 。存储这两个较小的矩阵只需要 个数字，而不是 。这种方法对于像引力或静电学这样的核函数之所以如此有效，其数学原因在于，良好分离的群体之间的相互作用基本上是平滑的，而平滑函数可以被这种可分离形式以惊人的效率近似 [@problem-id:3437060]。
对这些 -矩阵进行操作的算法，比如求解 ，然后在这个块结构上递归执行，从而得到我们之前看到的相同的近线性复杂度。-矩阵不仅仅是一种数据结构；它更是对物理学的一个深刻陈述：稠密相互作用矩阵中的 个数字，大多数都不是独立的信息片段。系统的真实信息内容更接近于 。
这段旅程远未结束。近线性算法的原理很简单，但它们的实现是一门必须尊重底层物理的艺术。
在波问题中，如雷达或声学，由亥姆霍兹方程所支配，出现了一个引人入胜的挑战。相互作用核不是平滑和衰减的，而是振荡的，像 。对于高频（大的 ），这种振荡变得非常剧烈。一个简单的多极子展开已不再足够；近似还必须知道波的方向。标准的 FMM 和 -矩阵方法会遭受“高频击穿”，其性能会退化回 。解决方案是将方向性构建到近似中，使用像平面波展开这样的工具，从而产生复杂的方向性快速方法，即使在这种具有挑战性的情况下也能保持近线性缩放。
此外，这些方法的基础——近场和远场之间的区分——至关重要。如果容许性条件过于宽松，你错误地将一个近场相互作用当作远场来近似，你就会在你的矩阵中引入一个巨大的误差。这个看似微小的错误可能会产生灾难性的后果，污染整个计算，并导致用于求解的迭代求解器（如 GMRES）停滞不前并失败。构建鲁棒的算法不仅需要聪明的近似，还需要仔细的误差控制，有时使用自适应的、自我修正的程序来证明每个近似都是安全的。
从 的暴政到 FFT 和层次化方法提供的优雅逃逸，近线性复杂度的故事是人类智慧的证明。它展示了深刻的物理直觉与强大的数学和算法思想相结合，如何将曾经被认为不可能的问题转变为现在可以在笔记本电脑上常规执行的计算，为科学发现开辟了广阔的新天地。
数字中存在着一种暴政。如果你想计算一千颗恒星的引力之舞，你可能会认为你需要计算每颗恒星对其他所有恒星的引力。这大约是五十万次计算。如果你有一百万颗恒星，这个数字会爆炸到五千亿。这就是“二次墙”，即 复杂度的诅咒，其中所需的工作量随着项目数量 的平方而增长。很长一段时间里，这堵墙是不可逾越的障碍，将我们最雄心勃勃的模拟限制在玩具大小的问题上。它似乎是自然界对任何相互作用的部件系统征收的一种基本税。
但事实证明，自然界充满了捷径。通过物理学、数学和计算机科学的美妙结合，我们已经学会了利用它们。那些打破二次墙的算法，通常以“近线性”时间——如 ——进行缩放，它们不仅仅是巧妙的编程技巧，更是关于我们世界结构的深刻陈述。它们是现代科学计算背后的引擎，是让我们能够处理规模惊人的问题的基本工具。这就是那个巧妙捷径的故事，以及它如何在整个科学版图上开启了新的发现世界。
让我们回到我们的一百万颗恒星。你真的需要计算遥远的仙女座星系中每一颗恒星对我们太阳的引力吗？当然不需要。从我们的视角看，整个星系的综合引力几乎等同于一个位于其中心的超大质量恒星的引力。这种简单而深刻的直觉——即远处的物体群可以被视为一个单一实体——是一类革命性算法的核心，其中最著名的是快速多极子方法（FMM）。
FMM 不是采用蛮力的、全对全的计算，而是构建了一个层次化的簇群。近邻物体之间的相互作用被直接计算，保留了其所有复杂的细节。但远处簇群之间的相互作用则使用一种压缩表示来近似，这是一种对其集体影响的“执行摘要”。这种分而治之的策略将复杂度从 削减到近线性。
这一个想法在截然不同的领域中产生了回响。在计算电磁学中，设计雷达系统或隐形飞机的工程师需要求解电磁波如何从复杂物体上散射。其底层物理学涉及到物体表面的每个部分与所有其他部分的相互作用。一种天真的方法会撞上二次墙。多层快速多极子算法（MLFMA），FMM 的一个近亲，通过将相邻表面片之间的“近场”喋喋不休与可以通过多极子展开的层次化分组高效处理的“远场”广播分离开来，解决了这个问题。根据波的频率，其复杂度是惊人的 或 。同样的原理让我们能够模拟计算声学中的声波，无论是优化音乐厅的声音，还是消除喷气发动机的噪音。物理学变了，但捷径的数学艺术保持不变。
这个原理也可以向下扩展。在计算化学中，模拟蛋白质的行为或设计新药需要计算数百万个原子之间的静电力。这里使用了一种不同但相关的捷径：粒子-网格-埃瓦尔德（PME）方法。PME 巧妙地将问题一分为二。短程力被直接计算，这是一个 的任务，因为每个原子只有少数几个直接邻居。然而，长程力是平滑和缓和的。它们不是逐对计算，而是被插值到一个规则的网格上。在这个网格上，问题变成了一个简单的卷积，可以使用快速傅里叶变换（FFT）——有史以来最重要的 算法之一——以惊人的速度解决。这种混合方法是现代分子动力学的主力，使得在曾经纯属幻想的尺度上模拟生物机器成为可能。
近线性思维的力量并不仅限于模拟物理世界；它在构建我们的数字世界中同样至关重要。思考一下编译器设计的艺术。当你编写一个计算机程序时，编译器的任务是将其翻译成机器指令，并对其进行优化。为此，它必须首先理解程序的结构，特别是其循环。一个强大的工具是寻找“支配点”——即程序控制流图中位于从起点到某个其他点的每条路径上的节点。著名的 Lengauer-Tarjan 算法可以在一个有 条边和 个节点的图中，在 时间内找到所有支配点，其中 是反阿克曼函数。这个函数增长得极其缓慢，以至于对于任何你可以在计算机上存储的图，它的值都小于 5。在所有实际应用中，该算法是线性的。这使得编译器能够以闪电般的速度分析和优化即使是最庞大和最复杂的软件项目。
或者想想现代计算机芯片的奇迹，数十亿个晶体管被精心放置在一片硅片上。在电子设计自动化（EDA）中，一种名为 Abacus 的算法被用于“合法化”，这是一个将组件微调到芯片上最终有效位置的过程。该算法的一个关键步骤是简单地根据组件的期望坐标对它们进行排序。正如每个计算机科学学生所学，基于比较的排序不能快于 。这个在入门课程中教授的基本算法是一个关键的构建模块，它使得设计极其复杂的集成电路成为可能，表明有时最优雅的捷径是书中最古老的捷径之一 [@problem-id:4279412]。
近线性算法是工程师们解决支配我们世界的方程——流体流动、热传递和结构力学的偏微分方程（PDE）——不可或缺的工具。对于某些理想化的问题，比如在简单的矩形网格上求解泊松方程，快速傅里叶变换再次提供了一个惊人高效的 解法，将一个复杂的线性代数问题变成了频域中的简单除法。
对于更复杂的几何形状和问题，需要更复杂的工具。在现代谱方法中，我们可能使用非常高阶的多项式以难以置信的精度来表示解。对解的导数进行朴素计算将花费 次操作，其中 是多项式阶数。但通过巧妙地将问题转换到不同的基（多项式系数空间）并使用快速变换，这可以在 时间内完成，从而催生了一类新的高保真度模拟。
通常，最具挑战性的工程问题需要耦合不同的物理模型。想象一下模拟振动的汽车引擎产生的噪音。引擎本身是一个固体结构，可以用有限元法（FEM）建模，这会产生一个大型但稀疏的方程组。辐射到周围空气中的声音最好用边界元法（BEM）建模，但它有一个不幸的副作用，即产生一个稠密的 矩阵。这个稠密块成为整个模拟的瓶颈。解决方案？用捷径的艺术来攻击那个稠密块。通过对 BEM 部分应用 FMM 或相关的层次矩阵（-矩阵）技术，其成本从 降低到近线性。瓶颈被打破，整个耦合模拟变得可行。
将近线性算法用作“预条件子”——一个加速更大型求解器的助手——的想法是一个反复出现的主题。在计算固体力学中，模拟像橡胶这样的近不可压缩材料需要特殊的混合公式，这会导致极其困难的矩阵系统。高效求解它们的关键在于构建一个预条件子，该预条件子近似系统中一个特别棘手的部分，即舒尔补。事实证明，这个舒尔补的行为类似于一个扩散算子，可以用另一种名为代数多重网格（AMG）的近线性方法高效求解。通过将一个快速算法嵌入另一个之中，我们可以创建鲁棒且可扩展的求解器，这是计算自举的一个优美范例。
也许近线性缩放的影响在现代生物学中最为显著。基因组学领域已被数据淹没，像英国生物银行（UK Biobank）这样的项目提供了五十万人的遗传信息。全基因组关联研究（GWAS）的一个中心目标是扫描这些个体中的数百万个遗传变异（SNP），以寻找与糖尿病或精神分裂症等疾病的联系。
一个主要的统计混杂因素是，队列中的个体彼此之间有亲缘关系，有些是近亲，有些是通过共同祖先的远亲。如果处理不当，这种群体结构可能导致大量的假阳性结果。处理这个问题的统计学黄金标准是线性混合模型，它使用一个 的“遗传关系矩阵”（GRM）来模拟所有个体对之间的遗传相似性。对于 ，构建和操作这个矩阵将需要数TB的内存和以世纪为单位的计算时间。二次墙似乎不可逾越。
然而今天，这些分析已成常规。这是通过针对这一确切问题开发近线性算法的创造力大爆发而实现的。像 fastGWA 这样的工具构建了一个稀疏的 GRM，忽略了远亲关系，只保留了最强的联系。其他的，如 BOLT-LMM 和 REGENIE，则使用巧妙的统计和数值线性代数技巧来捕捉完整 GRM 的效果，而无需真正形成它。它们可能使用惩罚回归或随机算法来构建一个隐含地考虑了亲缘关系的“多基因预测器”。这些方法将有效复杂度降低到接近线性的 ，将一个不可能的计算转变为一个可以在计算集群上通宵运行的计算。这不仅仅是增量改进；它关系到整个科学领域的存亡。
在所有这些多样化的应用中，从星系到基因组，一个统一的原则浮现出来。二次诅咒源于这样一个假设：所有事物都以复杂的方式与其他所有事物相互作用。近线性算法的胜利在于认识到这并非事实。世界是有结构的。像 FMM 这样的层次化方法利用了远距离相互作用是简单的这一事实。像 FFT 这样的基于变换的方法利用了平滑函数在频域中具有紧凑表示的特性。像 AMG 这样的代数方法不是在物理空间中发现层次结构，而是在矩阵本身的连接中发现。
这些算法是计算科学中最美丽、最强大的思想之一。它们是无声的革命，使我们能够以前辈只能梦想的保真度来模拟世界。当我们把目光投向更宏伟的挑战——模拟整个人类大脑、预测全球气候变化、从第一性原理发现新材料——近线性算法的持续发明和应用将仍然是不可或缺的关键，是将不可能变为常规的巧妙捷径。