Causal Structure Learning for Sparse Matrix Fill-in Reduction

The performance of sparse direct solvers is fundamentally governed by fill-in, i.e. new nonzero entries arising from the LU factorization of a sparse matrix, as they dictate memory footprint and subsequent computation time. For decades, a variety of graph-theoretic algorithms have aimed to minimize fill-in, a problem known to be both NP-hard and critically important. While recent deep learning methods, optimizing surrogate fill-in objectives, show empirical promise and can outperform classical algorithms on certain matrices, they offer limited interpretability into the underlying mechanism of fill-in generation. To address this, we propose a novel reordering approach, Causal Triplet Structure Learning (CTS), which is grounded in the Fill-Path Theorem and reduces arbitrary-length fill-paths to length-two candidate triplets, identifies the causal structures that trigger fill-in, and intervenes to block their formation. Empirically, we design a multigrid-style GAT with KAN activations to learn vertex embeddings and introduce a causal triplet loss that discourages such structures during training. Experiments on the SuiteSparse Matrix Collection demonstrate that our method reduces fill-in by 6$\times$, leading to 12$\times$ speedup in factorization time compared to state-of-the-art methods on Chemical Process Simulation and Computational Fluid Dynamics matrices.

Large scientific and engineering simulations often require computers to solve very large systems of equations. These systems are usually represented by matrices with many empty entries, which should make them efficient to store and process. However, during the solving process, many new entries can appear. This phenomenon, known as fill-in, can greatly increase memory use and computation time. This paper proposes a learning-based method to reduce fill-in before the solving process begins. Instead of only trying to guess a good ordering of the matrix entries, our method studies why fill-in happens. We show that fill-in can be understood through small three-node structures in the graph representation of a matrix. By learning to identify and avoid these structures, the method produces better orderings that lead to fewer extra entries during factorization. Experiments on widely used sparse matrix benchmarks from scientific and engineering applications show that the proposed method reduces fill-in and speeds up matrix factorization compared with existing methods. This can make large-scale simulations more efficient, reduce memory requirements, and potentially lower energy consumption in scientific computing workflows.