Uniformly effective algebraic multigrid for diagonally dominant systems
Fix a positive integer $c$. Let $M \in \mathbb{R}^{n \times n}$ be symmetric, with $M_{ij} \le 0$ for $i \ne j$ and $M_{ii} \ge \sum_{j \ne i} |M_{ij}|$ for every $i$, such that every row with equality is joined, through a chain of nonzero off-diagonal entries, to a row with strict inequality; assume $|M_{ij}| \le n^c$ and $n^c M_{ij} \in \mathbb{Z}$ for all $i, j$. Such a matrix is positive definite. Write $\preceq$ for the positive semidefinite order and $\operatorname{nnz}(M)$ for the number of nonzero entries, and let $\widetilde O$ hide factors polylogarithmic in $n$; constants may depend on $c$. For the finite-difference discretization of the Poisson equation with Dirichlet boundary conditions, the smoothing and approximation properties give multigrid convergence rates independent of the mesh size, and multigrid then solves it with $O(n)$ work.
Problem. Construct an algebraic multigrid algorithm, with explicitly specified smoothing, interpolation and coarse-grid operators, whose setup takes $\widetilde O(\operatorname{nnz}(M))$ operations and which yields a symmetric matrix $Z$ whose action $z \mapsto Zz$ takes $O(\operatorname{nnz}(M))$ operations, with $$a M^{-1} \preceq Z \preceq b M^{-1}$$ for constants $0 < a \le b < \infty$ independent of $n$ and $M$.
Source: Amsel et al. (2026), Problem 2.3, from the Simons Institute workshop on linear systems and eigenvalue problems (2025); stated with explicitly specified multigrid components by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- NA — Numerical Analysis
- Keywords
- AIM Open Applied Problems, algebraic multigrid, diagonally dominant matrices, preconditioners
References
@misc{amsel2026,
author = {Amsel, Noah and Baumann, Yves and Beckman, Paul and B{\"u}rgisser, Peter and Cama{\~n}o, Chris and Chen, Tyler and Chow, Edmond and Damle, Anil and Derezinski, Michal and Embree, Mark and Epperly, Ethan N. and Falgout, Robert and Fornace, Mark and Greenbaum, Anne and Greif, Chen and Halikias, Diana and Huang, Zhen and Jarlebring, Elias and Koutis, Yiannis and Kressner, Daniel and Kyng, Rasmus and Liesen, J{\"o}rg and Lok, Jackie and Meyer, Raphael A. and Nakatsukasa, Yuji and Pearce, Kate and Peng, Richard and Persson, David and Rebrova, Eliza and Schneider, Ryan and Shah, Rikhav and Solomonik, Edgar and Srivastava, Nikhil and Townsend, Alex and Webber, Robert J. and Williams, Jess},
title = {Linear Systems and Eigenvalue Problems: Open Questions from a {S}imons Workshop},
year = {2026},
eprint = {2602.05394},
archivePrefix = {arXiv},
note = {Revised August 2026 (v3)},
}
@article{xu2017,
author = {Xu, Jinchao and Zikatanov, Ludmil},
title = {Algebraic multigrid methods},
journal = {Acta Numer.},
volume = {26},
year = {2017},
pages = {591--721},
doi = {10.1017/S0962492917000083},
}
@misc{aim-universal-algebraic-multigrid,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Uniformly effective algebraic multigrid for diagonally dominant systems}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/040-universal-algebraic-multigrid.md},
note = {Entry 040 at commit a153f46, 2026-10-13},
}
Resolution claims
We show that Laplacian and symmetric diagonally dominant (SDD) matrices can be well approximated by linear-sized sparse Cholesky factorizations. We show that these matrices have constant-factor approximations of the form $L L^{T}$, where $L$ is a lower-triangular matrix with a number of nonzero entries linear in its dimension. Furthermore linear systems in $L$ and $L^{T}$ can be solved in $O …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-25 | Open → Partially resolved | The registry's curators | Sparsified Cholesky Solvers for SDD linear systems v1 recorded from arXiv:1506.08204v2. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00398, "Uniformly effective algebraic multigrid for diagonally dominant systems", clopen.solutions.