Graph Algorithms in the Language of Linear AlgebraJeremy 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. |
Other editions - View all
Common terms and phrases
addition adjacency matrix analysis applied approach approximation array Bader bipartite block centrality chapter cluster column communication complexity components computing connected consider convergence corresponding cost data structure decomposition defined degree distribution denote dependency diameter edges efficient elements entries estimate et al example Figure fitting follows given gives gradient graph algorithms implementation indices initiator instance iteration Journal Kronecker graphs Kronecker product Leskovec likelihood mapping memory method multiplication nodes nonzero Note operations optimization pairs parallel parameters performance permutation plot power law present probability problem Proceedings processors properties random recursive representation represented requires sampling scores selected shortest paths shown shows SIAM similar simple single space sparse matrix step stochastic Table takes tensor tree triples types updates values vector vertex vertices weights