Topic: matrix multiplication

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.

Virginia Vassilevska Williams surveys the search for faster matrix multiplication, from Strassen’s first improvement over cubic time to modern bounds. The talk explains the role of this basic operation in graph algorithms, numerical linear algebra and learning, and the unresolved question of whether its exponent can reach the quadratic output-size lower bound. It offers intuition for the development and possible future direction of the area.

Jeroen Zuiddam examines whether repeated tasks permit economies of scale, focusing on fast matrix multiplication and graph Shannon capacity as unresolved direct-sum problems. The talk introduces Strassen's asymptotic-spectrum duality, originally developed for asymptotic tensor rank and later applied to Shannon capacity and other problems. It then explores approximation by sequences of easier instances: suitable notions of convergence, construction of the sequences, asymptotic-spectrum distance, and approaches using polynomials and algebraic geometry. Based on joint work with David de Boer, Pjo

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 obstacl