Using Reinforcement Learning to Improve Heuristic Sparse Matrix Algorithms

Abstract

A large number of important mathematical problems do not have perfect solutions which can be computed in a polynomial time. The solution to these problems is often calculated by using polynomial time heuristic algorithms which produce solve the problem with some approximation. If the matrix algorithm can be effectively formulated as a game, reinforcement learning can be used instead of the usual heuristics to improve the quality of the approximation. One such problem is to reduce the fill-in produced during matrix decomposition. A large number of computational and scientific methods commonly require decomposing a sparse matrix into triangular factors as LU decomposition. A common problem that is 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 a neural network is used as a decision making algorithm to search for the best move in our game. The proposed method, Alpha Elimination was 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. In addition to the main problem of the thesis, work was also conducted in the field of extreme classification. In this area, a fast algorithm called LightDXML was developed to solve the problem of extreme classification at scale