CompressedSparseBlocks

Documentation for CompressedSparseBlocks.

Why and when should I use CompressedSparseBlocks?

If you have a computation with an iteration where the time is dominated by a large sparse matrix multiplication, 

julia> using LinearAlgebra, SparseArrays, BenchmarkTools

julia> n = 2^22; d = 10; A = sprand(n,n,d/n); x = rand(n);

julia> y = @btime $A*$x;
  909.738 ms (2 allocations: 32.00 MiB)

julia> yt = @btime $(transpose(A))*$x;
  640.637 ms (2 allocations: 32.00 MiB)

you may want to consider the CompressedSparseBlocks.jl package.

julia> using CompressedSparseBlocks

Transforming a SparseMatrixCSC into a SparseMatrixCSB is straightforward, though it might take a few seconds for very large matrices.

julia> Ac = SparseMatrixCSB(A);

but the transformation cost can be eliminated with the speedup from CSB.

julia> yc = @btime $Ac*$x;
  352.766 ms (2 allocations: 32.00 MiB)

julia> yc ≈ y
true

julia> yct = @btime $(transpose(Ac))*$x;
  379.569 ms (3 allocations: 32.00 MiB)

julia> yct ≈ yt
true

API

CompressedSparseBlocks.SparseMatrixCSB — Type
mutable struct SparseMatrixCSB{Tv, Ti} <: SparseArrays.AbstractSparseArray{Tv, Ti, 2}

Matrix type for storing sparse matrices in the Compressed Sparse Blocks format. The standard way of constructing SparseMatrixCSB is to pass a SparseMatrixCSC object, see the constructors.

CompressedSparseBlocks.SparseMatrixCSB — Method
SparseMatrixCSB(A::SparseArrays.SparseMatrixCSC{Tv, Ti<:Integer}) -> SparseMatrixCSB{_A, _B} where {_A, _B}
SparseMatrixCSB(A::SparseArrays.SparseMatrixCSC{Tv, Ti<:Integer}, beta::Integer) -> SparseMatrixCSB{_A, _B} where {_A, _B}

Convert a SparseMatrixCSC matrix A into a SparseMatrixCSB matrix.

Optional arguments

  • beta: The size of each block in base-2 logarithm; if 0 the package decides the block size internally.