%0 Book Section %1 buluc11 %A Buluc, Aydin %A Gilbert, John %A Shah, Viral B. %B Graph Algorithms in the Language of Linear Algebra %D 2011 %I SIAM %K algorithm linear.algebra matrix sparse textbook %P 287--313 %R 10.1137/1.9780898719918.ch13 %T Implementing Sparse Matrices for Graph Algorithms %X Sparse matrices are a key data structure for implementing graph algorithms using linear algebra. This chapter reviews and evaluates storage formats for sparse matrices and their impact on primitive operations. We present complexity results of these operations on different sparse storage formats both in the random access memory (RAM) model and in the input/output (I/O) model. RAM complexity results were known except for the analysis of sparse matrix indexing. On the other hand, most of the I/O complexity results presented are new. The chapter focuses on different variations of the triples (coordinates) format and the widely used compressed sparse row (CSR) and compressed sparse column (CSC) formats. For most primitives, we provide detailed pseudocodes for implementing them on triples and CSR/CSC. %& 13 %@ 978-0-89871-990-1

@inbook{buluc11, abstract = {Sparse matrices are a key data structure for implementing graph algorithms using linear algebra. This chapter reviews and evaluates storage formats for sparse matrices and their impact on primitive operations. We present complexity results of these operations on different sparse storage formats both in the random access memory (RAM) model and in the input/output (I/O) model. RAM complexity results were known except for the analysis of sparse matrix indexing. On the other hand, most of the I/O complexity results presented are new. The chapter focuses on different variations of the triples (coordinates) format and the widely used compressed sparse row (CSR) and compressed sparse column (CSC) formats. For most primitives, we provide detailed pseudocodes for implementing them on triples and CSR/CSC.}, added-at = {2013-09-11T17:25:11.000+0200}, author = {Bulu\c{c}, Aydin and Gilbert, John and Shah, Viral B.}, biburl = {https://www.bibsonomy.org/bibtex/278a6acd9744014bf2b9b635e67fcf249/ytyoun}, booktitle = {Graph Algorithms in the Language of Linear Algebra}, chapter = 13, doi = {10.1137/1.9780898719918.ch13}, interhash = {44db250ca67c7a219aeed6aab9e00af9}, intrahash = {78a6acd9744014bf2b9b635e67fcf249}, isbn = {978-0-89871-990-1}, keywords = {algorithm linear.algebra matrix sparse textbook}, pages = {287--313}, publisher = {SIAM}, timestamp = {2016-10-24T11:18:27.000+0200}, title = {Implementing Sparse Matrices for Graph Algorithms}, year = 2011 }