Fast Sparse Matrix Permutation for Mesh-Based Direct Solvers

一句话总结

针对三角网格产生的稀疏线性系统，提出一种”以补丁（patch）压缩网格、在商图上做嵌套剖分”的快速填充约减重排算法，在保留可复用消去树结构的同时把重排开销砍掉一大截，集成进 cuDSS / MKL 后端到端最高提速 6.27×。

研究背景

• 领域现状：稀疏 Cholesky 分解是图形学里解大规模半正定系统（参数化、变形、物理仿真、几何流）的主力方法，胜在稳健。现代求解器（Apple Accelerate、Intel MKL、NVIDIA cuDSS）已经大幅优化了符号分析与数值分解阶段。
• 核心痛点：符号阶段里”计算填充约减重排（permutation）”成了新的可扩展性瓶颈。作者实测在 cuDSS 上求解平均曲率流时，重排平均占端到端时间的 86%，大网格上高达 96%。同时，重排通常被当成独立的黑盒前处理，跑完就丢，导致嵌套剖分产生的层次结构信息无法被后续符号分析复用——而 cuDSS 恰恰需要消去树来驱动并行数值执行。
• 本文 idea：找最优填充约减重排是 NP 完全的，通用分区器（METIS、PT-Scotch）把大量时间花在”严格平衡 + 分隔集最小化”上。对网格系统而言，主动放松这两个约束能大幅省时，虽然分隔集质量略降，但省下的前处理开销远大于填充增多带来的代价。于是把网格压缩成补丁、在小得多的商图上做嵌套剖分，并在重排的同时把消去树一并建出来供符号分析直接复用。

方法

整体框架：算法把重排拆成”补丁级局部排序 + 分隔集的紧凑商图排序”两层。先在 GPU 上把网格划成补丁，把补丁提升（lift）到矩阵图得到分组映射 gmap；再以补丁分组为指导做嵌套剖分、同时构建消去树 etree；最后按用户选定的遍历顺序（schedule）拼接各节点局部排序，得到全局重排向量。GPU 只负责第一步算补丁，其余在 CPU 上跑。

flowchart LR
  A["三角网格 M + 矩阵 A"] --> B["GPU 计算补丁划分"]
  B --> C["提升到矩阵图得 gmap"]
  C --> D["补丁引导的嵌套剖分 + 构建 etree"]
  D --> E["各节点局部 AMD 排序"]
  E --> F["按 schedule 拼接成全局 perm"]

关键设计：

• 商图压缩搜索空间：分隔集计算是最贵的一步且规模敏感。把一个补丁当作商图里的一个节点后，分隔集决策在补丁粒度上做，商图规模远小于原矩阵图 \(G\)，因此分隔集计算显著加速。极限情况下每个补丁只含一个网格顶点，算法退化为经典嵌套剖分。分隔集提取流程是：对当前子图建商图 \(q\)、带平衡约束地二分 \(q\)、把分区提升回顶点得到”分隔集超集”、再做平衡与局部精化缩小它、最后导出左右子图递归。

• 商图一次构建、跨递归复用：经典多层剖分（如 METIS）在每一递归层都重新粗化图，代价高。本文只构建一次商图，之后在从根到叶计算 etree 节点时，仅通过”移除已标记分隔集的节点权重与边权重”来增量更新商图，避免反复扫描整个矩阵，省去冗余粗化。分隔集的二分与精化都借用 METIS 在小商图上完成，因而很快。

• 重排与消去树同时产出：算法把 etree 用一维数组存的满二叉树表示（节点 idx，孩子为 \(2\,idx+1\) 与 \(2\,idx+2\)），在剖分过程中同步建好。这样 cuDSS 的符号分析可以直接拿去用，省掉一次昂贵的消去树重建。实践中深度取 9–10 就能提供足够并行度。

• 局部排序 + 可选 schedule：每个树节点在其诱导子图上做局部排序（默认用 AMD，比 METIS 快一个数量级），缓存结果后按遍历顺序拼接。schedule 只要满足”父节点不早于子节点”即为合法，不改变填充量，但影响性能：CPU 求解器（如 CHOLMOD）偏好后序遍历以提升时间局部性，GPU 求解器（cuDSS）偏好按层的 wavefront 顺序以暴露并行度。算法同时提供后序与层序两种。

实验结果

作者把重排阶段替换进 cuDSS 与 Intel MKL（cuDSS 还替换了消去树构建），数值分解与求解例程保持不变，从而隔离重排的影响；测试平台为 Intel Xeon Gold 6248 + NVIDIA RTX 3080，网格来自 Smithsonian、ThreeDScans、Thingi10K。下面汇总各应用在 cuDSS 上的端到端提速（大网格与小网格各一例）：

应用	设置	网格规模	端到端提速
数据平滑 Data Smoothing	单次分解	1M 顶点	5.23×
数据平滑 Data Smoothing	单次分解	0.1M 顶点	2.92×
谱共形参数化 SCP	定分解 + 重复右端	1.5M 顶点	4.16×
网格平滑 Mesh Smoothing	重复分解 + 矩阵右端	1.76M 顶点	3.70×
参数化 Parameterization	重复分解 + 重复右端	1.1M 顶点	1.47×

在 Laplace-Beltrami 单次分解实验中（103 个网格，1.5K–1.8M 顶点），提速随规模增长，大网格上 cuDSS 最高 6.62×、MKL 最高 2.55×；几何平均 cuDSS 3.51×、MKL 1.76×。经验阈值大约是 cuDSS 上 5 万顶点、MKL 上 10 万顶点以上本方法才划算。只看重排本身的排序时间，相对 METIS 最高 10.27×（几何平均 4.58×）、相对 ParMETIS 最高 2.27×。消融显示：补丁尺寸默认取 256 在质量与速度间平衡最佳；商图分隔集比 METIS 顶点分隔快约 3×、填充率仅升 6–15%；局部排序用 AMD 比 METIS 快约 12×、填充率仅升 7–11%。对称 Dirichlet 参数化这类二阶（Hessian）系统，通过把每个 2×2 块合并为单节点后重排、再展开回原系统，保持了与标量 Laplacian 相当的重排成本。

亮点与局限

• 亮点：
  • 精准打击了”重排占符号阶段大头”这一被忽视的瓶颈，思路简单但工程收益直接；
  • 补丁 + 商图的复用机制让重排随网格规模的扩展性明显优于 METIS/ParMETIS；
  • 重排产出即带可复用的消去树，天然契合 cuDSS 这类需要 etree 的并行求解器；
  • 以插件方式替换厂商求解器的重排阶段，无需改动数值内核，落地成本低。
• 局限：
  • 用”质量换速度”，分隔集质量与填充率会略降；当矩阵结构固定、同一分解被复用上千次求解（如逆向渲染）时，累计的分解/回代额外开销可能反使端到端略微变慢（作者给出各应用的 break-even 迭代数）；
  • 小网格（约 10 万顶点以下）上重排成本本就很小，METIS 反而更优；
  • 目前专门针对三角网格；四面体网格的初步实验里不含补丁时最高 3.73×，一旦计入补丁时间掉到 0.83×，说明体网格还缺一个够快的补丁生成例程。

延伸思考

这项工作体现了”针对领域结构放松通用最优性”的典型收益：网格的空间结构本身就是很好的分区先验，与其用通用分区器苦求最小分隔集，不如借网格补丁快速给出”够用”的层次。它和同组的 Parth（复用消去树以在稀疏模式随时间变化时加速重排）、以及 GPU 版 AMD 等工作在”复用/加速符号阶段”的方向上互补。值得追问的点：补丁质量（连通性、尺寸分布）与最终填充率的定量关系能否用来自适应选补丁尺寸；作者提到的 GPU 端分隔集计算与并行局部排序若打通，重排是否能进一步不再是瓶颈；以及把这套思路推广到四面体乃至更一般 FEM 网格时，快速体网格补丁划分会是关键一环。