Graph Algorithms in the Language of Linear Algebra (Software, Environments, and Tools)

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 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. Graph Algorithms in the Language of Linear Algebra is the first book to cover graph algorithms accessible to engineers and scientists not trained in computer science but having a strong linear algebra background, enabling them to quickly understand and apply graph algorithms. It also covers array-based graph algorithms, showing readers how to express canonical graph algorithms using a highly elegant and efficient array notation and how to tap into the large range of tools and techniques that have been built for matrices and tensors; parallel array-based algorithms, demonstrating with examples how to easily implement parallel graph algorithms using array-based approaches, which enables readers to address much larger graph problems; and array-based theory for analyzing graphs, providing a template for using array-based constructs to develop new theoretical approaches for graph analysis. Audience: 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. Contents: List of Figures; List of Tables; List of Algorithms; Preface; Acknowledgments; Part I: Algorithms: Chapter 1: Graphs and Matrices; Chapter 2: Linear Algebraic Notation and Definitions; Chapter 3: Connected Components and Minimum Paths; Chapter 4: Some Graph Algorithms in an Array-Based Language; Chapter 5: Fundamental Graph Algorithms; Chapter 6: Complex Graph Algorithms; Chapter 7: Multilinear Algebra for Analyzing Data with Multiple Linkages; Chapter 8: Subgraph Detection; Part II: Data: Chapter 9: Kronecker Graphs; Chapter 10: The Kronecker Theory of Power Law Graphs; Chapter 11: Visualizing Large Kronecker Graphs; Part III: Computation: Chapter 12: Large-Scale Network Analysis; Chapter 13: Implementing Sparse Matrices for Graph Algorithms; Chapter 14: New Ideas in Sparse Matrix-Matrix Multiplication; Chapter 15: Parallel Mapping of Sparse Computations; Chapter 16: Fundamental Questions in the Analysis of Large Graphs; Index. Cover 1 S Title 2 Editorial Board 3 Title: Graph Algorithms in theLanguage of Linear Algebra 4 Copyright 5 2011 by the Society for Industrial and Applied Mathematics 5 ISBN 978-0-898719-90-1 5 Dedication 6 List of Contributors 7 Contents 8 List of Figures 16 List of Tables 20 List of Algorithms 21 Preface 23 Acknowledgments 25 Chapter 1: Graphs and Matrices 26 1.1 Motivation 26 1.2 Algorithms 27 1.2.1 Graph adjacency matrix duality 27 1.2.2 Graph algorithms as semirings 28 1.2.3 Tensors 29 1.3 Data 29 1.3.1 Simulating power law graphs 29 1.3.2 Kronecker theory 30 1.4 Computation 30 1.4.1 Graph analysis metrics 30 1.4.2 Sparse matrix storage 31 1.4.3 Sparse matrix multiply 32 1.4.4 Parallel programming 32 1.4.5 Parallel matrix multiply performance 33 1.5 Summary 35 References 35 Chapter 2: Linear Algebraic Notation and Definitions 36 2.1 Graph notation 36 2.2 Array notation 37 2.3 Algebraic notation 37 2.3.1 Semirings and related structures 37 2.3.2 Scalar operations 38 2.3.3 Vector operations 38 2.3.4 Matrix operations 39 2.4 Array storage and decomposition 39 2.4.1 Sparse 39 2.4.2 Parallel 40 Block distribution 40 Cyclic distribution 40 Chapter 3: Connected Components and Minimum Paths 42 Abstract 42 3.1 Introduction 42 3.2 Strongly connected components 43 3.2.1 Nondirected links 44 3.2.2 Computing C quickly 45 3.3 Dynamic programming, minimum paths, and matrix exponentiation 46 3.3.1 Matrix powers 48 3.4 Summary 49 References 50 Chapter 4: Some Graph Algorithms in an Array-Based Language 51 Abstract 51 4.1 Motivation 51 4.2 Sparse matrices and graphs 52 4.2.1 Sparse matrix multiplication 53 4.3 Graph algorithms 54 4.3.1 Breadth-first search 54 4.3.2 Strongly connected components 55 4.3.3 Connected components 56 4.3.4 Maximal independent set 57 4.3.5 Graph contraction 57 4.3.6 Graph partitioning 59 4.4 Graph generators 61 4.4.1 Uniform random graphs 61 4.4.2 Power law graphs 61 4.4.3 Regular geometric grids 61 References 63 Chapter 5: Fundamental Graph Algorithms 66 Abstract 66 5.1 Shortest paths 66 5.1.1 Bellman–Ford 67 Algebraic Bellman–Ford 68 5.1.2 Computing the shortest path tree (for Bellman–Ford) 69 Parent pointers are on smallest size paths 70 Computing parent pointers with 3-tuples 70 Computing parent pointers at the end 73 5.1.3 Floyd–Warshall 74 Algebraic Floyd–Warshall 75 5.2 Minimum spanning tree 76 5.2.1 Prim’s 76 Algebraic Prim’s 78 Computing the tree 78 References 79 Chapter 6: Complex Graph Algorithms 80 Abstract 80 6.1 Graph clustering 80 6.1.1 Peer pressure clustering 80 Starting approximation 83 Assuring vertices have equal votes 83 Preserving small clusters and unclustered vertices 83 Settling ties 84 Sample calculation 84 Space complexity 85 Time complexity 85 6.1.2 Matrix formulation 87 Starting approximation 87 Assuring vertices have equal votes 87 Preserving small clusters and unclustered vertices 88 Settling ties 88 Space complexity 88 Time complexity 88 6.1.3 Other approaches 88 Comparison to Markov clustering 89 6.2 Vertex betweenness centrality 89 6.2.1 History 89 6.2.2 Brandes’ algorithm 90 Traditional algorithm 90 Sample calculation 90 Linear algebraic formulation 94 Time complexity 95 Space complexity 96 6.2.3 Batch algorithm 96 Linear algebraic formulation 97 Time complexity 97 Space complexity 97 6.2.4 Algorithm for weighted graphs 99 6.3 Edge betweenness centrality 99 6.3.1 Brandes’ algorithm 99 Vertex/edge set formulation 99 Sample calculation 99 Adjacency matrix formulation 102 Time complexity 102 Space complexity 104 6.3.2 Block algorithm 104 6.3.3 Algorithm for weighted graphs 105 References 105 Chapter 7: Multilinear Algebra for Analyzing Data with Multiple Linkages 106 Abstract 106 7.1 Introduction 107 7.2 Tensors and the CANDECOMP/PARAFAC decomposition 108 7.2.1 Notation 108 7.2.2 Vector and matrix preliminaries 109 7.2.3 Tensor preliminaries 109 7.2.4 The CP tensor decomposition 110 7.2.5 CP-ALS algorithm 110 7.3 Data 112 7.3.1 Data as a tensor 112 7.3.2 Quantitative measurements on the data 114 7.4 Numerical results 114 7.4.1 Community identification 115 7.4.2 Latent document similarity 116 7.4.3 Analyzing a body of work via centroids 118 7.4.4 Author disambiguation 119 7.4.5 Journal prediction via ensembles of tree classifiers 124 7.5 Related wor 127 7.5.1 Analysis of publication data 127 7.5.2 Higher order analysis in data mining 128 7.5.3 Other related work 129 7.6 Conclusions and future work 129 7.7 Acknowledgments 131 References 131 Chapter 8: Subgraph Detection 136 Abstract 136 8.1 Graph model 136 8.1.1 Vertex/edge schema 137 8.2 Foreground: Hidden Markov model 139 8.2.1 Path moments 139 Special cases 140 Expected paths 140 8.3 Background model: Kronecker graphs 141 8.4 Example: Tree finding 141 8.4.1 Background: Power law 141 8.4.2 Foreground: Tree 142 8.4.3 Detection problem 142 8.4.4 Degree distribution 144 8.5 SNR, PD, and PFA 145 8.5.1 First and second neighbors 146 8.5.2 Second neighbors 146 8.5.3 First neighbors 147 8.5.4 First neighbor leaves 147 8.5.5 First neighbor branches 148 8.5.6 SNR hierarchy 149 8.6 Linear filter 150 8.6.1 Find nearest neighbors 150 8.6.2 Eliminate high degree nodes 150 8.6.3 Eliminate occupied nodes 151 8.6.4 Find high probability nodes 151 8.6.5 Find high degree nodes 152 8.7 Results and conclusions 153 References 154 Chapter 9: Kronecker Graphs 155 Abstract 155 9.1 Introduction 156 9.2 Relation to previous work on network modeling 158 9.2.1 Graph patterns 158 9.2.2 Generative models of network structure 160 9.2.3 Parameter estimation of network models 160 9.3 Kronecker graph model 161 9.3.1 Main idea 161 9.3.2 Analysis of Kronecker graphs 165 Degree distribution 165 Spectral properties 166 Connectivity of Kronecker graphs 167 Temporal properties of Kronecker graphs 168 9.3.3 Stochastic Kronecker graphs 170 Probability of an edge 172 9.3.4 Additional properties of Kronecker graphs 172 9.3.5 Two interpretations of Kronecker graphs 173 9.3.6 Fast generation of stochastic Kronecker graphs 175 9.3.7 Observations and connections 176 9.4 Simulations of Kronecker graphs 177 9.4.1 Comparison to real graphs 177 9.4.2 Parameter space of Kronecker graphs 179 9.5 Kronecker graph model estimation 181 9.5.1 Preliminaries 183 9.5.2 Problem formulation 184 9.5.3 Summing over the node labelings 187 Sampling permutations 187 Speeding up the likelihood ratio calculation 189 9.5.4 Efficiently approximating likelihood and gradient 190 9.5.5 Calculating the gradient 191 9.5.6 Determining the size of an initiator matrix 191 9.6 Experiments on real and synthetic data 192 9.6.1 Permutation sampling 192 Convergence of the log-likelihood and the gradient 192 Different proposal distributions 194 Properties of the permutation space 196 9.6.2 Properties of the optimization space 198 9.6.3 Convergence of the graph properties 199 9.6.4 Fitting to real-world networks 199 Fitting to autonomous systems network 200 Choice of the initiator matrix size N 202 Network parameters over time 204 9.6.5 Fitting to other large real-world networks 205 9.6.6 Scalability 208 9.7 Discussion 211 9.8 Conclusion 213 Appendix: Table of networks 214 References 215 Chapter 10: The Kronecker Theory of Power Law Graphs 223 Abstract 223 10.1 Introduction 223 10.2 Overview of results 224 10.3 Kronecker graph generation algorithm 226 10.3.1 Explicit adjacency matrix 226 10.3.2 Stochastic adjacency matrix 227 10.3.3 Instance adjacency matrix 229 10.4 A simple bipartite model of Kronecker graphs 229 10.4.1 Bipartite product 230 10.4.2 Bipartite Kronecker exponents 231 10.4.3 Degree distribution 233 10.4.4 Betweenness centrality 234 10.4.5 Graph diameter and eigenvalues 236 10.4.6 Iso-parametric ratio 237 10.5 Kronecker products and useful permutations 238 10.5.1 Sparsity 238 10.5.2 Permutations 238 10.5.3 Pop permutation 239 10.5.4 Bipartite permutation 239 10.5.5 Recursive bipartite permutation 239 10.5.6 Bipartite index tree 242 10.6 A more general model of Kronecker graphs 243 10.6.1 Sparsity analysis 244 10.6.2 Second order terms 245 10.6.3 Higher order terms 248 10.6.4 Degree distribution 249 10.6.5 Graph diameter and eigenvalues 249 10.6.6 Iso-parametric ratio 251 10.7 Implications of bipartite substructure 252 10.7.1 Relation between explicit and instance graphs 252 10.7.2 Clustering power law graphs 255 10.7.3 Dendragram and power law graphs 256 10.8 Conclusions and future work 256 10.9 Acknowledgments 257 References 257 Chapter 11: Visualizing Large Kronecker Graphs 259 Abstract 259 11.1 Introduction 259 11.2 Kronecker graph model 260 11.3 Kronecker graph generator 261 11.4 Analyzing Kronecker graphs 261 11.4.1 Graph metrics 261 11.4.2 Graph view 263 11.4.3 Organic growth simulation 263 11.5 Visualizing Kronecker graphs in 3D 264 11.5.1 Embedding Kronecker graphs onto a sphere surface 265 11.5.2 Visualizing Kronecker graphs on parallel system 265 References 268 Chapter 12: Large-Scale Network Analysis 269 Abstract 269 12.1 Introduction 270 12.2 Centrality metrics 271 Preliminaries 272 Degree centrality 272 Closeness centrality 272 Betweenness centrality 273 Algorithms for computing betweenness centrality 274 12.3 Parallel centrality algorithms 274 Degree centrality 275 Closeness centrality 275 Stress and betweenness centrality 276 12.3.1 Optimizations for real-world graphs 278 12.4 Performance results and analysis 280 12.4.1 Experimental setup 280 Network data 281 12.4.2 Performance results 282 12.5 Case study: Betweenness applied to protein-interaction networks 284 12.6 Integer torus: Betweenness conjecture 288 12.6.1 Proof of conjecture when n is odd 290 12.6.2 Proof of conjecture when n is even 292 Acknowledgments 296 References 296 Chapter 13: Implementing Sparse Matrices for Graph Algorithms 302 Abstract 302 13.1 Introduction 302 13.2 Key primitives 306 13.3 Triples 308 13.3.1 Unordered triples 309 13.3.2 Row ordered triples 313 Indexing and SpMV with row ordered triples 313 The sparse accumulator 314 SpAdd and SpGEMM with row ordered triples 315 13.3.3 Row-major ordered triples 317 13.4 Compressed sparse row/column 320 13.4.1 CSR and adjacency lists 320 13.4.2 CSR on key primitives 321 13.5 Case study: Star-P 323 13.5.1 Sparse matrices in Star-P 323 Sparse matrix-dense vector multiplication (SpMV) 324 13.6 Conclusions 325 References 325 Chapter 14: New Ideas in Sparse Matrix Matrix Multiplication 329 Abstract 329 14.1 Introduction 329 14.2 Sequential sparse matrix multiply 331 14.2.1 Layered graphs for different formulations of SpGEMM 332 14.2.2 Hypersparse matrices 334 14.2.3 DCSC data structure 335 14.2.4 A sequential algorithm to multiply hypersparse matrices 336 14.3 Parallel algorithms for sparse GEMM 340 14.3.1 1D decomposition 340 14.3.2 2D decomposition 340 14.3.3 Sparse 1D algorithm 341 14.3.4 Sparse Cannon 341 14.3.5 Sparse SUMMA 342 14.4 Analysis of parallel algorithms 342 14.4.1 Scalability of the 1D algorithm 343 14.4.2 Scalability of the 2D algorithms 344 14.5 Performance modeling of parallel algorithms 345 References 348 Chapter 15: Parallel Mapping of Sparse Computations 352 Abstract 352 15.1 Introduction 352 15.2 Lincoln Laboratory mapping and optimization environment 353 15.2.1 LLMOE overview 354 15.2.2 Mapping in LLMOE 356 Co-optimization of mapping and routing 357 Outer GA 358 Inner GA 359 Search space 359 Parallelization of the nested GA 360 15.2.3 Mapping performance results 360 Machine model 360 Matrix multiplication algorithm 362 Sparsity patterns 362 Benchmarks 363 Results 363 Conclusion 365 References 365 Chapter 16: Fundamental Questions in the Analysis of Large Graphs 366 Abstract 366 16.1 Ontology, schema, data model 367 16.2 Time evolution 367 16.3 Detection theory 368 16.4 Algorithm scaling 368 16.5 Computer architecture 369 Index 371 Cover......Page 1 S Title......Page 2 Editorial Board......Page 3 Title: Graph Algorithms in theLanguage of Linear Algebra......Page 4 ISBN 978-0-898719-90-1......Page 5 Dedication......Page 6 List of Contributors......Page 7 Contents......Page 8 List of Figures......Page 16 List of Tables......Page 20 List of Algorithms......Page 21 Preface......Page 23 Acknowledgments......Page 25 1.1 Motivation......Page 26 1.2.1 Graph adjacency matrix duality......Page 27 1.2.2 Graph algorithms as semirings......Page 28 1.3.1 Simulating power law graphs......Page 29 1.4.1 Graph analysis metrics......Page 30 1.4.2 Sparse matrix storage......Page 31 1.4.4 Parallel programming......Page 32 1.4.5 Parallel matrix multiply performance......Page 33 References......Page 35 2.1 Graph notation......Page 36 2.3.1 Semirings and related structures......Page 37 2.3.3 Vector operations......Page 38 2.4.1 Sparse......Page 39 Cyclic distribution......Page 40 3.1 Introduction......Page 42 3.2 Strongly connected components......Page 43 3.2.1 Nondirected links......Page 44 3.2.2 Computing C quickly......Page 45 3.3 Dynamic programming, minimum paths, and matrix exponentiation......Page 46 3.3.1 Matrix powers......Page 48 3.4 Summary......Page 49 References......Page 50 4.1 Motivation......Page 51 4.2 Sparse matrices and graphs......Page 52 4.2.1 Sparse matrix multiplication......Page 53 4.3.1 Breadth-first search......Page 54 4.3.2 Strongly connected components......Page 55 4.3.3 Connected components......Page 56 4.3.5 Graph contraction......Page 57 4.3.6 Graph partitioning......Page 59 4.4.3 Regular geometric grids......Page 61 References......Page 63 5.1 Shortest paths......Page 66 5.1.1 Bellman–Ford......Page 67 Algebraic Bellman–Ford......Page 68 5.1.2 Computing the shortest path tree (for Bellman–Ford)......Page 69 Computing parent pointers with 3-tuples......Page 70 Computing parent pointers at the end......Page 73 5.1.3 Floyd–Warshall......Page 74 Algebraic Floyd–Warshall......Page 75 5.2.1 Prim’s......Page 76 Computing the tree......Page 78 References......Page 79 6.1.1 Peer pressure clustering......Page 80 Preserving small clusters and unclustered vertices......Page 83 Sample calculation......Page 84 Time complexity......Page 85 Assuring vertices have equal votes......Page 87 6.1.3 Other approaches......Page 88 6.2.1 History......Page 89 Sample calculation......Page 90 Linear algebraic formulation......Page 94 Time complexity......Page 95 6.2.3 Batch algorithm......Page 96 Space complexity......Page 97 Sample calculation......Page 99 Time complexity......Page 102 6.3.2 Block algorithm......Page 104 References......Page 105 Abstract......Page 106 7.1 Introduction......Page 107 7.2.1 Notation......Page 108 7.2.3 Tensor preliminaries......Page 109 7.2.5 CP-ALS algorithm......Page 110 7.3.1 Data as a tensor......Page 112 7.4 Numerical results......Page 114 7.4.1 Community identification......Page 115 7.4.2 Latent document similarity......Page 116 7.4.3 Analyzing a body of work via centroids......Page 118 7.4.4 Author disambiguation......Page 119 7.4.5 Journal prediction via ensembles of tree classifiers......Page 124 7.5.1 Analysis of publication data......Page 127 7.5.2 Higher order analysis in data mining......Page 128 7.6 Conclusions and future work......Page 129 References......Page 131 8.1 Graph model......Page 136 8.1.1 Vertex/edge schema......Page 137 8.2.1 Path moments......Page 139 Expected paths......Page 140 8.4.1 Background: Power law......Page 141 8.4.3 Detection problem......Page 142 8.4.4 Degree distribution......Page 144 8.5 SNR, PD, and PFA......Page 145 8.5.2 Second neighbors......Page 146 8.5.4 First neighbor leaves......Page 147 8.5.5 First neighbor branches......Page 148 8.5.6 SNR hierarchy......Page 149 8.6.2 Eliminate high degree nodes......Page 150 8.6.4 Find high probability nodes......Page 151 8.6.5 Find high degree nodes......Page 152 8.7 Results and conclusions......Page 153 References......Page 154 Abstract......Page 155 9.1 Introduction......Page 156 9.2.1 Graph patterns......Page 158 9.2.3 Parameter estimation of network models......Page 160 9.3.1 Main idea......Page 161 Degree distribution......Page 165 Spectral properties......Page 166 Connectivity of Kronecker graphs......Page 167 Temporal properties of Kronecker graphs......Page 168 9.3.3 Stochastic Kronecker graphs......Page 170 9.3.4 Additional properties of Kronecker graphs......Page 172 9.3.5 Two interpretations of Kronecker graphs......Page 173 9.3.6 Fast generation of stochastic Kronecker graphs......Page 175 9.3.7 Observations and connections......Page 176 9.4.1 Comparison to real graphs......Page 177 9.4.2 Parameter space of Kronecker graphs......Page 179 9.5 Kronecker graph model estimation......Page 181 9.5.1 Preliminaries......Page 183 9.5.2 Problem formulation......Page 184 Sampling permutations......Page 187 Speeding up the likelihood ratio calculation......Page 189 9.5.4 Efficiently approximating likelihood and gradient......Page 190 9.5.6 Determining the size of an initiator matrix......Page 191 Convergence of the log-likelihood and the gradient......Page 192 Different proposal distributions......Page 194 Properties of the permutation space......Page 196 9.6.2 Properties of the optimization space......Page 198 9.6.4 Fitting to real-world networks......Page 199 Fitting to autonomous systems network......Page 200 Choice of the initiator matrix size N......Page 202 Network parameters over time......Page 204 9.6.5 Fitting to other large real-world networks......Page 205 9.6.6 Scalability......Page 208 9.7 Discussion......Page 211 9.8 Conclusion......Page 213 Appendix: Table of networks......Page 214 References......Page 215 10.1 Introduction......Page 223 10.2 Overview of results......Page 224 10.3.1 Explicit adjacency matrix......Page 226 10.3.2 Stochastic adjacency matrix......Page 227 10.4 A simple bipartite model of Kronecker graphs......Page 229 10.4.1 Bipartite product......Page 230 10.4.2 Bipartite Kronecker exponents......Page 231 10.4.3 Degree distribution......Page 233 10.4.4 Betweenness centrality......Page 234 10.4.5 Graph diameter and eigenvalues......Page 236 10.4.6 Iso-parametric ratio......Page 237 10.5.2 Permutations......Page 238 10.5.5 Recursive bipartite permutation......Page 239 10.5.6 Bipartite index tree......Page 242 10.6 A more general model of Kronecker graphs......Page 243 10.6.1 Sparsity analysis......Page 244 10.6.2 Second order terms......Page 245 10.6.3 Higher order terms......Page 248 10.6.5 Graph diameter and eigenvalues......Page 249 10.6.6 Iso-parametric ratio......Page 251 10.7.1 Relation between explicit and instance graphs......Page 252 10.7.2 Clustering power law graphs......Page 255 10.8 Conclusions and future work......Page 256 References......Page 257 11.1 Introduction......Page 259 11.2 Kronecker graph model......Page 260 11.4.1 Graph metrics......Page 261 11.4.3 Organic growth simulation......Page 263 11.5 Visualizing Kronecker graphs in 3D......Page 264 11.5.2 Visualizing Kronecker graphs on parallel system......Page 265 References......Page 268 Abstract......Page 269 12.1 Introduction......Page 270 12.2 Centrality metrics......Page 271 Closeness centrality......Page 272 Betweenness centrality......Page 273 12.3 Parallel centrality algorithms......Page 274 Closeness centrality......Page 275 Stress and betweenness centrality......Page 276 12.3.1 Optimizations for real-world graphs......Page 278 12.4.1 Experimental setup......Page 280 Network data......Page 281 12.4.2 Performance results......Page 282 12.5 Case study: Betweenness applied to protein-interaction networks......Page 284 12.6 Integer torus: Betweenness conjecture......Page 288 12.6.1 Proof of conjecture when n is odd......Page 290 12.6.2 Proof of conjecture when n is even......Page 292 References......Page 296 13.1 Introduction......Page 302 13.2 Key primitives......Page 306 13.3 Triples......Page 308 13.3.1 Unordered triples......Page 309 Indexing and SpMV with row ordered triples......Page 313 The sparse accumulator......Page 314 SpAdd and SpGEMM with row ordered triples......Page 315 13.3.3 Row-major ordered triples......Page 317 13.4.1 CSR and adjacency lists......Page 320 13.4.2 CSR on key primitives......Page 321 13.5.1 Sparse matrices in Star-P......Page 323 Sparse matrix-dense vector multiplication (SpMV)......Page 324 References......Page 325 14.1 Introduction......Page 329 14.2 Sequential sparse matrix multiply......Page 331 14.2.1 Layered graphs for different formulations of SpGEMM......Page 332 14.2.2 Hypersparse matrices......Page 334 14.2.3 DCSC data structure......Page 335 14.2.4 A sequential algorithm to multiply hypersparse matrices......Page 336 14.3.2 2D decomposition......Page 340 14.3.4 Sparse Cannon......Page 341 14.4 Analysis of parallel algorithms......Page 342 14.4.1 Scalability of the 1D algorithm......Page 343 14.4.2 Scalability of the 2D algorithms......Page 344 14.5 Performance modeling of parallel algorithms......Page 345 References......Page 348 15.1 Introduction......Page 352 15.2 Lincoln Laboratory mapping and optimization environment......Page 353 15.2.1 LLMOE overview......Page 354 15.2.2 Mapping in LLMOE......Page 356 Co-optimization of mapping and routing......Page 357 Outer GA......Page 358 Search space......Page 359 Machine model......Page 360 Sparsity patterns......Page 362 Results......Page 363 References......Page 365 Abstract......Page 366 16.2 Time evolution......Page 367 16.4 Algorithm scaling......Page 368 16.5 Computer architecture......Page 369 Index......Page 371 Publisher description: 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