Self-Supervised Learning for Sparse Matrix Reordering
For scientific computing and linear algebra, this provides a principled approach to a classic NP-complete problem with measurable improvements over existing heuristics.
Proposed a self-supervised learning method for sparse matrix reordering that directly minimizes fill-ins using the Fill-Path Theorem, achieving up to 30% fill-in reduction and 2x speedup in LU factorization on SuiteSparse matrices.
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.