Factorization-in-Loop:Proximal Fill-in Minimization for Sparse Matrix Reordering
Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (1) · 730-737
DOI: 10.1609/aaai.v40i1.37039 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Ziwei Li und 4 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).
Abstract (Originalsprache)
Fill-ins are new nonzero elements in the summation of the upper and lower triangular factors generated during LU factorization. For large sparse matrices, they will increase the memory usage and computational time, and be reduced through proper row or column arrangement, namely matrix reordering. Finding a row or column permutation with the minimal fill-ins is NP-hard, and surrogate objectives are designed to derive fill-in reduction permutations or learn a reordering function. However, there is no theoretical guarantee between the golden criterion and these surrogate objectives. Here we propose to learn a reordering network by minimizing l1 norm of triangular factors of the reordered matrix to approximate the exact number of fill-ins. The reordering network utilizes a graph encoder to predict row or column node scores. For inference, it is easy and fast to derive the permutation from sorting algorithms for matrices. For gradient based optimization, there is a large gap between the predicted node scores and resultant triangular factors in the optimization objective. To bridge the gap, we first design two reparameterization techniques to obtain the permutation matrix from node scores. The matrix is reordered by multiplying the permutation matrix. Then we introduce the factorization process into the objective function to arrive at target triangular factors. The overall objective function is optimized with the alternating direction method of multipliers and proximal gradient descent. Experimental results on benchmark sparse matrix collection SuiteSparse show the fill-in and LU factorization time reduction of our proposed method is 0.2% and 17.8% compared with state-of-the-art baselines.
Zitieren
APA
Li, Z., Niu, S., Yuan, T., Li, H., & Wu, W. (2026). Factorization-in-Loop:Proximal Fill-in Minimization for Sparse Matrix Reordering. Proceedings of the AAAI Conference on Artificial Intelligence, 40(1), 730-737. https://doi.org/10.1609/aaai.v40i1.37039
Vancouver
Li Z, Niu S, Yuan T, Li H, Wu W. Factorization-in-Loop:Proximal Fill-in Minimization for Sparse Matrix Reordering. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(1):730-737. doi:10.1609/aaai.v40i1.37039
BibTeX
@article{Li2026,
author = {Li, Ziwei and Niu, Shuzi and Yuan, Tao and Li, Huiyuan and Wu, Wenjia},
title = {Factorization-in-Loop:Proximal Fill-in Minimization for Sparse Matrix Reordering},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
year = {2026},
volume = {40},
number = {1},
pages = {730--737},
doi = {10.1609/aaai.v40i1.37039}
}
EUVIMED