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
timesm
.- ↑val zero: (n: i64) -> (m: i64) -> mat [n] [m]
The zero matrix. Given
n
andm
, the function returns ann
timesm
empty sparse matrix (zeros everywhere).- ↑val eye: (n: i64) -> (m: i64) -> mat [n] [m]
The eye. Given
n
andm
, the function returns ann
timesm
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 byv
.- ↑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
xm
.- ↑val zero: (n: i64) -> (m: i64) -> mat [n] [m]
The zero matrix. Given
n
andm
, the function returns ann
timesm
empty sparse matrix (zeros everywhere).- ↑val eye: (n: i64) -> (m: i64) -> mat [n] [m]
The eye. Given
n
andm
, the function returns ann
timesm
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 byv
.- ↑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
timesm
matrix and a vector of sizem
, the function returns a vector of sizen
, 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
timesm
matrix and a vector of sizem
, the function returns a vector of sizen
, 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, acsc
module, anmsr
module, and anmsc
module. Sparse matrix-vector multiplication is available in thecsr
andmsr
modules.