# Alpha Elimination: Using Deep Reinforcement Learning to Reduce Fill-In during Sparse Matrix Decomposition

arXiv: https://arxiv.org/abs/2310.09852 · HTML: https://mlsanity.com/paper/2310.09852/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 36 references that are in the map.
- First posted on arXiv 15 Oct 2023.

## Builds on (most cited first, 8 of 8)

- [Neural Architecture Search with Reinforcement Learning](https://mlsanity.com/paper/1611.01578/) (2016)
- [End-to-End Training of Deep Visuomotor Policies](https://mlsanity.com/paper/1504.00702/) (2015)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Learning Hand-Eye Coordination for Robotic Grasping with Deep Learning and Large-Scale Data Collection](https://mlsanity.com/paper/1603.02199/) (2016)
- [Learning to Optimize](https://mlsanity.com/paper/1606.01885/) (2016)
- [Qubit Routing using Graph Neural Network aided Monte Carlo Tree Search](https://mlsanity.com/paper/2104.01992/) (2021)
- [Effects of Spectral Normalization in Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2212.05331/) (2022)
- [marl-jax: Multi-Agent Reinforcement Leaning Framework](https://mlsanity.com/paper/2303.13808/) (2023)

## Built on by (most cited first, 4 of 4)

- [Factorization-in-Loop: Proximal Fill-in Minimization for Sparse Matrix Reordering](https://mlsanity.com/paper/2511.09093/) (2025)
- [Bridging the Gap between Sparse Matrix Reordering and Factorization: A Deep Learning Framework for Fill-in Reduction](https://mlsanity.com/paper/2605.17339/) (2026)
- [Learning Fill-in Reduction Ordering via Graph Policy Optimization for Sparse Matrices](https://mlsanity.com/paper/2605.17362/) (2026)
- [Self-Supervised Learning for Sparse Matrix Reordering](https://mlsanity.com/paper/2605.17403/) (2026)

## Abstract (arXiv)

A large number of computational and scientific methods commonly require decomposing a sparse matrix into triangular factors as LU decomposition. A common problem faced during this decomposition is that even though the given matrix may be very sparse, the decomposition may lead to a denser triangular factors due to fill-in. A significant fill-in may lead to prohibitively larger computational costs and memory requirement during decomposition as well as during the solve phase. To this end, several heuristic sparse matrix reordering methods have been proposed to reduce fill-in before the decomposition. However, finding an optimal reordering algorithm that leads to minimal fill-in during such decomposition is known to be a NP-hard problem. A reinforcement learning based approach is proposed for this problem. The sparse matrix reordering problem is formulated as a single player game. More specifically, Monte-Carlo tree search in combination with neural network is used as a decision making algorithm to search for the best move in our game. The proposed method, alphaElimination is found to produce significantly lesser non-zeros in the LU decomposition as compared to existing state-of-the-art heuristic algorithms with little to no increase in overall running time of the algorithm. The code for the project will be publicly available herefootnoteurlhttps://github.com/misterpawan/alphaEliminationPaper.