Array Types

There are two primary array types in SuiteSparseGraphBLAS.jl: GBVector and GBMatrix, as well as a few specialized versions of those array types. The full type hierarchy is:

AbstractGBArray{T, F, O, N} <: AbstractSparseArray{Union{T, F}, N}
 ├ N = 2 ─ AbstractGBMatrix{T, F} 
 │   ├─ GBMatrix{T, F, RuntimeOrder()}
 │   ├─ OrientedGBMatrix{T, F, O}
 │   └─ GBShallowMatrix{T, F, ColMajor()}
 └ N = 1, O = ColMajor() ─ AbstractGBVector{T, F}
     ├─ GBVector{T, F}
     └─ GBShallowVector{T, F}

The T parameter is the element type of the array, N is the dimensionality, F is the type of the fill value (often Nothing or T), and O is the storage order. The OrientedGBMatrix restricts the orientation to the parameter O to either ByRow() or ByCol().

All of these types attempt to implement most of the AbstractArray interface, and the relevant parts of the SparseArrays interface.

GBMatrix

The GBMatrix is an opaque sparse matrix structure, which adapts to the sparsity of a matrix by changing the implementation internally. There are 4 different internal representations, all stored in either row or column orientation:

1. Dense - Equivalent to a Julia Matrix, except it may be stored in RowMajor() order.
2. Bitmap - 2 dense arrays, one storing booleans in the pattern of the matrix, the other storing the values.
3. Sparse Compressed - Compressed Sparse Column (CSC) or Compressed Sparse Row(CSR)
4. Doubly Compressed or Hypersparse - Doubly Compressed Sparse Column (DCSC or Hypersparse CSC) and Doubly Compressed Sparse Row (DCSR or Hypersparse CSR). See this paper for more information: pdf.

Additionally, when the stored values in a GBMatrix are uniform the value array may be stored in the iso version of one of the formats above. Rather than storing the full value array, an iso GBMatrix will only store the single scalar to improve performance. This is useful for matrices like the unweighted adjacency matrix, where all stored values may be true.

Users should rarely need to directly interact with the underlying storage format, SuiteSparse:GraphBLAS will automatically convert between them as necessary.

Construction

There are several methods to construct GBArrays. Shown here are empty construction, conversion from a dense matrix and a sparse matrix, and coordinate form with uniform or iso coefficients.

julia> x = GBMatrix{Bool}(20_000_000, 50_000)20000000x50000 GraphBLAS bool matrix, hypersparse by row
  no entries, memory: 280 bytes
julia> x = GBMatrix([[1,2] [3,4]])2x2 GraphBLAS int64_t matrix, full by col
  4 entries, memory: 288 bytes

    (1,1)   1
    (2,1)   2
    (1,2)   3
    (2,2)   4
julia> x = GBMatrix(sprand(100, 100, 0.5); fill = 0.0)100x100 GraphBLAS double matrix, bitmap by col
  5082 entries, memory: 144.2 KB

    (5,1)    0.531256
    (6,1)    0.557153
    (7,1)    0.0943923
    (8,1)    0.839623
    (9,1)    0.563748
    (10,1)    0.839269
    (14,1)    0.0713452
    (17,1)    0.321494
    (18,1)    0.288813
    (21,1)    0.391371
    (22,1)    0.99928
    (23,1)    0.33344
    (24,1)    0.838604
    (25,1)    0.828814
    (31,1)    0.640337
    (35,1)    0.848721
    (37,1)    0.43021
    (38,1)    0.951394
    (40,1)    0.291409
    (41,1)    0.676733
    (42,1)    0.240139
    (43,1)    0.483403
    (44,1)    0.354868
    (47,1)    0.395505
    (48,1)    0.971428
    (49,1)    0.763323
    (52,1)    0.956218
    (53,1)    0.140588
    (54,1)    0.710877
    ...
julia> x = GBMatrix(
           rand(1:50_000, 5000), rand(1:500_000, 5000), 1, 500_000, 500_000
       )500000x500000 GraphBLAS int64_t matrix, hypersparse by row
  5000 entries, memory: 192.3 KB
  iso value:   1

    (6,194858)   1
    (36,152849)   1
    (56,116526)   1
    (76,302375)   1
    (79,142866)   1
    (86,14331)   1
    (87,336159)   1
    (91,20310)   1
    (99,121397)   1
    (106,482069)   1
    (110,229698)   1
    (111,336192)   1
    (117,96127)   1
    (131,421541)   1
    (136,494965)   1
    (145,313139)   1
    (154,9876)   1
    (167,110353)   1
    (173,373108)   1
    (185,53572)   1
    (202,232602)   1
    (221,221224)   1
    (233,29602)   1
    (240,444661)   1
    (252,369814)   1
    (256,126011)   1
    (268,29408)   1
    (274,29001)   1
    (283,140186)   1
    ...

GBMatrix{T, F} <: AbstractSparseArray{T, UInt64, 2}

1. Dense
2. Bitmap
3. Sparse Compressed
4. Hypersparse

GBMatrix{T, F}(nrows::Integer, ncols::Integer; fill = defaultfill(F))
GBMatrix{T}(nrows::Integer, ncols::Integer; fill = defaultfill(T))
GBMatrix(I::AbstractVector, J::AbstractVector, X::AbstractVector{T}, dims...; fill=defaultfill(T), combine=+)
GBMatrix(I::AbstractVector, J::AbstractVector, x::T, dims...; fill=defaultfill(T), combine=+)
GBMatrix(A::Union{<:AbstractGBArray, <:AbstractMatrix}; fill = defaultfill(eltype(A)))

GBVector

A GBVector is the one-dimensional equivalent of the GBMatrix, and internally a GBVector is represented in exactly the same fashion. However, they are always column-oriented.

Construction

julia> v = GBVector{ComplexF32}(100)100x1 GraphBLAS float complex matrix, sparse by col
  no entries, memory: 272 bytes
julia> v = GBMatrix(rand(ComplexF64, 3); fill = nothing)3x1 GraphBLAS double complex matrix, full by col
  3 entries, memory: 304 bytes

    (1,1)    0.0186413 + 0.508617i
    (2,1)    0.748939 + 0.523676i
    (3,1)    0.114567 + 0.606418i
julia> v = GBVector(sprand(Bool, 100_000_000, 0.001))100000000x1 GraphBLAS bool matrix, sparse by col
  100149 entries, memory: 880.5 KB

    (248,1)   1
    (1078,1)   1
    (2806,1)   1
    (3000,1)   1
    (3636,1)   1
    (4164,1)   1
    (4318,1)   1
    (7014,1)   1
    (7030,1)   1
    (7115,1)   1
    (7146,1)   1
    (7661,1)   1
    (8982,1)   1
    (9549,1)   1
    (9841,1)   1
    (9883,1)   1
    (10197,1)   1
    (11661,1)   1
    (12296,1)   1
    (14109,1)   1
    (15531,1)   1
    (16340,1)   1
    (16400,1)   1
    (18959,1)   1
    (19197,1)   1
    (20375,1)   1
    (20531,1)   1
    (21407,1)   1
    (21424,1)   1
    ...

GBVector{T, F} <: AbstractSparseArray{T, UInt64, 1}

GBVector{T, F}(n::Integer; fill = defaultfill(F))
GBVector{T}(n::Integer; fill = defaultfill(T))
GBVector(I::AbstractVector, X::AbstractVector{T}, n; fill=defaultfill(T), combine=+)
GBVector(I::AbstractVector, x::T, n; fill=defaultfill(T), combine=+)
GBVector(v::Union{<:AbstractGBVector, <:AbstractVector}; fill = defaultfill(eltype(v)))

Indexing

The usual AbstractArray and SparseArray indexing capabilities are available. Including indexing by scalars, vectors, and ranges.

julia> A = GBMatrix([1,1,2,2,3,4,4,5,6,7,7,7], [2,4,5,7,6,1,3,6,3,3,4,5], [1:12...])7x7 GraphBLAS int64_t matrix, bitmap by row
  12 entries, memory: 832 bytes

    (1,2)   1
    (1,4)   2
    (2,5)   3
    (2,7)   4
    (3,6)   5
    (4,1)   6
    (4,3)   7
    (5,6)   8
    (6,3)   9
    (7,3)   10
    (7,4)   11
    (7,5)   12
julia> SparseMatrixCSC(A)7×7 SparseMatrixCSC{Int64, Int64} with 12 stored entries:
 ⋅  1   ⋅   2   ⋅  ⋅  ⋅
 ⋅  ⋅   ⋅   ⋅   3  ⋅  4
 ⋅  ⋅   ⋅   ⋅   ⋅  5  ⋅
 6  ⋅   7   ⋅   ⋅  ⋅  ⋅
 ⋅  ⋅   ⋅   ⋅   ⋅  8  ⋅
 ⋅  ⋅   9   ⋅   ⋅  ⋅  ⋅
 ⋅  ⋅  10  11  12  ⋅  ⋅
julia> A[4]6
julia> A[1,2]1
julia> A[[1,3,5,7], :]4x7 GraphBLAS int64_t matrix, bitmap by row
  7 entries, memory: 544 bytes

    (1,2)   1
    (1,4)   2
    (2,6)   5
    (3,6)   8
    (4,3)   10
    (4,4)   11
    (4,5)   12
julia> A[1:2:7, :]4x7 GraphBLAS int64_t matrix, bitmap by row
  7 entries, memory: 544 bytes

    (1,2)   1
    (1,4)   2
    (2,6)   5
    (3,6)   8
    (4,3)   10
    (4,4)   11
    (4,5)   12
julia> A[:,:]7x7 GraphBLAS int64_t matrix, bitmap by row
  12 entries, memory: 832 bytes

    (1,2)   1
    (1,4)   2
    (2,5)   3
    (2,7)   4
    (3,6)   5
    (4,1)   6
    (4,3)   7
    (5,6)   8
    (6,3)   9
    (7,3)   10
    (7,4)   11
    (7,5)   12
julia> A[:, 5]7x1 GraphBLAS int64_t matrix, bitmap by col
  2 entries, memory: 328 bytes

    (2,1)   3
    (7,1)   12

The functionality illustrated above extends to GBVector as well.

Transpose

The lazy Julia transpose is available, and the adjoint operator ' is also overloaded to be equivalent for non-Complex types.

Special GBArray Types

OrientedGBMatrix{T, F, O} <: AbstractSparseArray{T, UInt64, 2}

GBMatrix[R | C]{T, F}(nrows::Integer, ncols::Integer; fill = defaultfill(F))
GBMatrix[R | C]{T}(nrows::Integer, ncols::Integer; fill = defaultfill(T))
GBMatrix[R | C](I::AbstractVector, J::AbstractVector, X::AbstractVector{T}, dims...; fill=defaultfill(T), combine=+)
GBMatrix[R | C](I::AbstractVector, J::AbstractVector, x::T, dims...; fill=defaultfill(T), combine=+)
GBMatrix[R | C](A::Union{<:AbstractGBArray, <:AbstractMatrix}; fill = defaultfill(eltype(A)))

OrientedGBMatrix{T, F, O} <: AbstractSparseArray{T, UInt64, 2}

GBMatrix[R | C]{T, F}(nrows::Integer, ncols::Integer; fill = defaultfill(F))
GBMatrix[R | C]{T}(nrows::Integer, ncols::Integer; fill = defaultfill(T))
GBMatrix[R | C](I::AbstractVector, J::AbstractVector, X::AbstractVector{T}, dims...; fill=defaultfill(T), combine=+)
GBMatrix[R | C](I::AbstractVector, J::AbstractVector, x::T, dims...; fill=defaultfill(T), combine=+)
GBMatrix[R | C](A::Union{<:AbstractGBArray, <:AbstractMatrix}; fill = defaultfill(eltype(A)))

GBShallowMatrix{T, F, O, P, B, A} <: AbstractSparseArray{T, UInt64, 2}

GBShallowVector{T, F, P, B, A} <: AbstractSparseArray{T, UInt64, 1}