Sparse exact linear algebra faster than matrix multiplication

Speaker: Prof. Mark Giesbrecht，David R. Cheriton School of Computer Science, University of Waterloo 

Title: Sparse exact linear algebra faster than matrix multiplication

Language: English 

Time & Venue: 2026.10.22   14:00-15:00   南楼N219

Abstract: Sparse matrices arise throughout computational algebra, number theory and topology, and their efficient treatment has a long history in numerical computation. Their sparsity makes matrix-vector products inexpensive, but this advantage is easily lost when intermediate matrices become dense.  I will discuss a line of research over the past two decades on solving exact linear algebra problems at a cost provably below that of dense matrix multiplication.

Beginning with joint work with Eberly, Giorgi, Storjohann and Villard in 2006--2007, I will show how to compute the entire inverse of a sparse matrix faster than matrix multiplication, even though the inverse is generally dense. For an $n \times n$ matrix over a field with nearly linear-time matrix-vector products, the expected

cost is $\softO(n^{3-1/(\omega-1)})$ field operations, where $O(n^\omega)$ is the cost of matrix multiplication.  For the best current $\omega\approx 2.37$, this gives an algorithm for inverse which requires only $\softO(n^{2.27})$ operations; recent developments in matrix multiplication would imply further improvements.

I will then discuss recent work on Smith forms modulo prime powers $p^e$. These diagonal forms record divisibility information beyond rank and arise naturally in homology computations. I will conclude with prospects for computing transformation matrices and Smith forms of sparse matrix pencils, which arise naturally in electrical circuit models and control theory.