Abstract

Compressed sparse matrices.

A compressed sparse matrix is a matrix that stores fewer elements than a corresponding dense regular matrix (non-stored elements are assumed to be zero). There are two different kinds of compressed sparse matrices, compressed sparse row matrices, which are indexed by row, and compressed sparse column matrices that are indexed by column. Transposing a compressed sparse row matrix yields (with zero cost) a compressed sparse column matrix (and vice versa).

Synopsis

local module type compressed = {
type t
type~ csr [n] [m]
type~ csc [n] [m]
module csr: {
include matrix_irregular with t = t with mat [n] [m] = csr [n] [m]
val transpose [n] [m]: mat [n] [m] -> csc [m] [n]
val smvm [n] [m]: mat [n] [m] -> [m]t -> [n]t
}
module csc: {
include matrix_irregular with t = t with mat [n] [m] = csc [n] [m]
val transpose [n] [m]: mat [n] [m] -> csr [m] [n]
val vsmm [n] [m]: [n]t -> mat [n] [m] -> [m]t
}
val smsmm [n] [m] [k]: csr [n] [m] -> csc [m] [k] -> csr [n] [k]
}
module mk_compressed: (T: field) -> compressed with t = T.t

Description

local module type compressed
type t
type~ csr [n] [m]
type~ csc [n] [m]
module csr

Compressed sparse row representation.

include matrix_irregular with t = t with mat [n] [m] = csr [n] [m]
val transpose [n] [m]: mat [n] [m] -> csc [m] [n]

Matrix transposition.

val smvm [n] [m]: mat [n] [m] -> [m]t -> [n]t

Sparse matrix vector multiplication. Given a sparse n times m matrix and a vector of size m, the function returns a vector of size n, the result of multiplying the argument matrix with the argument vector.

module csc

Compressed sparse column representation.

include matrix_irregular with t = t with mat [n] [m] = csc [n] [m]
val transpose [n] [m]: mat [n] [m] -> csr [m] [n]

Matrix transposition.

val vsmm [n] [m]: [n]t -> mat [n] [m] -> [m]t

Vector sparse matrix multiplication.

val smsmm [n] [m] [k]: csr [n] [m] -> csc [m] [k] -> csr [n] [k]

Sparse matrix-matrix multiplication.

module mk_compressed

Parameterised compressed sparse matrix module with individual submodules for compressed sparse row (CSR) and compressed sparse column (CSC) representations. The module is parameterised over a field (defined in the linalg package).