Numerical Analysis seminars

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.

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.

Daniel Kressner surveys randomized algorithms for joint eigenvalue problems: finding common eigenvectors and their eigenvalues across a family of matrices. The talk covers algorithm development and analysis, with examples from signal processing and multivariate root finding. Joint work with Haoze He and Bor Plestenjak.

Sherry Xiaoye Li surveys randomized construction of hierarchically low-rank matrices, including H/H2, HODLR, HSS, and butterfly formats with different off-diagonal structures. Applications include integral equations, boundary elements, discretized PDEs, and statistical or machine-learning kernel matrices, using either iterative matrix-vector products or direct factorization and solves. Constructing these representations from an implicit dense operator is often the main cost. The talk offers a unified view of sketch distributions, sketch sizes, approximation error bounds, high-performance implementation, applications, and open questions.

Alberto Bucci develops single-pass randomized and streaming low-rank approximation, beginning with large matrices and the strengths and limitations of streaming algorithms. The discussion extends to Tucker, tensor-train, and tree tensor-network representations. Tensor-train approximations are then incorporated into Krylov solvers, including sketched GMRES, to reduce expensive intermediate contractions. The framework is presented as applicable beyond tensor trains to other tensor-network architectures.