Alpha Elimination: Using Deep Reinforcement Learning to Reduce Fill-In
  during Sparse Matrix Decomposition
Arpan Dasgupta Pawan Kumar
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
here\footnote{\url{https://github.com/misterpawan/alphaEliminationPaper}}.