# Complexity of Matrix Computations

Complexity of Matrix Computations is a series of online discussions dedicated to bridging the gap between numerical linear algebra and theoretical computer science. Seminars take place on Wednesdays at 9am (PT) = noon (ET) = 6pm (CEST) and are scheduled on a fortnightly basis. Each session will be centered around a discussion prompt with 5-minute blitz talks and a panel of experts.

To join the seminar, please send an email to cmc-l-request@cornell.edu with the subject "join". Information about how to connect to the Zoom conference call will be circulated via email to all registered attendees prior to each seminar.

Organizing committee:

Ilse Ipsen (NCSU), Mike Mahoney (Berkeley), Yuji Nakatsukasa (University of Oxford), Nikhil Srivastava (Berkeley), Alex Townsend (Cornell), and Joel Tropp (Caltech).

## SEMINARS

### May 12 - Matrix inversion

**Speakers: **Peter Bürgisser (TU Berlin),** **Nick Higham (Manchester), Cameron Musco (University of Massachusetts Amherst)

**Panelists:** Jim Demmel (Berkeley), Ilse Ipsen (NC State), Richard Peng (Georgia Tech)

**Discussion prompt:** *What does it mean to solve the equation Ax=b, for an invertible matrix A? What do precision, accuracy, conditioning, and complexity mean in this context?*

### May 26 - Symmetric eigenvalue problems

**Speakers: **Cleve Moler (Mathworks), Yuji Nakatsukasa (University of Oxford), and Santosh Vempala (Georgia Tech)

**Panelists:** Beresford Parlett (Berkeley), Sushant Sachdeva (University of Toronto)

**Discussion prompt:** *What does it mean to compute all the eigenvalues and eigenvectors of a symmetric matrix A?** **When is multiplicity a difficulty?** **How should eigenvector computation be formulated?** **What algorithm would you use?*

### June 9 - Low rank approximation

**Speakers: **Gunnar Martinsson (UT Austin) and David Woodruff (Carnegie Mellon)

**Panelists:** Petros Drineas (Purdue), Laura Grigori (INRIA Paris), and Madeleine Udell (Cornell)

**Discussion prompt: **What does it mean to compute a low rank approximation of a matrix? What is a low rank matrix? What does approximation mean in this context? What is a good algorithm for this problem? How should the running time depend on the approximation parameter?

### June 23 - Nonsymmetric eigenvalue problems

**Speakers: **Mark Embree (Virginia Tech) and Nikhil Srivastava (Berkeley)

**Panelists: **Cleve Moler (Mathworks), Ryan O'Donnell (CMU), and Nick Trefethen (University of Oxford)

**Discussion prompt: ***What does it mean to compute all the eigenvalues and eigenvectors of a diagonalizable matrix A? What does it mean to be diagonalizable? What is a good algorithm for this problem?*

### CMC SUMMER BREAK: July-August

We have decided that the CMC seminar will break for the summer. We will resume on September 1st.

### Sept 1 - Least squares

**Speakers: **Ilse Ipsen (NCSU) and Michael Mahoney (Berkeley)

**Discussion prompt: ***What does it mean to solve a least squares problem? What algorithm would you use? What is its complexity?*

### Sept 15 - Matrix exponential and perhaps other functions of matrices

**Speakers: **Aaron Sidford (Stanford) and Nick Trefethen (University of Oxford)

**Discussion prompt: ***Computing the matrix exponential and perhaps other functions of matrices.*

### Sept 29 - Laplacian solvers

**Speakers: **George Biros (UT Austin) and Rasmus Kyng (ETH Zurich)

**Discussion prompt: ***What does it mean to approximately solve a Laplacian linear system? What is the optimal Laplacian solver, theoretically and practically? What is the scope of applications for Laplacian solvers?*

### Oct 13 - Iterative solvers for linear systems

**Speakers: **Richard Peng (Georgia Institute of Technology) and Zdenek Strakos (Charles University in Prague)

**Discussion prompt: ***What does it mean to solve Ax=b iteratively? On what theoretical and practical criteria do you compare different solvers? What are the best solvers based on these criteria?*

### Oct 27 - Iterative solvers for eigenvalue problems

**Speakers: **Christopher Musco (NYU), Andreas Stathopoulos (William & Mary), Tom Trogdon (UW)

**Discussion prompt: ***What does it mean to solve an eigenvalue problem iteratively? What iterative eigensolver do you recommend? What stopping criterion do you use? *

### Nov 10 - RRQR and column subset selection

**Speakers: **Jim Demmel (Berkeley), Ming Gu (Berkeley) and Michael Mahoney (Berkeley)

**Discussion prompt: ***What does a "rank-revealing algorithm" mean? What rank-revealing algorithm do you recommend? In your applications, do you care about Type I error (column subset selection error) or Type II error (low-rank approximation error)?*

### Nov 24 - Thanksgiving break

### Dec 8 - Matrix-Matrix multiplication

**Speakers: **Josh Alman (Columbia) and Julien Langou (CU Denver)

**Discussion prompt: **What is your favorite algorithm for matrix-matrix multiplication? How do you compare algorithms both practically and theoretically? What makes matrix-matrix multiplication so important?