Numerical Analysis seminars

Daniel Szyld analyzes rand-cholQR, a randomized method for tall-and-skinny QR factorization using one or two sketch matrices. For numerically full-rank inputs, its orthogonality error is bounded with high probability at the scale of unit roundoff. NVIDIA A100 experiments compare multisketching with CholeskyQR2, reporting comparable or better speed and stronger stability with little additional memory or computation. Joint work with Andrew Higgins, Erik Boman, and Ichitaro Yamazaki.

Per-Gunnar Martinsson presents randomized black-box algorithms that compress rank-structured matrices, including H-matrices and HSS matrices, into data-sparse representations. Access is through matrix-vector products, which suits Schur-complement construction and matrix multiplication. When both the operator and its transpose admit O(N) application, the overall compression can also have linear complexity. A featured method combines compression and factorization of an H-matrix under strong admissibility.

Yuji Nakatsukasa explains how CUR decompositions approximate a matrix using selected columns and rows, without inspecting every entry once the indices are chosen. Near-optimal CUR approximations exist relative to the truncated singular value decomposition, and efficient algorithms make them useful for large problems. The talk covers computation and theoretical guarantees before exploring applications to approximation theory, model reduction, and parameter-dependent problems.

Ilse Ipsen examines full-column-rank least-squares systems solved through normal equations with symmetric or nonsymmetric randomized preconditioning computed at lower arithmetic precision. Effective preconditioning can deliver accuracy close to QR-based MATLAB backslash even for badly conditioned matrices. The analysis separates the solution's accuracy from the accuracy of the preconditioner: the original least-squares residual controls the error. The talk develops realistic relative-error perturbation bounds. Joint work with James Garrison.

Charles Bordenave revisits von Neumann and Goldstine's proposal to model numerical computing errors as probabilistic noise. This perspective helps explain large errors in computed eigenvalues of badly conditioned matrices. Toeplitz matrices provide a case study: they occur throughout mathematics, physics, and engineering, are highly sensitive to small perturbations, and possess a rich spectral theory that supports precise descriptions under random perturbations. The talk is based on joint work with Mireille Capitaine and François Chapon.

Matrix multiplication underpins scientific computing and artificial intelligence, yet practical numerical libraries and hardware accelerators commonly retain the classical cubic-time algorithm despite decades of subcubic theoretical advances. This talk reviews the effort to make faster multiplication algorithms useful in practice. It examines why arithmetic complexity alone does not determine performance: some algorithms require enormous matrices or incur large hidden constants, while communication costs, numerical stability and the match between software and hardware create additional obstacles. The historical perspective connects asymptotic algorithm design to actual performance and power consumption.

This talk examines randomized sampling methods for approximating positive semidefinite matrices. Fast leverage-score approximation combined with the Nystrom method yields provably accurate, linear-time algorithms for kernel ridge regression and kernel principal-component analysis, avoiding the usual quadratic-time cost. Related sampling techniques give relative-error low-rank approximations of positive semidefinite matrices in sublinear time without assumptions about incoherence or condition number. The results illustrate how randomized algorithms can exploit positive semidefinite structure beyond the capabilities of traditional methods. The talk concludes with open questions, particularly about oblivious sketches of kernel matrices.

Building on the preceding linear-algebra tutorials, this lecture presents two further approaches to matrix sketching: leverage-score sampling and the Subsampled Randomized Hadamard Transform. It examines how these methods produce effective compressed matrix representations for a variety of applications.

This tutorial surveys nearly optimal algorithms for regression, low-rank approximation and related numerical problems. The central approach is sketch and solve: compress a large problem into a smaller representation, then apply an algorithm to that reduced problem. These techniques provide fast methods for fundamental machine-learning and numerical-linear-algebra tasks, with running times proportional to the number of nonzero entries in the input.

Randomization offers an alternative approach to large matrix computations arising in scientific data analysis. This talk explains how randomized algorithms approximate matrix multiplication and singular-value decomposition, solve least-squares problems and linear systems, and support data-analysis applications. The accompanying presentation develops matrix sketches through row and column sampling, compares length-squared sampling with leverage-score sampling, and describes their use in low-rank approximation and matrix factorizations. It also explains how leverage scores can be approximated efficiently and how sampling guarantees support least-squares and feature-selection procedures.