Complexity of Matrix Computations

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?

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?

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?

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?

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

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?

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

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

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?

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?

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?

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)?

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?