SZ Sequences: Binary-Based (0, 2^q)-Sequences

一句话总结

用 GF(2) 二进制矩阵从零构造出一族全新的低差异序列 SZ：以 \(2\times 2\)（乃至 \(q\times q\)）二进制块矩阵充当”符号”，拼出 \((0, 2^q)\)-序列，使每对维度都是 \((0,2)\)-序列、每四维都是 \((0,4)\)-序列，兼具 Sobol 的比特级计算效率与更好的低维投影质量，可直接替换现有系统里的 Sobol 矩阵。

研究背景

采样是计算机图形学的基础环节，渲染尤其依赖对复杂光传输路径的蒙特卡洛积分。这些路径虽然名义上是高维的，但主要由一系列二维表面交互（外加少量一维分量）拼接而成。因此长期以来研究重心都放在优化二维分布上，一度认为优化高维空间”至多是次要问题”。后来 Grünschloß 等人给出低差异序列的求逆方法，使得单条高维低差异序列可以为所有像素、所有维度统一生成样本（全局采样），Sobol 由此成为 pbrt、Mitsuba 等主流渲染器的默认采样器。

现有三大数字构造路线各有短板：Halton 用不同素数基，比特运算不友好；Sobol 用二进制多项式矩阵，速度极快，但只有前两维构成 \((0,2)\)-序列，随维度增加参数 \(t\) 变大、低维投影质量下降；Faure/Niederreiter 用 Pascal 矩阵在大素数（或素数幂）基上工作，理论优美但基太大、需要查表符号运算，在图形学里几乎无人使用。本文的目标是把 Faure/Niederreiter 这一类构造真正引入图形学：既保留 Sobol 的二进制高效计算，又获得对低维投影的强控制力。

方法

核心思路是”违反两条传统规则再让它们互相抵消”：既不能用合数当基，也不能用小于维数 \(s\) 的基 \(b\) 得到 \((0,s)\)-序列——但作者用 \(2\times 2\) 二进制块矩阵去”模拟”基 4，同时打破这两条规则从而得到 \((0,4)\)-序列。

flowchart TD
    A[GF(2) 二进制块矩阵作为符号] --> B[穷举搜索: 找可生成 0,4 序列的矩阵集]
    B --> C[提炼出三条符号规则: 可逆 / 逐列互异 / 两两之和可逆]
    C --> D[识别出 S 与 Z 两套字母表<br/>S 集恰为有限域]
    D --> E[Algorithm 1: 由字母表构造 Pascal 矩阵<br/>得到 0,2^q 序列生成矩阵]
    E --> F[Nesting 嵌套: 低维序列嵌入高维]
    E --> G[Ensembling 组装: 拼合低维子序列成高维]
    F --> H[可直接替换 Sobol 矩阵]
    G --> H

关键设计：

1. 块矩阵符号与三条规则。把生成矩阵的 \(2\times 2\) 块、以及被乘索引向量的每对比特都当作基 4 数字来解释。通过对”混合矩阵”（hybrid matrix）可逆性条件的分析，作者推导出：首块行里每个块必须（1）可逆、（2）在三个矩阵对应槽位互异、（3）对应符号两两之和可逆。满足条件的六个可逆 \(2\times 2\) 矩阵恰好分成两个不相交的三元集合，分别记作 \(S\)（形如三角形一侧）与 \(Z\)（镜像另一侧），SZ 之名由此而来。

2. 字母表即有限域。进一步发现 \(S\) 集不仅对加法封闭，还对乘法封闭，因而按 Wedderburn 小定理构成一个有限域——所缺的”零元”正是此前一直用来构造单位矩阵的全零块。于是构造 \((0, 2^q)\)-序列被归约为：寻找一套对加法、乘法、求逆都封闭的 \(q\times q\) 块矩阵字母表，再为每个符号建 Pascal 矩阵 \(P(a)\)。这与 Niederreiter 对 Faure 的推广在本质上重合，区别在于本文把域元素直接”嵌”进 GF(2) 生成矩阵，用二进制矩阵-向量乘法同时完成域运算与双射，无需符号查表，因而更快更可扩展。

3. Alpha 元素加速搜索。有限域里存在能通过自乘遍历所有非零元素的”本原元” \(\alpha\)，字母表可写成 \(\Sigma = \lbrace 0, I, \alpha, \alpha^2, \ldots, \alpha^{q-2}\rbrace\)。据此 AlphaSearch 只需随机取可逆块、自乘直到回到 \(I\)、检查其阶是否为 \(s-1\)，即可高效找字母表并枚举全部字母表；作者统计到各维字母表数目恰好对应一般仿射群 AGL 的阶除以维数（OEIS A258745）。

4. 嵌套（Nesting）与组装（Ensembling）。嵌套：找一个 \(2^{2q}\) 上的字母表，其符号内嵌给定 \(2^q\) 字母表的符号，借助 Pascal 矩阵性质与 Lucas 定理，可用保序变换从高维生成矩阵复原低维序列（每步把维度平方）。组装：利用 \(P(a+x)=P(a)P(x)\) 这一 Pascal 矩阵性质，把符号按”逐层嵌套”结构排序（NestSort），使高维序列各维度带（band）之间彼此看起来与低维带一致，从而把两个 \((0,2)\)-序列拼成 \((0,4)\)-序列、四个 \((0,4)\) 拼成 \((0,16)\)，以此类推。组装会引入维度间强相关，可用字母表乘法交换性等价实现的 Faure–Tezuka 混洗来缓解。

实验结果

数值积分方面，作者按 Jarosz 等人的方法，用阶跃 \(g_0\)、线性 \(g_1\)、高斯 \(g_\infty\) 三种基函数构造 4 维与 8 维合成函数，比较独立随机、Halton、Sobol、SZ 的均方相对误差（MRSE），每种做 1024 次独立试验、最多 \(2^{16}\) 样本、用 Owen 置乱随机化。结论：SZ-d0 在 4 的幂次样本数处与 Sobol-d0 相当；在”从第 4 维开始取样”（模拟渲染中前几维已被消耗）的情形下，SZ-d4 仍与 SZ-d0 一样好，而 Sobol-d4 明显变差；在两个 2D 函数乘积之和这类被积函数上，SZ 显著优于 Sobol。

渲染方面，作者在 pbrt 中实现了 SZ 采样器（全局采样与改造后的 Z-采样两种索引），在多种常见测试场景上与 Sobol、Halton、Faure/Niederreiter 对比 RMSE。Sportscar 场景配 HDR 环境贴图、64 spp 直接光照下，SZ 相对 Sobol 把 MRSE 降低约 \(1.93\times\)，并且不出现未收敛 Sobol 特有的棋盘格伪影。多张环境贴图（Hangar、Cayley、Empty Warehouse、Sky）的定量结果如下（部分 spp 的 MRSE 比值）：

场景	16 spp	64 spp	256 spp	1024 spp
Hangar Interior	1.15×	1.93×	0.977×	1.13×
Cayley Interior	1.23×	1.49×	1.34×	1.76×
Empty Warehouse	1.38×	1.60×	1.31×	1.09×
Sky	2.96×	0.897×	2.71×	0.852×

越复杂的环境光照与 BSDF（如车漆的高光反射）获益越大，作者推测源于 SZ 为这些维度提供了真正的 \((0,4)\)-序列。星差异测试中三种序列均值接近、Sobol 略优，但 SZ 在 4D 的 4 的幂次处略有优势；频谱上 SZ 的成对投影在 \(2^q\) 倍频程处更规整平滑。

亮点与局限

亮点：从纯实验探索出发，反向逼近并统一了 Faure/Niederreiter 的经典理论，却用二进制矩阵取代素数幂域上的符号运算，实现比特级高效计算；给出 S-P-Z 分解，把 \(m\) 比特精度下的时空复杂度从 \(O(m)\) 降到中间 Pascal 因子 \(O(\log m)\)、\(S/Z\) 因子 \(O(2^{q-1})\)，前 16/256 维实测省内存 11%/23%、提速 20×/15×；生成矩阵与 Sobol 前两维完全一致，可无缝替换、渲染性能几乎无变化（生成样本耗时不足总渲染时间 3%）；独有的嵌套与组装能力契合渲染中”积分域主要由二维表面构成”的结构。

局限：作者坦言其构造与 Niederreiter 序列”很可能一致”仍只是待证的假设，因两者都存在多个自由度导致实现各异、难以经验验证；组装会在对应维度间引入较强相关性，需额外混洗缓解，但混洗又可能破坏高维结构；在星差异等指标上 Sobol 仍略占优；作者也强调，要对这些序列下最终性能结论，还需要更深入地分析”积分器-采样器”之间的交互。

延伸思考

这项工作最耐人寻味的地方在于”实验先行、理论殿后”的路径：先靠穷举搜索撞见规律，再用有限域理论把它讲清楚，最后发现自己无意间重走了 Niederreiter 的路，却换来了二进制实现的巨大效率红利。字母表数目与一般仿射群阶的对应关系暗示字母表本身或许能算法化直接生成，省去搜索。更值得追问的是”积分器-采样器交互”：SZ 在不同 spp、不同场景下相对 Sobol 的优劣并不单调（甚至同一场景 16 spp 大胜、64 spp 略负），说明采样质量与被积函数的维度耦合结构高度相关，单看差异或频谱都不足以预测渲染表现。把”每对维度都是 \((0,2)\)-序列”这一性质与蓝噪声优化、可微 Owen 置乱等既有工具结合，可能是让这族序列真正撼动 Sobol 垄断地位的关键方向。