Anne Greenbaum

Noah Amsel, Yves Baumann, Paul Beckman et al. · berkeley

This document presents a series of open questions arising in matrix computations, i.e., the numerical solution of linear algebra problems. It is a result of working groups at the workshop Linear Systems and Eigenvalue Problems, which was organized at the Simons Institute for the Theory of Computing program on Complexity and Linear Algebra in Fall 2025. The complexity and numerical solution of linear algebra problems is a crosscutting area between theoretical computer science and numerical analysis. The value of the particular problem formulations here is that they were produced via discussions between researchers from both groups. The open questions are organized in five categories: iterative solvers for linear systems, eigenvalue computation, low-rank approximation, randomized sketching, and other areas including tensors, quantum systems, and matrix functions.

Anne Greenbaum, Hexuan Liu, Tyler Chen · uw

We consider three mathematically equivalent variants of the conjugate gradient (CG) algorithm and how they perform in finite precision arithmetic. It was shown in [{\em Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences}, Lin.~Alg.~Appl., 113 (1989), pp.~7-63] that under certain conditions the convergence of a slightly perturbed CG computation is like that of exact CG for a matrix with many eigenvalues distributed throughout tiny intervals about the eigenvalues of the given matrix, the size of the intervals being determined by how closely these conditions are satisfied. We determine to what extent each of these variants satisfies the desired conditions, using a set of test problems and show that there is significant correlation between how well these conditions are satisfied and how well the finite precision computation converges before reaching its ultimately attainable accuracy. We show that for problems where the width of the intervals containing the eigenvalues of the associated exact CG matrix makes a significant difference in the behavior of exact CG, the different CG variants behave differently in finite precision arithmetic. For problems where the interval width makes little difference or where the convergence of exact CG is essentially governed by the upper bound based on the square root of the condition number of the matrix, the different CG variants converge similarly in finite precision arithmetic until the ultimate level of accuracy is achieved, although this ultimate level of accuracy may be different for the different variants. This points to the need for testing new CG variants on problems that are especially sensitive to rounding errors.

Michel Crouzeix, Anne Greenbaum

We extend the proof in [M.~Crouzeix and C.~Palencia, {\em The numerical range is a $(1 + \sqrt{2})$-spectral set}, SIAM Jour.~Matrix Anal.~Appl., 38 (2017), pp.~649-655] to show that other regions in the complex plane are $K$-spectral sets. In particular, we show that various annular regions are $(1 + \sqrt{2} )$-spectral sets and that a more general convex region with a circular hole or cutout is a $(3 + 2 \sqrt{3} )$-spectral set. We demonstrate how these results can be used to give bounds on the convergence rate of the GMRES algorithm for solving linear systems and on that of rational Krylov subspace methods for approximating $f(A)b$, where $A$ is a square matrix, $b$ is a given vector, and $f$ is a function that can be uniformly approximated on such a region by rational functions with poles outside the region.

Trevor Caldwell, Anne Greenbaum, Kenan Li

In [{\em The Numerical Range is a $(1 + \sqrt{2})$-Spectral Set}, SIAM J. Matrix Anal. Appl. 38 (2017), pp.~649-655], Crouzeix and Palencia show that the numerical range of a square matrix or linear operator $A$ is a $(1 + \sqrt{2})$-spectral set for $A$; that is, for any function $f$ analytic in the interior of the numerical range $W(A)$ and continuous on its boundary, the inequality $\| f(A) \| \leq (1 + \sqrt{2} ) \| f \|_{W(A)}$ holds, where the norm on the left is the operator 2-norm and $\| f \|_{W(A)}$ on the right denotes the supremum of $| f(z) |$ over $z \in W(A)$. In this paper, we show how the arguments in their paper can be extended to show that other regions in the complex plane that do {\em not} necessarily contain $W(A)$ are $K$-spectral sets for a value of $K$ that may be close to $1 + \sqrt{2}$. We also find some special cases in which the constant $(1 + \sqrt{2})$ for $W(A)$ can be replaced by $2$, which is the value conjectured by Crouzeix.