Graph Algorithms in the Language of Linear Algebra

by Kepner, Jeremy; Gilbert, John

• ISBN13: 9780898719901
• ISBN10: 0898719909
• Format: Hardcover
• Copyright: 2011-07-14
• Publisher: SOCIETY FOR INDUSTRIAL & APPLIED MA

Summary

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.

Table of Contents

Preface

Algorithms

Graphs and matrices

Linear algebraic notation and definitions

Connected components and minimum paths

Some graph algorithms in an array-based language

Fundamental graph algorithms

Complex graph algorithms

Multilinear algebra for analyzing data with multiple linkages

Subgraph detection

Data

Kronecker graphs

The Kronecker theory of power law graphs

Visualizing large Kronecker graphs

Computation

Large-scale network analysis

Implementing sparse matrices for graph algorithms

New ideas in sparse matrix-matrix multiplication

Parallel mapping of sparse computations

Fundamental questions in the analysis of large graphs

Index

Table of Contents provided by Publisher. All Rights Reserved.