IIIT Hyderabad Publications 


Using Reinforcement Learning to Improve Heuristic Sparse Matrix AlgorithmsAuthor: Arpan Dasgupta 2018111010 Date: 20231108 Report no: IIIT/TH/2023/183 Advisor:Pawan Kumar AbstractA 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 fillin 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 fillin. A significant fillin 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 fillin before the decomposition. However, finding an optimal reordering algorithm that leads to minimal fillin during such decomposition is known to be a NPhard 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, MonteCarlo 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 nonzeros in the LU decomposition as compared to existing stateoftheart 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 Full thesis: pdf Centre for Security, Theory and Algorithms 

Copyright © 2009  IIIT Hyderabad. All Rights Reserved. 