# Learning the Markov Decision Process in the Sparse Gaussian Elimination

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 62 references that are in the map.
- First posted on arXiv 30 Sep 2021.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Conservative Q-Learning for Offline Reinforcement Learning](https://mlsanity.com/paper/2006.04779/) (2020)
- [Learning to Optimize DAG Scheduling in Heterogeneous Environment](https://mlsanity.com/paper/2103.06980/) (2021)
- [Geometric Deep Reinforcement Learning for Dynamic DAG Scheduling](https://mlsanity.com/paper/2011.04333/) (2020)
- [Deep differentiable forest with sparse attention for the tabular data](https://mlsanity.com/paper/2003.00223/) (2020)

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

- [Fast Block Linear System Solver Using Q-Learning Schduling for Unified Dynamic Power System Simulations](https://mlsanity.com/paper/2110.05843/) (2021)

## Abstract (arXiv)

We propose a learning-based approach for the sparse Gaussian Elimination. There are many hard combinatorial optimization problems in modern sparse solver. These NP-hard problems could be handled in the framework of Markov Decision Process, especially the Q-Learning technique. We proposed some Q-Learning algorithms for the main modules of sparse solver: minimum degree ordering, task scheduling and adaptive pivoting. Finally, we recast the sparse solver into the framework of Q-Learning. Our study is the first step to connect these two classical mathematical models: Gaussian Elimination and Markov Decision Process. Our learning-based algorithm could help improve the performance of sparse solver, which has been verified in some numerical experiments.