Abstract: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.
| Comments: | Accepted by DASFAA 2026 |
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2605.17403 [cs.LG] |
| (or arXiv:2605.17403v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2605.17403 arXiv-issued DOI via DataCite (pending registration) |
From: Ziwei Li [view email]
[v1]
Sun, 17 May 2026 11:54:12 UTC (462 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。