张量积网格

表示复杂系统通常需要在多维空间中进行操作，这是从金融到量子力学等所有科学领域面临的一个根本性挑战。虽然将简单的一维点线扩展到多维网格似乎很简单，但这种直观的方法却隐藏着一个灾难性的缺陷，使其无法用于真正的高维问题。本文将带领读者从这一简单的想法出发，探索现代计算所需的复杂解决方案。我们将首先揭示张量积网格的基本原理和机制，探讨其看似简单却具有欺骗性的一面，以及限制其应用的“维度灾难”。随后，本文将展示其广泛的应用和跨学科联系，说明其带来的挑战如何推动了稀疏网格等先进方法的发展，这些方法对于解决当今前沿科学问题至关重要。

我们如何描述世界？我们通常从为世界建立坐标开始。在一维空间中，这很简单：我们只需沿一条线放置点。但对于二维空间，如一张平坦的纸，或三维空间，如您所在的房间，该怎么办呢？对于金融或量子力学等领域所需的四维、五维甚至数百维的空间，又该如何处理？

扩展我们一维网格的最直接、最直观的方法是通过一种称为​​张量积​​的构造。想象一下，您在 x 轴上有一组点，位置分别为 $x_1, x_2, \dots, x_n$。现在，想象在 y 轴上有一组类似的点 $y_1, y_2, \dots, y_n$。要创建一个二维网格，您只需将每个 x 坐标与每个 y 坐标配对即可。在视觉上，这就像铺设 x 轴网格，并在其每个点上绘制一个 y 轴网格的垂直副本。结果是一个完美的、矩形的点 $(x_i, y_j)$ 棋盘。

这个思想可以完美地扩展到任意数量的维度。对于一个 $d$ 维空间，我们为 $d$ 个坐标轴中的每一个定义一组 $n$ 个点。张量积网格就是所有可能的点 $(x^{(1)}_{i_1}, x^{(2)}_{i_2}, \dots, x^{(d)}_{i_d})$ 的集合，其中 $i_1, i_2, \dots, i_d$ 各自的取值范围都从 $1$ 到 $n$。

这种构造提供了一种自然的方式来存储定义在该网格上的函数信息。在一个一维网格上求值的函数 $u(x)$ 只是一个数字列表，或一个向量。在一个二维张量网格上求值的函数 $u(x, y)$ 可以排列成一个矩阵，其中第 $i$ 行第 $j$ 列的元素是值 $u(x_i, y_j)$。遵循这个逻辑，一个在 $d$ 维网格上采样的函数 $u(x_1, \dots, x_d)$ 自然地表示为一个多维数组，数学家称之为​​$d$ 阶张量​​。函数在网格点 $(x^{(1)}_{i_1}, \dots, x^{(d)}_{i_d})$ 处的值成为张量元素 $U_{i_1, i_2, \dots, i_d}$。这种优雅的对应关系是数值计算与张量数学之间深层联系的起点。

张量积网格的刚性、有序结构不仅仅是美学上的愉悦；它非常强大。它将出了名困难的高维问题转化为一系列可管理的一维问题。

考虑​​插值​​问题：寻找一个通过给定数据集的光滑函数。在一维中，这是一个经典问题，可以通过例如 Lagrange 多项式完美解决。在多维中，如果您得到一团随机分散的数据点，寻找一个唯一的插值多项式是一场噩梦。没有简单的存在性或唯一性保证，而且这个问题在计算上充满风险。

但在张量积网格上，问题变得惊人地简单。要在二维网格上找到一个插值数据的多项式，我们可以用一维构建块来构造它。如果 $L_i(x)$ 是 x 坐标的一维 Lagrange 多项式，$M_j(y)$ 是 y 坐标的 Lagrange 多项式，那么函数 $P_{ij}(x,y) = L_i(x) M_j(y)$ 构成了一个完美的基。插值多项式只是这些基函数的和，并且找到它既直接又有保证，在适当的多项式空间中存在唯一解。网格的张量结构使我们能够“分解”问题。

同样的魔力也适用于​​数值积分​​（求积）。如果我们想计算一个函数在 $d$ 维立方体上的积分，张量积网格允许我们通过简单地取 $d$ 个一维积分法则的乘积来构建一个 $d$ 维求积法则。对于某些“表现良好”的函数，这非常高效。考虑一个完全可分的函数，如 $f(x_1, x_2, \dots, x_d) = f_1(x_1) f_2(x_2) \cdots f_d(x_d)$。它在立方体上的积分就是其各分量一维积分的乘积。一个由对每个 $f_i$ 都精确的一维积分法则构建的张量积求积法则，将精确计算出 $d$ 维积分。在一个引人注目的例子中，函数 $f(\mathbf{x}) = \prod_{i=1}^d x_i$ 的积分可以仅用一个网格点就精确求出，无论维度 $d$ 是多少！这是张量积网格的最佳表现，利用了函数的简单性和结构的规律性，使高维问题变得微不足道。

然而，这种优雅的结构隐藏着一个毁灭性的秘密。每个维度有 $n$ 个点的张量积网格的总点数是 $N = n^d$。这个数字随着维度 $d$ 呈指数增长。这种灾难性的增长被称为​​维度灾难​​。

让我们具体地看这个问题。假设我们需要 $n=10$ 个点来合理地表示一维函数。 在二维空间中，我们需要 $10^2 = 100$ 个点。尚可管理。 在三维空间中，我们需要 $10^3 = 1,000$ 个点。仍然可以。 在六维空间中，我们需要 $10^6 = 1,000,000$ 个点。这开始变得昂贵了。 在十维空间中，我们需要 $10^{10} = 10,000,000,000$ 个点。在每个点上存储一个值就需要大约 80 GB 的 RAM。对每个点执行最简单的操作也需要现代计算机花费数分钟，甚至数小时。 在二十维空间中，我们需要 $10^{20}$ 个点。这比地球上所有海滩的沙粒还要多。问题变得完全不可能解决。

这并非纯粹的学术问题。在计算金融学中，“彩虹”期权的价格可能取决于 $d=5$ 或 $d=10$ 种不同资产的价格。试图在张量积网格上使用动态规划解决这个问题是不可行的，正是因为状态空间大小的这种指数级爆炸。同样，如果我们想保证我们的网格能够解析或“看到”单位超立方体内大小为 $\ell$ 的小特征，我们需要的网格间距最多为 $\ell$。这要求每个维度需要 $n \approx 1/\ell$ 个点，对于张量网格，总点数约为 $N \approx (1/\ell)^d$。解析精细细节所需的点数呈指数级爆炸。

张量积网格的简单性正是其自身的致命弱点。通过以同等、不懈的分辨率处理每个维度，它创造了一个计算怪物。这种蛮力棋盘格过于密集、过于冗余、过于昂贵。我们需要一种更聪明、更精炼的方法。

摆脱这场灾难的出路在于一个关键的观察：现实世界中大多数有趣的函数并非空间中每一点值的任意集合。它们拥有结构。特别是，它们通常是“光滑的”，而且许多不同变量之间的相互作用通常很弱。全张量积网格包含了网格点的所有组合，它将第 10 个变量与第 20 个变量之间的相互作用看得与仅沿第 1 个变量的变化同等重要。这通常是一种极大的浪费。

解决方案是构建一个“更智能”的网格，只包含最重要的点。这就是​​稀疏网格​​背后的思想。稀疏网格不是对精细的一维网格进行完全的张量积，而是通过巧妙地组合不同分辨率级别的网格来构建。

要理解这一点，我们必须进行层级化思考。假设 $U^\ell$ 是使用级别为 $\ell$ 的网格（其中 $\ell$ 越高，网格越精细）来近似一维函数的算子。我们可以将从级别 $\ell-1$ 移动到 $\ell$ 所增加的“细节”或​​层级增量​​定义为 $\Delta^\ell = U^\ell - U^{\ell-1}$（其中 $U^0 = \Delta^0$）。完整的近似可以通过将这些细节相加来重建：$U^L = \sum_{\ell=0}^L \Delta^\ell$。

级别为 $L$ 的全张量积网格对应于取这些细节 $\Delta^{\ell_1} \otimes \cdots \otimes \Delta^{\ell_d}$ 的所有张量积，其中每个级别 $\ell_i$ 最多为 $L$。​​Smolyak 构造法​​的突破性见解是只保留这些组合中的一小部分。它不是让所有级别同时都很高，而是对级别的总和施加一个约束：

其中 $|\boldsymbol{\ell}|_1 = \ell_1 + \cdots + \ell_d$。这个公式说：我们将包括那些许多维度处于粗糙级别（低 $\ell_i$）而只有少数维度处于精细级别（高 $\ell_i$）的细节组合。我们系统地丢弃了那些许多变量同时以高分辨率表示的“高阶相互作用”。

这对网格点数的影响是巨大的。虽然分辨率对应于级别 $L$ 的全张量网格大约有 $(2^L)^d = 2^{Ld}$ 个点，但稀疏网格只有大约 $2^L L^{d-1}$ 个点。对乘积 $Ld$ 的致命指数依赖性已经减少为对数项中对 $d$ 的温和得多的多项式依赖性。这就是我们的出路。

为什么丢弃所有那些高阶相互作用项是合理的？答案在于对高维空间中“光滑性”含义的更深层次理解。稀疏网格能发挥其魔力的函数类别是那些具有​​有界混合导数​​的函数。

标准的（或各向同性的）光滑性意味着像 $\frac{\partial^2 f}{\partial x_1^2}$ 和 $\frac{\partial^2 f}{\partial x_2^2}$ 这样的导数是表现良好的。​​混合光滑性​​是一个更强的条件，它要求*混合偏导数*如 $\frac{\partial^2 f}{\partial x_1 \partial x_2}$ 也表现良好。直观地说，一个具有混合光滑性的函数，其变量之间的耦合是弱的。它的行为不依赖于许多变量之间复杂的、高阶的相互作用。这些正是其细节贡献 $\Delta^{\ell_1} \otimes \cdots \otimes \Delta^{\ell_d}$ 随着级别总和 $|\boldsymbol{\ell}|_1$ 的增长而迅速衰减的函数。因此，稀疏网格是为利用这种特定规律性而量身定做的。

这一见解从根本上改变了游戏规则。当我们比较预算为 $N$ 个网格点的近似误差时，对于光滑度为 $r$ 的函数，各种方法的排名如下：

• ​​全张量网格误差：​​ $\mathcal{O}(N^{-r/d})$。收敛速度本身随维度增加而降低。
• ​​蒙特卡罗误差：​​ $\mathcal{O}(N^{-1/2})$。速度与维度无关，但很慢。
• ​​稀疏网格误差：​​ $\mathcal{O}(N^{-r} (\log N)^k)$。代数收敛速度 $-r$ 现在与维度无关！

对于任何维度 $d \ge 2$，稀疏网格的速度都优于全网格。如果函数足够光滑（$r > 1/2$），稀疏网格最终也会击败蒙特卡罗方法。这就是其强大功能的数学依据。此外，这个框架是灵活的。对于在某些方向上变化比其他方向更大的​​各向异性​​函数，我们可以使用级别的加权和，将更多的点集中在重要的方向上，这对于全张量网格来说是成本高昂而无法实现的。

还有另一种优美的方式来形象化这个原理。Smolyak 对级别的条件 $\sum \ell_i \le L$ 在傅里叶空间中有一个直接的对应。如果我们将级别 $\ell_i$ 看作对应于解析高达 $k_i \sim 2^{\ell_i}$ 的频率，那么对频率对数的求和约束就变成了对频率本身的乘积约束：

满足此条件的傅里叶系数集合形成一个称为​​双曲交叉​​的形状。它不是一个系数立方体（全张量网格会捕捉到），而是包含那些只有一个频率 $k_i$ 很大而其他频率很小的系数。这在不同的语言中是同一个原则：保留基频和简单的相互作用，但丢弃复杂的、高频的相互作用。双曲交叉中的系数数量，以及稀疏网格中的点数，都以 $\Theta(N (\log N)^{d-1})$ 的规模增长。这揭示了这两种驯服高维空间的方法之间深刻的统一性。

从简单的张量积网格到复杂的稀疏网格机制的历程，是科学过程的见证。我们从一个直观的想法开始，将其推向极限，直面其灾难性的失败——维度灾难——并作为回应，发展出更深刻、更细致的理论，利用我们试图理解的函数本身隐藏的结构。其他强大的技术，如​​低秩张量格式​​，例如张量链 (TT)，也基于类似的原理，将巨大的 $n^d$ 元素张量近似为一个紧凑的、由较小张量组成的网络，其存储成本仅为 $\mathcal{O}(dnr^2)$。所有这些方法都共享一个共同的哲学：在高维度中，你无法靠蛮力取胜。你必须靠智慧取胜。

理解了张量积的原理后，我们可能会倾向于将其视为一个巧妙的数学技巧。但事实证明，自然界中充满了可以用这个优美而简单的思想很好地描述的现象。其真正的力量不是体现在抽象中，而是在其跨越科学和工程的广泛多样的应用中。它是从最简单的一维线条构建真实和抽象世界的工具。

想象你是一位正在设计桥梁或飞机机翼的工程师。为了分析应力和应变，你可能会使用一种称为有限元法的强大技术。这种方法将一个复杂的形状分解成由更简单、可管理的块或“单元”组成的拼凑物。我们如何描述一个物理场——比如温度或位移——在这些简单块（如一个正方形）内的行为？

人们可能会认为这需要一些复杂的、定制的二维函数。但张量积的魔力告诉我们并非如此。我们可以通过将两个基本的一维函数相乘来构建一个复杂的二维描述。例如，一个在 $x$ 方向的二次曲线 $L_i(\xi)$ 和另一个在 $y$ 方向的二次曲线 $L_j(\eta)$ 可以相乘，形成一个丰富而灵活的二维“形函数”$N_{ij}(\xi, \eta) = L_i(\xi)L_j(\eta)$。这不仅仅是一个近似；对于一大类重要的单元来说，这是为我们的计算构建基的精确且唯一的方法。二维曲面的复杂性直接从一维线条的简单性中编织而成，这是一个支撑着现代计算力学大部分内容的深刻见解。

这种构造能力出现在非常实际的场景中。考虑在一个方形半导体芯片上放置温度传感器。我们需要以一种能准确插值它们之间温度场的方式来放置一个传感器网格。一个简单的、均匀的网格似乎是显而易见的，但它可能导致我们插值的温度在边缘附近出现剧烈振荡——这是一个臭名昭著的称为 Runge 现象的问题。解决方案是首先在一维空间中变得更聪明。通过将节点沿一条线不均匀地放置，而是在被称为 Chebyshev 点的特殊位置上，我们可以抑制这些振荡。然后，张量积使我们能够毫不费力地将这种最优的一维排列“提升”到一个二维传感器网格，为我们提供一个稳健可靠的芯片热分布图。

我们正在绘制的“世界”甚至不必是我们日常经验所熟悉的那个空间。在固态物理学中，晶体中电子的行为由它们的动量决定，动量存在于一个称为“倒易空间”的抽象景观中。为了计算诸如电导率或光吸收之类的材料性质，我们必须在这个动量空间上积分函数，特别是在一个称为布里渊区的基本区域上。我们如何为这个积分创建一个网格？著名的 Monkhorst-Pack 网格是现代计算材料科学的基石，它不过是一个简单的张量积网格——一个沿着倒易晶格轴线布置的均匀网格。将传感器放置在芯片上的相同原理，帮助我们理解了金刚石的电子结构。

张量积的影响力甚至更深，揭示了我们网格的几何结构与物理定律的代数之间的隐藏统一。考虑求解一个瞬态问题，比如热量通过一根金属棒的扩散。我们可以将棒离散化为一组点（空间上的一维网格），并在一系列离散的时间步长（时间上的一维网格）上模拟该过程。我们完整的问题存在于一个二维时空网格上。

当我们为这个系统写下方程时，我们会得到一个巨大的矩阵方程 $B U = g$，我们必须解出所有点在所有未来时间的温度。这个矩阵 $B$ 可能非常巨大，包含数百万甚至数十亿个条目。乍一看，它似乎是一个不可穿透的、庞然大物。但如果我们仔细观察，一个惊人的结构就会出现。矩阵 $B$ 根本不是随机的；它本身就是一个张量积！它可以优雅地写成代表时间操作和空间操作的小而简单的矩阵的组合，例如 $B = I_t \otimes A_x - S_t \otimes I_x$，其中下标分别表示时间和空间。我们时空网格的结构完美地反映在主方程的代数结构中。这不是巧合；这是一个基本原则，它使我们能够设计出极其高效的算法来求解科学中一些最重要的方程。

到目前为止，张量积网格似乎是一种威力巨大的通用工具。确实如此——在低维度下。但当我们涉足具有超过三或四个维度的问题时，一场可怕的风暴正在地平线上聚集。这就是臭名昭著的“维度灾难”。

问题在于规模。要用 10 个点在一维中保持一定的分辨率，我们需要 10 次函数评估。在二维中，张量网格需要 $10 \times 10 = 100$ 个点。在三维中，1000 个。在六维中，我们需要一百万个点。对于一个 $d=6$ 维的金融问题，全张量网格上的网格点数随所需精度 $h$ 的变化关系为 $N = \mathcal{O}(h^{-6})$。将网格间距减半并不会使成本加倍；它会乘以 $2^6 = 64$。这种指数级增长使得直接张量积方法对于许多现代问题在计算上变得不可能。

那么，这些高维问题从何而来呢？它们无处不在。它们出现在金融领域，当基于数十个经济因素评估投资组合时。它们出现在不确定性量化中，其中“维度”不是空间坐标，而是模型的不确定参数——风速、材料纯度、反应速率。如果我们对核反应的模型有 10 个不确定参数，我们突然就面临一个 10 维的积分问题。天真的张量积网格把我们引向了一堵计算的砖墙。

我们必须放弃我们优美的构造原则吗？不！我们只需要更聪明一点。突破来自于这样一个认识：对于许多函数，特别是光滑函数，最重要的信息包含在变量之间的低阶相互作用中。由所有六个或十个变量同时相互作用产生的精细细节通常可以忽略不计。

全张量积网格是浪费的，因为它以相同的高分辨率解析所有相互作用，无论重要与否。解决方案是​​稀疏网格​​。通过 Smolyak 算法构建的稀疏网格是一件精妙的杰作。它仍然由张量积构建，但它不是使用一个巨大的、高分辨率的张量积，而是巧妙地组合了许多小的、低分辨率的张量积，以捕捉重要的相互作用，同时丢弃不重要的相互作用 [@problemid:2379307]。

结果是惊人的。对于具有足够光滑性的函数，稀疏网格在 $d$ 维空间中达到精度 $h$ 所需的点数，其规模为 $N = \mathcal{O}(h^{-1} |\log(h)|^{d-1})$。基数中对 $d$ 的毁灭性指数依赖 $h^{-d}$ 已被一个温和得多的对数项所取代。一个原本不可能的问题变得仅仅是困难，并且通常是完全可以解决的。

这个想法解锁了整个领域。在不确定性量化中，我们可以在高维参数空间中构建稀疏网格，以计算复杂模型输出的均值和方差，例如考虑到风和大气稳定性的不确定性，工厂烟囱排放污染物的地面浓度。我们甚至可以使这些网格各向异性，将我们的计算精力集中在最重要的参数上，或者使其自适应，自动发现并细化参数空间中最敏感的区域。这就是计算科学的前沿——解决几十年前无法想象的数十甚至数百维的问题。

拥有如此强大的力量，人们很容易将张量积网格（无论是密集的还是稀疏的）视为解决所有问题的万能锤。但科学需要品味和判断力。张量积网格本质上是笛卡尔式的；它诞生于正方形和立方体。它并不总是适用于所有几何形状的正确工具。

考虑在球体表面上积分一个函数，这是量子化学等领域在使用密度泛函理论计算分子性质时常见的问题。人们可以尝试在角坐标 $(\theta, \phi)$ 上施加一个张量积网格。但这就像试图用一张矩形的方格纸包裹一个地球仪。网格点将不可避免地在两极聚集，计算结果将不具有真正的旋转不变性——结果将取决于我们如何相对于这个任意的网格来定向我们的分子。对于这类问题，像 Lebedev 网格这样尊重球体固有对称性的专门点集，要高效和优雅得多。

张量积网格的历程是科学进步本身的缩影。我们从一个简单、优雅的想法开始。我们通过将其应用于世界，在预期和意想不到的地方发现它的力量。我们将其推向极限，直到遇到一堵墙，即“维度灾难”。然后，凭借新的洞察力，我们完善了最初的想法，将墙壁变成了通往新领域的大门。在这一切之中，我们不仅学会了欣赏我们工具的力量，还学会了知道何时以及如何使用它们的智慧。