Linear Algebra seminars

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.

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.

Spectral methods for high-dimensional nearest-neighbor search can perform well in practice even when random projections appear preferable under worst-case theory. This talk studies that difference in a semi-random model: points lie in an unknown low-dimensional subspace and are then perturbed by Gaussian noise in the full ambient space. The algorithms repeatedly compute a leading principal component or subspace and achieve query times polynomial in the ambient dimension and logarithm of the number of points over substantial parameter ranges. They can remain effective when noise is much larger than the distances among the original points. The work is joint with Amirali Abdullah, Ravi Kannan and Robi Krauthgamer.

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.