## 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 = {
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

local module type matrix_regular = {
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

local module type sparse = {
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

- ↑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

- ↑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.