Learning to relax

This repository contains code to reproduce the empirical results in our paper on learning-augmented linear system solvers, specifically successive over-relaxation (SOR) and Symmetric SOR-preconditioned conjugate gradient (CG).

Script descriptions:

asymptotic.m: computes bounds on the performance of SOR across different relaxation parameters
cg.m: computes bounds on the performance of CG across different relaxation parameters
comparators.m: computes average SOR performance across distributions over linear systems
contextual.m: evaluates contextual bandit algorithms for setting the SOR relaxation parameter
degenerate.m: compares SOR performance on degenerate and stochastic target vectors
h2d.m: evaluates different approaches for accelerating a heat equation simulation
learning.m: compares several fixed settings of the SOR relaxation parameter with a bandit algorithm

Reference:

Mikhail Khodak, Edmond Chow, Maria-Florina Balcan, Ameet Talwalkar. Learning to relax: Setting solver parameters across a sequence of linear system instances. ICLR 2024.