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).

Python port

This repo now includes a Python port under src/ltr/ plus Python equivalents of the MATLAB scripts under scripts/ (as they are implemented).

Conda setup (recommended, Python 3.11)

conda create -n banditos-py311 -c conda-forge python=3.11 numpy scipy matplotlib joblib pytest -y
conda activate banditos-py311
pip install -e .

Run tests (Python)

pytest

Install (Python)

python -m pip install -e .

Run (Python)

python scripts/learning.py

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.