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.