稀疏乔列斯基分解的消元树结构与并行化策略

稀疏乔列斯基分解（sparse Cholesky factorization）是求解大规模对称正定线性系统 Ax = b 的核心手段。与稠密分解不同，稀疏分解必须在数值计算之前先完成符号分析，以确定非零元位置并控制填充（fill-in）。在这一阶段，消元树（elimination tree，后文简称 etree）充当了依赖图的角色 —— 它既决定了哪些列可以并行处理，也决定了填充将在何处产生。如何通过 etree 分析来同时实现最小填充与最大化并行度，是数值线性代数与高性能计算交叉领域的核心工程问题。

消元树：从矩阵结构到依赖图

给定一个对称正定矩阵 A 与某种重排序 P，稀疏 Cholesky 分解将 A 分解为 A = PLLᵀPᵀ，其中 L 为下三角因子。重排序的目标是让 L 尽量稀疏 —— 即非零元数量最少，这对应于最小化填充的启发式策略。

消元树的构建逻辑如下：对矩阵的第 k 列执行消元时，若该列的非零元跨越了更大的行索引集合，则新产生的非零元会被注入到后续列中。这些新产生的非零元构成了填充，它们在 etree 中体现为父节点关系。具体而言，列 j 的父节点定义为第一个在 L 的第 j 列中出现非零元的列 i（i > j）。整个过程递归构造出一棵树形结构，根节点对应最后消元的列。

消元树的一个关键性质是：同一父节点的所有子列在数值分解时存在严格的串行依赖 —— 只有父列完成消元后，子列的后续更新才能进行。然而，不同子列之间天然并行，因为它们共享同一个父列但彼此之间没有直接依赖。这正是 etree 揭示并行机会的起点。

符号分解阶段完全依赖 etree 来预测 L 的非零模式，无需任何浮点运算。通过从叶节点向上传播非零位置集合，算法能够精确计算每个列所需的存储空间和算术操作数量，从而在数值分解之前评估不同重排序方案的优劣。好的重排序（如近似最小度 AMD 或嵌套剖分）产生的 etree 较浅且子树分布均衡，填充少且并行度高；糟糕的排序则导致深树结构，填充急剧膨胀，并行度大幅下降。

两层并行化：树级与节点级

稀疏 Cholesky 的并行化策略可以分解为两个互补的层次。

树级并行（tree-level parallelism） 关注 etree 的分支结构。树中任意两条独立分支可以被并行处理，因为它们之间不存在数据依赖。以一个典型的三叉树为例：根节点的三个子分支可以分配给三个独立计算核心同时执行。这种粗粒度并行是稀疏 Cholesky 获得大规模并行的主要来源，但也受到树深度的限制 —— 当 etree 较深时，能够同时执行的分支数量有限。

节点级并行（node-level parallelism） 则针对单个超节点（supernode）内部的稠密块操作。当一个超节点规模较大时，其内部的 Cholesky 分解可以被进一步划分为块级任务，利用多线程 BLAS 或 GPU 核函数进行细粒度并行。节点级并行的优势在于利用了稠密矩阵运算的高算术密度，但它的有效性取决于超节点的大小 —— 过小的超节点无法提供足够的并行度。

实际系统通常将两层策略结合使用：首先根据 etree 的分支结构进行粗粒度任务分配，然后在每个超节点内部使用嵌套并行来处理块操作。这种两层方案能够在树宽受限的情况下依然维持较高的核心利用率。

DAG 任务调度：数据流执行与负载均衡

将 etree 转化为有向无环图（DAG）是现代稀疏 Cholesky 运行时的标准做法。在 DAG 中，每个节点对应一个任务（如一个超节点的分块消元、一个三角求解或一个 Schur 补更新），有向边表示数据依赖。当一个任务的所有输入数据就绪后，调度器可以将该任务分配给任意空闲核心执行。

DAG 调度的一个关键设计决策是任务粒度划分。基于 etree 的粗粒度方案将每个超节点作为一个任务，好处是任务数量少、调度开销低，适合通信密集的分布式环境；基于块的细粒度方案则将超节点内部的块作为独立任务，任务数量大幅增加但调度更灵活，能够更好地容忍负载不均衡。

运行时系统通常采用全局就绪队列加工作窃取（work-stealing）的组合策略：新任务在父任务完成后加入就绪队列，空闲核心从队列中取走任务执行。OpenMP 的 task 机制、StarPU 运行时和 PaRSEC 都是这类设计的典型实现。在单节点多核环境下，OpenMP 的 task pragma 配合 dependency clause 可以简洁地表达 etree 依赖关系，编译器生成 DAG 调度代码，无需手动管理队列。

负载均衡是 DAG 调度中的持续挑战。不均衡的 etree（如深度大而宽度小的树结构）会导致核心空闲，而填充密集的列会产生计算热点。基于分层 DAG 调度的方案通过在多个层次上并行化来缓解这一问题：高层使用树级并行，低层使用块级并行，形成流水线式的执行流，让不同深度的子任务能够相互掩盖延迟。

可落地的工程参数

在实际实现中，以下参数对性能有决定性影响。

超节点尺寸选择：典型值为 32 到 128 列。更大的超节点提供更高的 BLAS3 算术强度和更好的节点级并行机会，但会降低树级并行度并增加填充风险。SuiteSparse 的实现通常默认 64 列作为阈值。

块大小（block size）：用于在超节点内部划分任务。常用值为 32 到 64。若系统配备 GPU，块大小应与 GPU 线程块维度匹配（128 到 256），以最大化设备利用率。

重排序策略：对于结构规则的矩阵（如有限元离散化），METIS 的嵌套剖分通常能产生低填充且树宽均匀的 etree；对于不规则稀疏矩阵，AMD 的近似最小度排序更为鲁棒。在实践中，组合使用 AMD 初始化加后续 METIS 重分区可以在填充量和并行度之间取得较好平衡。

运行时选择：多核 CPU 推荐使用 OpenMP task + dependency 机制，实现简单且与现代编译器兼容较好；需要异构计算（CPU + GPU）时，StarPU 或 PaRSEC 提供了更完整的数据移动与异步执行支持，但学习曲线较陡。

内存预分配策略：符号分解阶段确定的非零模式可以用于一次性分配 L 的存储空间，避免分解过程中的动态内存分配开销。CSR 格式配合 etree 导向的压缩列存储（CCS）是标准选择，访问模式应尽量保证列内数据连续以提高缓存命中率。

消元树不仅是稀疏 Cholesky 的理论工具，更是连接符号分析、数值分解与并行执行的关键数据结构。通过构建高质量的 etree，工程师能够在填充最小化与并行度最大化之间做出有据可依的权衡；通过 DAG 调度，理论上的并行潜力可以转化为实际的核心利用率提升。在大规模稀疏线性系统求解场景中，etree 的深度与宽度分析值得作为性能调优的首要步骤纳入工程流程。

资料来源：稀疏直接求解器的 DAG 调度设计研究（Hogg、Reid、Scott，2010）；基于运行时系统的任务化稀疏 Cholesky 求解器（Lopez 等，Cerfacs，2016）。

systems