Sparsity: Practice-to-Theory-to-Practice

Join us for ASE-60, where we celebrate the life and the career of Professor Alan Stuart Edelman, on the occasion of his 60th birthday: https://math.mit.edu/events/ase60celebration/

As we all know, the entire world of computation is mostly matrix multiplies. Within this universe we do allow some variation. Specifically, all the world is mostly either dense matrix multiplies or sparse matrix multiplies. Sparse matrices are often used as a trick to solve larger problems by only storing non-zero values. As a result, there is large toolkit of powerful sparse matrix software. The availability of sparse matrix tools inspires representing a wide range of problems as sparse matrices. Notably graphs have many wonderful sparse matrix properties and many graph algorithms can be written as matrix multiplies using a variety of semirings. This inspires developing new sparse matrix software that encompasses a wide range of semiring operations. In the context of graphs, where vertex labels are diverse, it is natural to relax strict dimension constraints and make hyper-sparse matrices a full-fledged member of the sparse matrix software world. The wide availability of hyper-sparse matrices allows addressing a wide range of problems and completely new approaches to parallel computing.