Sparse

Usage

use LinearAlgebra.Sparse;

or

import LinearAlgebra.Sparse;

Support for Linear Algebra routines involving sparse data.

A high-level interface to linear algebra operations and procedures for sparse matrices (2D arrays).

Sparse matrices are represented as 2D arrays domain-mapped to a sparse layout. All sparse operations support the CSR layout (LayoutCS.CS(compressRows=true)) and some operations support COO layout (default sparse array layout).

See the Sparse Primer for more information about working with sparse domains and arrays in Chapel.

Sparse Linear Algebra Interface

LinearAlgebra.Sparse follows the same conventions and interface choices as the parent module, LinearAlgebra, with few exceptions. These exceptions are detailed below.

Sparse Domains

In Chapel, changes to the index set of a sparse array must be made directly on the sparse domain. When working with sparse arrays that will require index modification, it is necessary to maintain access to their sparse domains as well. As a result of this, the sparse linear algebra interface provides helper functions for creating both sparse domains and sparse arrays.

A common usage of this interface might look like this:

// Create an empty 3x3 CSR domain
var D = CSRDomain(3,3);

// Create a CSR matrix over this domain
var A = CSRMatrix(D, int);
// The above is equivalent to:
// var A: [D] int;

// Add indices to the sparse domain along the diagonal
D += (0,0);
D += (1,1);
D += (2,2);

// Set all nonzero indices to the value of 1
A = 1;

// A is now a 3x3 sparse identity matrix
writeln(A);

Note

This is an early prototype package submodule. As a result, interfaces may change over the next release.

proc CSRDomain(rows)  where isIntegral(rows)

Return an empty CSR domain over parent domain: {0..<rows, 0..<rows}

proc CSRDomain(rows, cols)  where isIntegral(rows) && isIntegral(cols)

Return an empty CSR domain over parent domain: {0..<rows, 0..<cols}

proc CSRDomain(space: range)

Return an empty CSR domain over parent domain: {space, space}

proc CSRDomain(rowSpace: range, colSpace: range)

Return an empty CSR domain over parent domain: {rowSpace, colSpace}

proc CSRDomain(Dom: domain)  where Dom.rank == 2 && isCSDom(Dom)

Return a CSR domain based on domain: Dom

If Dom is dense, it will be interpreted as the parent domain, and the domain returned will be empty.

If Dom is sparse (CSR), the domain returned will contain the same nonzeros as Dom

proc CSRMatrix(Dom: domain, type eltType = real)  where Dom.rank == 2 && isCSDom(Dom)

Return a CSR matrix over domain: Dom

If Dom is dense, it will be interpreted as the parent domain, and the matrix returned will be empty.

If Dom is sparse (CSR), the matrix returned will contain the same nonzeros as Dom

proc CSRMatrix(A: [?Dom] ?Atype, type eltType = Atype)  where isCSArr(A)

Return a CSR matrix with domain and values of A

If A is dense, only the indices holding nonzero elements are added to the sparse matrix returned.

If A is sparse (CSR), the returned sparse matrix will be a copy of A casted to eltType

proc CSRMatrix(parentDom: domain(2), data: [?nnzDom] ?eltType, indices: [nnzDom], indptr: [?indDom])  where indDom.rank == 1 && nnzDom.rank == 1

Return a CSR matrix constructed from internal representation:

  • parentDom: parent domain for sparse matrix, bounding box for nonzeros indices

  • data: non-zero element values

  • indices: non-zero row pointers

  • indptr: index pointers

proc CSRDomain(parentDom: domain(2), indices: [?nnzDom], indptr: [?indDom])  where indDom.rank == 1 && nnzDom.rank == 1

Return a CSR domain constructed from internal representation

proc CSRMatrix(shape: 2*(int), data: [?nnzDom] ?eltType, indices: [nnzDom], indptr: [?indDom])  where indDom.rank == 1 && nnzDom.rank == 1

Return a CSR matrix constructed from internal representation: - shape: (M,N) bounding box will be {0..#M,0..#N} - data: non-zero element values - indices: non-zero row pointers - indptr: index pointers

proc CSRDomain(shape: 2*(int), indices: [?nnzDom], indptr: [?indDom])  where indDom.rank == 1 && nnzDom.rank == 1

Return a CSR domain constructed from internal representation

proc dot(A: [?Adom] ?eltType, B: [?Bdom] eltType)  where B.isSparse() || A.isSparse()

Generic matrix multiplication, A and B can be a scalar, dense vector, or sparse matrix.

Note

When A is a vector and B is a matrix, this function implicitly computes dot(transpose(A), B), which may not be as efficient as passing A and B in the reverse order.

proc _array.dot(A: [])  where isCSArr(A) || isCSArr(this)

Compute the dot-product

proc _array.dot(a)  where isNumeric(a) && isCSArr(this)

Compute the dot-product

proc transpose(D: domain)  where isCSDom(D)

Transpose CSR domain

proc transpose(A: [?Adom] ?eltType)  where isCSArr(A)

Transpose CSR matrix

proc _array.T  where isCSArr(this)

Transpose CSR matrix

proc _array.plus(A: [?Adom] ?eltType)  where isCSArr(this) && isCSArr(A)

Element-wise addition, supports CSR and COO.

proc _array.minus(A: [?Adom] ?eltType)  where isCSArr(this) && isCSArr(A)

Element-wise subtraction, supports CSR and COO.

proc _array.times(A)  where isCSArr(this) && isCSArr(A)

Element-wise multiplication, supports CSR and COO.

proc _array.elementDiv(A)  where isCSArr(this) && isCSArr(A)

Element-wise division, supports CSR and COO.

proc eye(Dom: domain, type eltType = real)  where isCSDom(Dom)

Return an identity matrix over sparse domain Dom

proc isDiag(A: [?D] ?eltType)  where A.isSparse()

Return true if sparse matrix is diagonal. Supports CSR and COO arrays.

proc isZero(A: [?D] ?eltType)  where A.isSparse()

Return true if sparse matrix is the additive identity (zero matrix).

proc isEye(A: [?D] ?eltType)  where A.isSparse()

Return true if sparse matrix is the multiplicative identity (identity matrix).

proc isHermitian(A: [?D])  where A.isSparse()

Return true if matrix is Hermitian. Supports CSR and COO arrays.

proc isSymmetric(A: [?D])  where A.isSparse(): bool

Return true if sparse matrix is symmetric. Supports CSR and COO arrays.