Julia Interface to Matrix-Vector Multiplications in CSB Format

| Documentation | Build Status | Contributing | Extras | |:-------------------------------------------------------------------------------:|:-----------------------------------------------------------------------------------------------:|:-----:|:------:| | | | | |

We provide a Julia interface (a wrapper) to the Compressed Sparse Blocks (CSB) library. The library is written in C/C++, available at https://people.eecs.berkeley.edu/~aydin/csb/html/index.html. The library supports fast computation of large sparse matrix-vector products, $Ax$ and $A^{\rm T}x$ operations specifically, with sparse matrix $A$ in the format of compressed sparse blocks (CSB), on shared-memory computer systems. The CSB format was introduced by A. Buluç, J. Fineman, M. Frigo, J. Gilbert, and C. Leiserson [1].

The CSB format and library have the following advantages: (1) The matrix-vector operations in CSB format often outpace the conventional general-purposes sparse formats, namely, CSC and CSR [2]. (2) The multiplication with the transposed matrix $A^{\rm T}$ does not suffer from longer latency than that with $A$. The symmetric performance eliminates the need for an additional copy in a different layout for $A^{\rm T}$ (as with CSR or CSC) for reducing the speed gap at the cost of double memory consumption. (3) The library is integrated with Cilk [3]. The latter offers optimal run-time scheduling (in theory and in practice) on parallel computers with shared memory.

This Julia interface is intended to extend and ease the use of CSB to broader applications. This interface supports up to $32$ multiple vectors to be applied with the same matrix $A$.

<figure> <img src="https://github.com/fcdimitr/CompressedSparseBlocks.jl/blob/main/benchmarks/benchmark-results.png" alt="Benchmarks" style="width:100%"> <figcaption align = "center"><i>Fig.1 - Comparison in wall-clock execution time between CSB (direct and transpose) and MKLSparse (CSC transpose only). The parallel execution times are with 4 threads on an Intel Core i5-4288U @2.6GHz CPU. The average degree is the average number of nonzeros per row/column.</i></figcaption> </figure>

Installation

The package can be added using the Julia package manager. From the Julia REPL, type ] to enter the Pkg REPL mode and execute the following command

pkg> add CompressedSparseBlocks

:warning: CompressedSparseBlocks is currently not working on Windows and native M1 Macs: Either use WSL2 on Windows or use the package via Rosetta 2 on the M-processor Macs (that means by using the x86 and not the arm64 julia).

Documentation

• STABLE — most recently tagged version of the documentation.
• LATEST — in-development version of the documentation.

Contributing and Questions

Contributions are very welcome, as are feature requests and suggestions. Please open an issue if you encounter any problems.

References

[1] A. Buluç, J. T. Fineman, M. Frigo, J. R. Gilbert, and C. E. Leiserson, “Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks,” in Proceedings of the 21st Annual Symposium on Parallelism in Algorithms and Architectures, 2009, pp. 233–244. doi: 10.1145/1583991.1584053.

[2] S. C. Eisenstat, M. C. Gursky, M. H. Schultz, A. H. Sherman, “Yale Sparse Matrix Package,” Technical Report, 1977.

[3] M. Frigo, C. E. Leiserson, and K. H. Randall, “The implementation of the Cilk-5 multithreaded language,” ACM SIGPLAN Notices, vol. 33, no. 5, pp. 212–223, 1998, doi: 10.1145/277652.277725.

Contributors of the Julia interface

Design and development:
Dimitris Floros¹, Nikos Pitsianis^1,2, Xiaobai Sun²

¹ Department of Electrical and Computer Engineering, Aristotle University of Thessaloniki, Thessaloniki 54124, Greece
² Department of Computer Science, Duke University, Durham, NC 27708, USA