Abstract

Sparse matrices.

A 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 many different kinds of sparse matrices, some that are specialised to store non-zero elements only in certain areas of a matrix and some that make no assumptions about where in the matrix non-zero elements appear. This module features representations that make no assumptions about where in a matrix non-zero elements appear.

Synopsis

local module type matrix = {
type t
type~ mat [n] [m]
val zero: (n: i64) -> (m: i64) -> mat [n] [m]
val eye: (n: i64) -> (m: i64) -> mat [n] [m]
val dense [n] [m]: mat [n] [m] -> [n][m]t
val scale [n] [m]: t -> mat [n] [m] -> mat [n] [m]
val sparse [nnz]: (n: i64) -> (m: i64) -> [nnz](i64, i64, t) -> mat [n] [m]
val nnz [n] [m]: mat [n] [m] -> i64
val coo [n] [m]: mat [n] [m] -> ?[nnz].[nnz](i64, i64, t)
val + [n] [m]: mat [n] [m] -> mat [n] [m] -> mat [n] [m]
val - [n] [m]: mat [n] [m] -> mat [n] [m] -> mat [n] [m]
}
local module type matrix_regular = {
type t
type mat [n] [m]
val zero: (n: i64) -> (m: i64) -> mat [n] [m]
val eye: (n: i64) -> (m: i64) -> mat [n] [m]
val dense [n] [m]: mat [n] [m] -> [n][m]t
val scale [n] [m]: t -> mat [n] [m] -> mat [n] [m]
val sparse [nnz]: (n: i64) -> (m: i64) -> [nnz](i64, i64, t) -> mat [n] [m]
val nnz [n] [m]: mat [n] [m] -> i64
val coo [n] [m]: mat [n] [m] -> ?[nnz].[nnz](i64, i64, t)
val + [n] [m]: mat [n] [m] -> mat [n] [m] -> mat [n] [m]
val - [n] [m]: mat [n] [m] -> mat [n] [m] -> mat [n] [m]
}
local module type sparse = {
type t
type~ csr [n] [m]
type~ csc [n] [m]
type msr [n] [m]
type msc [n] [m]
module csr: {
include matrix 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 with t = t with mat [n] [m] = csc [n] [m]
val transpose [n] [m]: mat [n] [m] -> csr [m] [n]
}
val smm [n] [m] [k]: csr [n] [m] -> csc [m] [k] -> csr [n] [k]
module msr: {
include matrix_regular with t = t with mat [n] [m] = msr [n] [m]
val transpose [n] [m]: mat [n] [m] -> msc [m] [n]
val smvm [n] [m]: mat [n] [m] -> [m]t -> [n]t
}
module msc: {
include matrix_regular with t = t with mat [n] [m] = msc [n] [m]
val transpose [n] [m]: mat [n] [m] -> msr [m] [n]
}
}
module mk_sparse: (T: field) -> sparse with t = T.t

Description

local module type matrix
type t

The scalar type.

type~ mat [n] [m]

The type of sparse matrices of dimension n times m.

val zero: (n: i64) -> (m: i64) -> mat [n] [m]

The zero matrix. Given n and m, the function returns an n times m empty sparse matrix (zeros everywhere).

val eye: (n: i64) -> (m: i64) -> mat [n] [m]

The eye. Given n and m, the function returns an n times m sparse matrix with ones in the diagonal and zeros elsewhere.

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

Convert to dense format. Given a sparse matrix, the function returns a dense representation of the matrix.

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

Scale elements. Given a sparse matrix and a scale value v, the function returns a new sparse matrix with the elements scaled by v.

val sparse [nnz]: (n: i64) -> (m: i64) -> [nnz](i64, i64, t) -> mat [n] [m]

Create a sparse matrix from a coordinate array.

val nnz [n] [m]: mat [n] [m] -> i64

Number of non-zero elements. Given a sparse matrix, the function returns the number of non-zero elements.

val coo [n] [m]: mat [n] [m] -> ?[nnz].[nnz](i64, i64, t)

Convert to coordinate vectors. Given a sparse matrix, convert it to coordinate vectors.

val + [n] [m]: mat [n] [m] -> mat [n] [m] -> mat [n] [m]

Element-wise addition.

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

Element-wise subtraction.

local module type matrix_regular
type t

The scalar type.

type mat [n] [m]

The type of regular-sized sparse matrices of dimension n x m.

val zero: (n: i64) -> (m: i64) -> mat [n] [m]

The zero matrix. Given n and m, the function returns an n times m empty sparse matrix (zeros everywhere).

val eye: (n: i64) -> (m: i64) -> mat [n] [m]

The eye. Given n and m, the function returns an n times m sparse matrix with ones in the diagonal and zeros elsewhere.

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

Convert to dense format. Given a sparse matrix, the function returns a dense representation of the matrix.

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

Scale elements. Given a sparse matrix and a scale value v, the function returns a new sparse matrix with the elements scaled by v.

val sparse [nnz]: (n: i64) -> (m: i64) -> [nnz](i64, i64, t) -> mat [n] [m]

Create a sparse matrix from a coordinate array.

val nnz [n] [m]: mat [n] [m] -> i64

Number of non-zero elements. Given a sparse matrix, the function returns an upper approximation of the number of non-zero elements.

val coo [n] [m]: mat [n] [m] -> ?[nnz].[nnz](i64, i64, t)

Convert to coordinate vectors. Given a sparse matrix, convert it to coordinate vectors.

val + [n] [m]: mat [n] [m] -> mat [n] [m] -> mat [n] [m]

Element-wise addition.

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

Element-wise subtraction.

local module type sparse
type t
type~ csr [n] [m]
type~ csc [n] [m]
type msr [n] [m]
type msc [n] [m]
module csr

Compressed sparse row

include matrix 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

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

Matrix transposition.

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

Sparse matrix-matrix multiplication.

module msr

Mono sparse row

include matrix_regular with t = t with mat [n] [m] = msr [n] [m]
val transpose [n] [m]: mat [n] [m] -> msc [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 msc

Mono sparse column

include matrix_regular with t = t with mat [n] [m] = msc [n] [m]
val transpose [n] [m]: mat [n] [m] -> msr [m] [n]

Matrix transposition.

module mk_sparse

Parameterised sparse matrix module with different representations, including a compressed sparse row (CSR) representation and a mono sparse row (MSR) representation. The module is parameterised over a field (defined in the linalg package). The residual module includes submodules for the different representations, including a csr module, a csc module, an msr module, and an msc module. Sparse matrix-vector multiplication is available in the csr and msr modules.