Stop Thinking, Just Do!

Sung-Soo Kim's Blog

Mathematical Foundations of the GraphBLAS and Big Data


3 April 2021

Article Source

Mathematical Foundations of the GraphBLAS and Big Data


  • Jeremy Kepner, Massachusetts Institute of Technology, U.S.
  • Hayden Jananthan, Vanderbilt University, U.S.


Large-scale computations on networks and graphs arise in many areas of modern data science. Graph theory and linear algebra are of course intimately linked. This minisymposium will highlight tools from sparse matrix computation that are being used to develop efficient implementations of graph algorithms. Such tools range from linear algebra over semirings to fast solvers for Laplacian linear systems.

In the former area, matrices over various semirings describe the kernels of a wide variety of graph algorithms in theory, and efficient software for sparse semiring algebra has led to practical, scalable implementations with significant impact. In the latter area, the so-called Laplacian paradigm has lately challenged or replaced the asymptotically best algorithms known for such classic network problems as multicommodity flow, and we anticipate that fast Laplacian solvers will become a standard building block for graph and network software.

The minisymposium will open with two talks on sparse semirings for graph computation, the first on theory and the second on efficient implementation and software. The last two talks will highlight current work in graph Laplacians and their applications, and describe a number of applications of the linear algebraic approach to graph computation.

This minisymposium is organized under the auspices of the SIAM Activity Group on Applied and Computational Discrete Algorithms.

comments powered by Disqus