用图神经网络优化稀疏矩阵填充顺序，显著降低内存与计算开销。
Learning Fill-in Reduction Ordering via Graph Policy Optimization for Sparse Matrices
- 构建双视角图神经网络，融合全局与局部填充信息建模
- 在SuiteSparse数据集上平均减少29.3次填充、31.3峰值内存
- 适合需要高效稀疏求解的科学计算与工程仿真场景
大型稀疏求解器中的矩阵重排序旨在寻找一种排列方式，以最小化分解过程中的填充项，从而降低内存占用与计算量。由于最小填充排序问题为NP完全问题，且填充情况隐含于稀疏模式中，现有方法多采用图论启发式算法。现有的强化学习方法或忽略稀疏模式（丢失全局填充信息），或缺乏局部精确填充反馈。本文提出一种图策略优化方法：策略网络与价值网络均采用多跳图神经网络结构来嵌入全局填充信息；策略网络进一步通过符号分解与图交互，提取每一步的局部填充项，利用自适应饱和函数将反馈对齐至价值网络，提升收敛性。在SuiteSparse Matrix Collection数据集上，本方法相较当前最优基线，平均填充项减少29.3，峰值内存使用降低31.3。
原文摘要 · Abstract (English)
Matrix reordering in large sparse solvers seeks a permutation that minimizes factorization fill-in to reduce memory and computation. Because the minimum fill-in ordering problem is NP-complete and fill-in is implicit in the sparsity pattern, graph-theoretic heuristics are used. Existing reinforcement learning methods either ignore sparsity patterns--missing the global fill-in--or lack local exact fill-in feedback. We propose a graph policy optimization method, modeling fill-ins from global and local views: both the policy and value networks use a multi-hop graph neural backbone to embed global fill-in; the policy further interacts with symbolic factorization over graphs to extract local, step-level fill-ins, and the resulting feedback is aligned with the value network via an adaptive saturation function to improve convergence. On the SuiteSparse Matrix Collection, our method achieves mean reductions of 29.3 in fill-ins and 31.3 in peak memory usage over state-of-the-art baselines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。