John R. Gilbert (Computer Science, UCSB)

Event Date: 

Wednesday, November 30, 2016 - 3:30pm to 5:00pm

Event Date Details: 

Refreshments served at 3:15pm.

Event Location: 

  • Sobel Seminar Room; South Hall 5607F
  • Department Seminar Series

Abstract: The mathematical connections between graph theory and linear algebra are intimate and well known. The computational links between the two fields are also deep, extending from basic data structures to fundamental decompositions to the design of efficient algorithms. During the first 50 years of this computational relationship, graphs served numerical linear algebra by enabling efficient sparse matrix computation. Recently, matrix computation has been returning the favor. 

I will talk about the past and present of this relationship in both directions, and speculate a bit on its future. Along the way, I will describe two software systems we have built for computing with large graphs and networks on parallel computers, CombBLAS and the Knowledge Discovery Toolbox. The key to their performance and scaling is sparse matrix computation. Finally, I will advertise the Graph BLAS Forum, an open effort to standardize primitives for graph computation, building on many groups' work on graph algorithms in the language of linear algebra.