Graph Algorithms in the Language of Linear Algebra

by Jeremy Kepner, John Gilbert

The field of graph algorithms has become one of the pillars of theoretical computer science, informing research in such diverse areas as combinatorial optimization, complexity theory and topology. To improve the computational performance of graph algorithms, researchers have proposed a shift to a parallel computing paradigm. This book addresses the challenges of implementing parallel graph algorithms by exploiting the well-known duality between a canonical representation of graphs as abstract collections of vertices and edges and a sparse adjacency matrix representation. This linear algebraic approach is widely accessible to scientists and engineers who may not be formally trained in computer science. The authors show how to leverage existing parallel matrix computation techniques and the large amount of software infrastructure that exists for these computations to implement efficient and scalable parallel graph algorithms. The benefits of this approach are reduced algorithmic complexity, ease of implementation and improved performance.

Genres: Computer Science, Mathematics

375 pages, Hardcover

First published January 1, 2011

About the author

Jeremy Kepner is an MIT Lincoln Laboratory Fellow, Founder and Head of the MIT Lincoln Laboratory Supercomputing Center, and Research Affiliate in MIT's Mathematics Department.

Reviews

[Michiel · Rating 4 out of 5]

Very interesting reference on dealing with graphs using tools from linear algebra.

[Paul · Rating 5 out of 5]

Beautiful book about how to use the arsenal of linear Algebra and matrices to explore graphs. A must read for anyone who is interested in advanced analytics. These and similar algorithms will be used to analyze social networks, interest networks and risk (credit risk, intruder detection, etc) and much more.