
2011 / xxviii + 357 / Hardcover / ISBN: 9780898719901 / List Price $113.50 / SIAM Member Price $79.45 / Order Code SE22
Keywords: graph algorithms, network analysis, adjacency matrix, sparse matrixes, parallel programming, combinatorial scientific computing
Graphs are among the most important abstract data types in computer science, and the algorithms that operate on them are critical to modern life. Graphs have been shown to be powerful tools for modeling complex problems because of their simplicity and generality. Graph algorithms are one of the pillars of mathematics, informing research in such diverse areas as combinatorial optimization, complexity theory, and topology. Algorithms on graphs are applied in many ways in today's world—from Web rankings to metabolic networks, from finite element meshes to semantic graphs.
The current exponential growth in graph data has forced a shift to parallel computing for executing graph algorithms. Implementing parallel graph algorithms and achieving good parallel performance have proven difficult. This book addresses these challenges by exploiting the wellknown 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.
Graph Algorithms in the Language of Linear Algebra is the first book to cover
This book is suitable as the primary text for a class on linear algebraic graph algorithms and as either the primary or supplemental text for a class on graph algorithms for engineers and scientists without training in computer science.
Audience
This book will provide an excellent introduction to many classic graph algorithms for professional scientists and engineers with a background in linear algebra but not computer science. This book is suitable as the primary text for a class on linear algebraic graph algorithms and as either the primary or supplemental text for a class on graph algorithms for engineers and scientists without training in computer science.
About the Authors
Jeremy Kepner is a senior technical staff member at MIT Lincoln Laboratory. His research, on which he has published many articles (and the SIAM book Parallel Matlab for Multicore and Multinode Computers), focuses on the development of advanced libraries for the application of massively parallel computing to a variety of data intensive signal processing problems. Kepner is most proud of being the principal architect, principal investigator, or otherwise coleader of several very talented teams that have produced a number of innovative technologies that have broken new ground in parallel computing.
John Gilbert is a SIAM Fellow and Professor of Computer Science at the University of California at Santa Barbara. His research interests are combinatorial scientific computing, highperformance graph algorithms, sparse matrix methods, tools and software for computational science and engineering, and numerical linear algebra.
ISBN: 9780898719901