用自监督学习优化稀疏矩阵排列，显著减少计算时的内存占用和时间开销。
Self-Supervised Learning for Sparse Matrix Reordering
- 通过多网格图网络捕捉矩阵结构信息，构建路径三元组采样策略
- 提出端点最大链损失函数，使预测得分满足路径不等式约束的三元组更少
- 在SuiteSparse数据集上验证，填充值减少且LU分解加速明显
利用合适的行列重排可显著减少稀疏矩阵分解过程中的填充项（fill-ins），从而降低内存消耗和运行时间。然而，最小化填充项的重排问题属于NP完全问题。现有方法如图论或深度学习手段依赖代理目标，缺乏理论保证。本文基于填充值生成与矩阵稀疏结构间的内在关系——路径三元组不等式，首次引入多网格图网络捕获顶点结构特征，设计基于不等式的三元组采样策略，并提出端点最大链损失函数，以减少满足不等式的三元组数量。在公开的SuiteSparse矩阵集合上的实验表明，该方法在填充值减少和LU分解速度提升方面均优于现有方法。
原文摘要 · Abstract (English)
Rearranging the rows or columns of a sparse matrix using an appropriate ordering can significantly reduce fill-ins, i.e., new nonzeros introduced during matrix factorization, decreasing memory usage and runtime. However, finding an ordering that minimizes fill-ins is NP-complete. Existing approaches, including graph-theoretic and deep learning methods, rely on surrogate objectives without theoretical guarantees. The Fill-Path Theorem reveals a direct and intrinsic relationship between fill-in generation and the sparse structure of the matrix as path triplet inequalities. Here we first employ a multigrid graph network to capture structural information for each vertex. We then derive a triplet sampling strategy based on inequalities. Finally, we introduce an end-max chain loss function to reduce the number of triplets whose predicted scores satisfy these inequalities. Experimental evaluations on the publicly available SuiteSparse matrix collection demonstrate the superiority of the proposed method in terms of both fill-in reduction and speedup in LU factorization time.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。