Institute for Computational and Experimental Research in Mathematics (ICERM), Brown University

Katarzyna Swirydowicz uses an asynchronous solver on an AMD system to examine the practical implementation of computational linear algebra across CPUs and GPUs. The talk introduces the relevant computational ideas, programming models, and software tools, then considers how algorithmic structure interacts with hardware capabilities. This case study illustrates both the opportunities and implementation challenges of asynchronous methods for large-scale scientific computing on GPU-accelerated systems.

Yousef Saad examines relaxed gradient descent for large-scale optimization. Relaxing the optimal step length in Cauchy's steepest descent avoids its characteristic zigzag behavior and can bring the search direction close to an eigenvector of the Hessian. Once that alignment is sufficiently accurate, properties of the Lanczos method can accelerate convergence. The talk analyzes several such strategies and illustrates them in global minimization of strictly convex functions, retaining the simplicity and low memory requirements that make gradient methods attractive for machine learning.

Matthias Bolten discusses the scalability of multigrid solvers for linear systems arising from discretized partial differential equations. On modern supercomputers, heterogeneous CPUs and GPUs and the widening gap between computation, network, and memory speeds complicate parallelization. Classical multigrid analysis relies on tightly coupled multiplicative components, whereas additive and asynchronous variants relax this coupling. The talk compares approaches to improving high-performance multigrid scalability, including asynchronous execution.

Vasileios Kalantzis develops iterative linear algebra algorithms that tolerate incomplete matrix-vector products in controller-worker cloud systems. Richardson and Chebyshev schemes solve linear systems using randomly available product entries, replacing missing entries with zero. For dominant eigenvectors, modified power iterations substitute zeros, previous entries, or averages of partial iterates for delayed components. The talk presents convergence results in expectation and numerical experiments on sparse matrices for both problem classes.

Evan Coleman studies how asynchronous solvers can recover convergence quality while tolerating stale data, stragglers, and variable delays. At the coordinator, Anderson acceleration connects asynchronous stationary iterations to Krylov methods with changing preconditioners and flexible GMRES. Controlled-delay experiments on high-performance computing infrastructure show that its effectiveness depends on the iteration's coupling density. At the worker, residual-weighted randomized coordinate descent includes Boltzmann weights that interpolate between uniform and greedy selection while preserving convergence guarantees. Both approaches seek better use of computation when information is inconsistent.

Daniel Szyld extends randomized point and block Gauss-Seidel and Gauss-Southwell convergence results from Hermitian positive-definite matrices to certain non-Hermitian classes, including overlapping variables in domain decomposition. The analysis treats a range of sampling probabilities and greedy selection strategies and identifies choices that optimize the bounds. The best expected convergence bounds for randomized methods match those of more expensive deterministic Gauss-Southwell algorithms. These results establish a convergence rate for asynchronous iterations. Joint work with Andreas Frommer.

Erik Boman discusses preconditioning for asynchronous linear solvers. Inner products create synchronization requirements in Krylov methods, while preconditioners can also improve iterations such as Richardson's method. The talk focuses on asynchronous incomplete factorizations and introduces ATS-ILU, an iterative incomplete LU method with synchronous and asynchronous versions that performs competitively with ParILU.

Paritosh Ramanan presents algorithm–hardware co-design for reliable linear algebra and optimization on resistive-memory in-memory computing systems. The distributed MELISO simulation framework supports multiple hardware models, while multilevel error correction makes noisy, low-energy devices useful for matrix-vector multiplication. Simulations report energy improvements of up to five orders of magnitude and latency reductions of up to two for high-dimensional linear algebra. A distributed primal-dual hybrid gradient solver for linear programs combines convergence analysis under device noise with simulated gains of up to two orders in latency and three in energy over GPU baselines on medium-scale problems. Preliminary randomized Kaczmarz results use online signal-to-noise estimates to select rows, comparing this strategy with offline alternatives. The talk closes with open problems in in-memory computation.

Edmond Chow examines how asynchronous updates improve parallel iterative computation. The first part covers asynchronous versions of classical first- and second-order linear iterations, Chebyshev methods, and multigrid, with attention to efficiency and fault tolerance. The second introduces reinforcement learning and asynchronous state-value estimation for finding optimal policies. When the state space is too large to enumerate, these updates focus computational effort on frequently visited regions.

Misha Kilmer develops structured matrix approximation by an invertible matrix-to-tensor transformation, tensor approximation, and a mapping back to matrix space. Different tensor decompositions yield sums of structured Kronecker products, block low-rank matrices, or combinations of both. The framework exposes latent operator structure useful for large computations, and the talk considers where randomization could help. Joint work with Arvind Saibaba at North Carolina State University.

Robert Gower introduces Polar Express for the polar decomposition and matrix sign function, motivated by Muon neural-network training. Using only matrix-matrix products makes the method suited to high-throughput GPUs. Each iteration adapts its polynomial update through minimax optimization, building on Chen and Chow and Nakatsukasa and Freund. Worst-case error minimization gives rapid initial and asymptotic convergence. The talk addresses finite-precision implementation in bfloat16 and reports improved validation loss when training GPT-2 on one billion FineWeb tokens across several learning rates.

David Woodruff develops sampling bounds for estimating the spectrum of symmetric matrices with bounded entries. Principal-submatrix sampling achieves epsilon times n additive error using roughly 1/epsilon² samples, eliminating dependence on n and improving prior epsilon dependence up to logarithmic factors. Squared row-norm sampling gives epsilon times the Frobenius norm accuracy with roughly 1/epsilon² samples, improving a previous 1/epsilon⁸ bound. For bounded-entry positive-semidefinite matrices, O(1/epsilon) sampled columns permit nonadaptive approximation of the leading eigenvector with epsilon times n additive error. Applications include faster dense-matrix spectral sketches and improved sample complexity. Joint work with William Swartworth.

Robert Webber connects partial pivoted Cholesky, effective for nearly low-rank matrices, with Vecchia approximation, effective when inverse Cholesky factors are nearly sparse. Combining a partial Cholesky approximation with a Vecchia approximation of its residual produces another Vecchia approximation of the original matrix with an enlarged sparsity pattern. This unifies several factored matrix-approximation approaches and explains the broader applicability of the Vecchia framework.

Alice Cortinovis presents Adaptive Randomized Pivoting for selecting representative matrix columns through adaptive leverage-score sampling. Its expected Frobenius approximation error matches the optimal existence guarantee. The method is a randomized counterpart to an approach by Osinsky and offers a simpler, less costly alternative to volume sampling with the same theoretical guarantee. The talk extends the strategy to the Discrete Empirical Interpolation Method, cross or skeleton approximation, and Nyström approximation of positive-semidefinite matrices.

Tyler Chen presents randomized block conjugate gradient for one positive-definite linear system. The method can provably outperform conjugate gradient with a broad class of Nyström preconditioners while avoiding explicit preconditioner construction. Its analysis also yields guarantees for new Nyström-preconditioned variants. Applications include computing a complete ridge-regression regularization path and drawing multiple independent samples from a high-dimensional Gaussian distribution.

Michal Dereziński discusses oblivious subspace embeddings, random dimension-reduction maps that approximately preserve all vector norms in a low-dimensional subspace. Such maps support least-squares regression and low-rank approximation, yet efficient optimal embedding dimensions have left a gap between theory and practice. Analyzing universality in sparse random matrices leads to a resolution of the Nelson–Nguyen conjecture up to sub-polylogarithmic factors in SODA 2026. Joint work with Shabarish Chenakkod, Xiaoyu Dong, and Mark Rudelson.

Alex Townsend examines what greedy pivoting can guarantee in rank-revealing factorizations, which remain important alongside randomized sampling and sketching. A local maximum-volume viewpoint gives sharp criteria for reliable rank revelation by pivoted Gaussian elimination and QR. The comparison with pivoted Cholesky on smooth-kernel matrices shows that greedy pivoting there cannot exhibit Kahan-like behavior. These results clarify the theoretical strengths and limitations of deterministic steps in matrix approximation.

Chris Musco studies how to approximate an unknown matrix by a structured one using a limited, adaptively chosen sequence of matrix-vector products. This models operator learning in scientific machine learning as well as computational algorithms. Randomized SVD provides strong guarantees for low-rank targets; analogous results for sparse and hierarchical structures are less developed. The talk presents progress on efficient algorithms for these classes and a broader complexity theory. Joint work with Noah Amsel, Pratyush Avi, Tyler Chen, Prathamesh Dharangutte, Chinmay Hegde, Feyza Duman Keles, Diana Halikias, Cameron Musco, and David Persson.

Davide Palitta introduces the S^T S-SVD, a decomposition of A derived from the SVD of its sketch SA. It is exact with high probability, preserves singular values probabilistically, and makes left singular vectors orthonormal in the sketch-induced seminorm, with lower computational cost. The talk relates this perspective to subspace embeddings and least-squares residuals, assesses sketch quality, and bounds departures from ordinary orthogonality in randomized QR. A further application extends the nearest-orthogonal-matrix problem to S^T S-orthogonality. The work builds on Gilbert, Park, and Wakin and is joint with Valeria Simoncini.

Lior Horesh presents tensor-tensor algebra designed to retain key properties of matrix algebra while representing multidimensional correlations. An Eckart–Young-like tensor representation theorem underpins computationally feasible, provably optimal decompositions. Matrix-mimetic operations allow existing computational workflows to be adapted to tensors. Examples include tensorized neural-network structures and tensor graph convolutional networks for time-evolving graphs. The discussion concludes with tensor group symmetries and extensions to equivariant learning.