Linear Systems and Eigenvalue Problems — Problem 3 (Algebraic Multigrid Analysis for Theoretical Computer Scientists)

Definitions and mathematical statement

Let $n$ denote the matrix dimension, and let $\operatorname{nnz}(\mathbf M)$ denote the number of nonzero entries of $\mathbf M$. Write $\mathcal C_n$ for the intended class of $n\times n$ matrices described in the source as "polynomially bounded SWCDDM matrices." This is a placeholder: the supplied record does not define SWCDDM, specify the scalar domain, or explain which quantities are polynomially bounded or with respect to which parameters.

For matrices in a setting where positive semidefiniteness is defined, the Loewner relation $\mathbf A\preceq\mathbf B$ means that $\mathbf B-\mathbf A$ is positive semidefinite. The inverse $\mathbf M^{-1}$ below is the ordinary matrix inverse and therefore presupposes nonsingularity; the supplied record does not explicitly state a nonsingularity hypothesis or prescribe a convention for singular inputs.

Subject to resolving these qualifications, the requested assertion is that Algebraic Multigrid constructs, for every $\mathbf M\in\mathcal C_n$, an implicitly represented symmetric matrix $\mathbf Z$ in time \[ \widetilde O\!\left(\operatorname{nnz}(\mathbf M)\right), \] such that applying $\mathbf Z$, interpreted as computing $\mathbf Zx$ for an input vector $\mathbf x$, takes time $O(\operatorname{nnz}(\mathbf M))$, and \[ c\,\mathbf M^{-1}\preceq\mathbf Z\preceq C\,\mathbf M^{-1} \] for positive constants $c,C$ independent of $n$. These constants express the source's $\Omega(1)$ and $O(1)$ factors. Their permitted dependence on other class parameters is unspecified. The particular Algebraic Multigrid procedure, computational model, and logarithmic factors suppressed by $\widetilde O$ are also unspecified. Thus this is a qualified statement schema requiring clarification, rather than a fully determined algorithmic conjecture.

Short English statement

The source asks for a nearly linear construction of an implicit symmetric constant-factor approximation to the inverse of every polynomially bounded SWCDDM matrix, with linear-time application and approximation constants independent of dimension. The matrix class, polynomial bounds, algorithm, and treatment of singular matrices require clarification. The supplied registry labels the problem open; this draft does not independently verify that status.

Sources

• Local UnsolvedMath registry, permanent ID $800494$, source problem code catalogue entry, in the AMR Open Problem Lists collection. The supplied record attributes the problem to Amsel, Baumann et al., with proposed year 2026, and labels it open.
• Amsel, Baumann et al., Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop (2026), Problem 3. Supplied source URL: https://arxiv.org/abs/2602.05394. The supplied attribution/context is "Algebraic Multigrid Analysis for Theoretical Computer Scientists."
• The supplied provenance records access on 2026-10-16 and extraction by arxiv_latex. This access date and the source/status information are supplied dated curation, not independently verified access or literature assessment for this draft.