Learning the Markov Decision Process in the Sparse Gaussian Elimination

Abstract

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.

arXiv comment13 pages,2 figures

References in corpus (5)

• Semi-Supervised Classification with Graph Convolutional Networks
• Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems
• Conservative Q-Learning for Offline Reinforcement Learning
• Learning to Optimize DAG Scheduling in Heterogeneous Environment
• Deep differentiable forest with sparse attention for the tabular data

Cited by in corpus (1)

• Fast Block Linear System Solver Using Q-Learning Schduling for Unified Dynamic Power System Simulations