Linear Systems and Eigenvalue Problems — Problem 5

Definitions and mathematical statement

For a matrix $A$, let $\operatorname{nnz}(A)$ denote the number of its nonzero entries. The supplied source asks the following question in the direct access model:

Can an $(n,k,0,\kappa)$ linear system $Ax=b$ be solved to high accuracy using \[ \widetilde O\!\left(k^\omega+\operatorname{nnz}(A)\,\kappa\right) \] arithmetic operations?

Here $(n,k,0,\kappa)$ is retained as source notation. The supplied record does not define this class of systems, the admissible parameter ranges, the scalar domain, the matrix hypotheses, or the meaning of the zero parameter. It also does not specify the access operations, the accuracy criterion, the meaning of $\omega$, or the factors suppressed by $\widetilde O$. Thus the displayed question preserves the requested bound, but the supplied evidence does not determine a fully quantified algorithmic statement.

The source motivates the question by stating that the matrix-vector product model is particularly relevant for sparse matrices, where the extra cost paid by the Krylov solver is only \[ \widetilde O\!\left(\operatorname{nnz}(A)\,k\right). \] It explicitly qualifies this comparison by noting additional costs in finite precision arithmetic. It also states that many randomized linear algebra methods exploit input sparsity, motivating the possibility of a similar improvement in the direct access model. These are supplied background claims, not additional hypotheses or independently verified results.

Short English statement

The question asks whether sparse linear systems in the source's undefined $(n,k,0,\kappa)$ class admit a direct access algorithm with arithmetic cost $\widetilde O(k^\omega+\operatorname{nnz}(A)\kappa)$ and high accuracy. The system class, accuracy requirement, and computational conventions require clarification before a precise quantified formulation is possible.

Sources

• Local UnsolvedMath registry, permanent ID $800496$, source code catalogue entry, title: Linear Systems and Eigenvalue Problems --- Problem 5; collection: AMR Open Problem Lists. The registry attributes the problem to Amsel, Baumann et al., with proposed year 2026, and labels it open. This status is supplied curation, not an independently verified mathematical or literature assessment.
• Amsel, Baumann et al., Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop (2026), Problem 5. Supplied source URL: https://arxiv.org/abs/2602.05394.
• Supplied provenance records access on 2026-10-16 and extraction by arxiv_latex. These are supplied provenance statements; no independent source visit or verification is claimed. The registry records upstream revision d371ee917ac9647fbb06cd6fc529deec6f3dda82 and update time 2026-10-16T14:00:00Z.