ReFill: Reinforcement Learning for Fill-In Minimization
Elfarouk Harb, Ho Shan Lam · 2025
Read ReFill: Reinforcement Learning for Fill-In Minimization by Elfarouk Harb, Ho Shan Lam (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-16130.txt.
Introduction
Elfarouk Harb and Ho Shan Lam teach a machine to order eliminations in sparse systems in a paper from two thousand twenty-five. Solving large sparse equations by elimination creates fill-in, new nonzeros that swell memory and cost. Minimizing fill-in is provably hard, and classic heuristics adapt poorly across problems.
Their framework, ReFill, uses reinforcement learning with a graph neural network. The network learns ordering strategies tuned to each matrix's structure. In experiments it beat strong classical heuristics at cutting fill-in. The authors highlight the untapped promise of learning methods for this old, well-studied problem. Adaptive ordering could speed solvers across science, machine learning, and optimization.
Catalog record
| CREATOR | Elfarouk Harb, Ho Shan Lam |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-16130
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
ReFill: Reinforcement Learning for Fill-In Minimization Elfarouk Harb, Ho Shan Lam Abstract Efficiently solving sparse linear systems 𝐀𝐱 = 𝐛 \mathbf{Ax}=\mathbf{b} , where 𝐀 \mathbf{A} is a large, sparse, symmetric positive semi-definite matrix, is a core challenge in scientific computing, machine learning, and optimization. A major bottleneck in Gaussian elimination for these systems is fill-in —the creation of non-zero entries that increase memory and computational cost. Minimizing fill-in is NP-hard, and existing heuristics like Minimum Degree and Nested Dissection offer limited adaptability across diverse problem instances. We introduce ReFill , a reinforcement learning framework enhanced by Graph Neural Networks (GNNs) to learn adaptive ordering strategies for fill-in minimization. ReFill trains a GNN-based heuristic to predict efficient elimination orders, outperforming traditional heuristics by dynamically adapting to the structure of input matrices. Experiments demonstrate that ReFill outperforms strong heuristics in reducing fill-in, highlighting the untapped potential of learning-based methods for this well-studied classical problem. 1 Introduction and Background In this paper, we consider the fundamental problem of solving the system of equations {\bf Ax}={\bf b} , where {\bf A} is a n\times n symmetric positive semi-definite matrix. Such sparse linear systems show up naturally in scientific computing, machine learning, theoretical computer science, and scalable optimization [ 12 , 8 , 5 , 7 , 17 , 42 , 40 , 41 ] . These systems are instrumental in numerous domains ranging from finite element analysis to large graph-based models in machine learning. Typically, Gaussian elimination serves as a primary solution method. However, the efficiency of Gaussian elimination is highly sensitive to matrix ordering, as different variable elimination orderings introduce varying levels of fill-in —the additional non-zero entries created during variable elimination, which directly impact memory usage and runtime. If the matrix {\bf A} is dense, then Gaussian Elimination requires \Theta(n^{3}) time. However, if {\bf A} is sparse, we might be able to save time by avoiding explicit manipulation of zeros or fill-in. Reducing fill-in, therefore, is critical for optimizing resource use and enabling scalable computation in high-dimensional settings. Figure 1 : (a) A symmetric positive-definite matrix \mathbf{A} and its factorization after Gaussian elimination with a fixed variable elimination order. This ordering introduces three fill-in entries at positions A_{2,4} , A_{2,5} , and A_{4,5} , which were initially zero but became non-zero during elimination. (b) The same matrix after applying a permutation \pi=(5,1,2,3,4) via permutation matrix \mathbf{P}_{\pi} , which reorders the rows and columns of \mathbf{A} by moving the first row to the last row, and the first column to the last position resulting in matrix \mathbf{A}^{\prime} . This reordering leads to a matrix where Gaussian elimination introduces no fill-in, resulting in lower memory usage and faster computation. One way to minimize fill-in during Gaussian elimination is to reorder the rows and columns of {\bf A} to solve an equivalent system \mathbf{PAP}^{T} , where \mathbf{P} denotes a permutation matrix. See Figure 1 for an example where different variable elimination order in Gaussian elimination leads to fewer fill-in. This approach, introduced in the seminal works by Tarjan and Rose [ 40 , 41 , 42 ] , reinterprets fill-in into a graph-theoretic perspective, thereby providing structural insights into sparse matrices. Specifically, we will recap elimination orders and fill-in minimization within the context of graph theory. Let us consider a symmetric positive semi-definite system \mathbf{Ax}=\mathbf{b} , where the sparse structure of \mathbf{A} can be represented by an undirected graph G(\mathbf{A}) . In this graph, each vertex corresponds to a row (or column) in \mathbf{A} , with an edge ij,i\neq j present if \mathbf{A}_{i,j}\neq 0 . The process of Gaussian elimination on \mathbf{A} can then be interpreted in terms of eliminating vertices in G(\mathbf{A}) . Specifically, eliminating a vertex i in G^{\prime} entails connecting all neighbors of i (denoted \mathcal{N}_{G^{\prime}}(i) ) to form a clique, followed by the deletion of i from G^{\prime} . This in turn adds “fill-in” edges, neighbors of i that were previously not connected. Each permutation matrix \mathbf{P} determines a specific ordering \pi of the vertices. Executing Gaussian elimination according to this ordering \pi=(\pi(1),\ldots,\pi(n)) means sequentially eliminating variables in the specified order. The edges that emerge from this process are collectively known as the fill-in . See Figure 2 for an illustration. To formalize this process, consider the iterative graph sequence associated with an ordering \pi : 1. Set G^{(0)}\leftarrow G(\mathbf{A}) . 2. For each i=1 to n : • Define \mathcal{P}_{\pi}(i)=\{(v,w):v,w\in\mathcal{N}_{G^{(i-1)}}(\pi(i)),v\neq w,(v,w)\not\in E(G^{i-1})\} as the fill-in edges that will be added by eliminating \pi(i) . • Eliminate \pi(i) from G^{(i-1)} , resulting in the updated graph G^{(i)}=G^{(i-1)}\cup\mathcal{P}_{\pi}(i)\setminus\{\pi(i)\} . Figure 2 : (a) The matrix \mathbf{A} from Figure 1 and its corresponding graph representation G(\mathbf{A}) . Vertices are eliminated in the order 1,2,3,4,5 . Eliminating vertex 1 forces its neighbors (2,4,5) to form a clique, introducing three fill-in edges (2,4),(2,5),(4,5) (shown in red) before vertex 1 is removed. These fill-in edges directly correspond to the non-zero entries added during Gaussian elimination in Figure 1 . (b) The permuted matrix \mathbf{A}^{\prime} and its associated graph G(\mathbf{A}^{\prime}) , obtained by reordering the rows and columns of \mathbf{A} by moving the first row to be the last row, and the first column to be the last column (i.e. according to the permutation \pi=(51234) ). Although the graph is structurally identical to G(\mathbf{A}) , the new vertex ordering eliminates all variables without introducing any fill-in edges, showing how proper ordering prevents unnecessary fill-in. The edges E_{\pi}=\cup_{i}\mathcal{P}_{\pi}(i) thus represent the fill-in that occurs when performing Gaussian elimination in the order \pi . The following theorem offers a characterization of the fill-in associated with any ordering \pi . Theorem 1.1 ( [ 42 ] ) . Given an ordering \pi and assuming no ‘‘lucky cancellations’’ 1 1 1 Lucky cancellations happens for some matrices {\bf A} where some non-zero elements incidentally get cancelled to zeros when eliminating a variable. In practice, this is unlikely to happen, so one often ignores their effect. , an edge ij\in E_{\pi} exists if and only if i\neq j and there exists a path v_{0}=i,v_{1},\dots,v_{k},v_{k+1}=j in G(\mathbf{A}) satisfying \max_{1\leq r\leq k}\pi(v_{r})<\min(\pi(i),\pi(j)). Unfortunately, while we can characterize the fill-in for any given ordering \pi , finding an optimal ordering \pi^{\ast} that minimizes the fill-in is known to be NP-Complete [ 55 ] . Moreover, several inapproximation results are known. For example in [ 9 ] , the existence of polynomial time approximation schemes for this problem is ruled out, assuming {\bf P}\neq{\bf NP} , and the existence of a 2^{O(n^{1-\delta})} -time approximation schemes for any positive \delta is also ruled out, assuming the Exponential Time Hypothesis. Hence apriori, the problem might seems hopeless to tackle. Despite the theoretical computational difficulty of this problem, several heuristics, such as the Minimum Degree, Minimum Fill-In, and Nested Dissection heuristics, have been proposed and extensively studied in the literature [ 31 , 17 , 41 , 42 ] . These heuristics remain widely used in practice for fill-in minimization and are surprisingly effective in practice, often being within a few percentages off from the optimal fill-in order. Minimum Degree Heuristic, MDH This heuristic is a natural greedy algorithm, initially introduced by Markowitz [ 31 ] , and was popularized by Rose in their PhD thesis. The algorithm is