Abstract

Sparse triangular matrices.

A triangular matrix is a square matrix where all elements above or below the diagonal are zero, called respectively upper and lower triangular matrixes. While we can always represent an triangular matrix as an ordinary matrix where we store the zeroes, this is wasteful of memory. Instead, we can use a representation where we store only the possibly nonzero elements. This library supports both upper and lower triangular matrices using the same interface, but different concrete types.

Synopsis

module type triangular_matrix = {
type t
type~ mat [n]
val zero: (n: i64) -> mat [n]
val eye: (n: i64) -> mat [n]
val diag [n]: [n]t -> mat [n]
val triangular [n]: [n][n]t -> mat [n]
val dense [n]: mat [n] -> [n][n]t
val idx [n]: (i64, i64) -> mat [n] -> t
val scale [n]: t -> mat [n] -> mat [n]
val + [n]: mat [n] -> mat [n] -> mat [n]
val - [n]: mat [n] -> mat [n] -> mat [n]
val map [n]: (t -> t) -> mat [n] -> mat [n]
val nnz [n]: mat [n] -> i64
val smm [n]: mat [n] -> mat [n] -> mat [n]
}
module type triangular = {
type t
type~ lower [n]
type~ upper [n]
module lower: {
include triangular_matrix with t = t with mat [n] = lower [n]
val transpose [n]: lower [n] -> upper [n]
}
module upper: {
include triangular_matrix with t = t with mat [n] = upper [n]
val transpose [n]: upper [n] -> lower [n]
}
}
module mk_triangular: (T: field) -> triangular with t = T.t

Description

module type triangular_matrix

The module type of a triangular matrix. This module type leaves it unstated whether it is an upper or lower triangular matrix, but specific instantiations make it clear.

type t

The scalar type.

type~ mat [n]

The type of n times n triangular matrices.

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

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

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

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

val diag [n]: [n]t -> mat [n]

The diagonal matrix with zeros everywhere but in the diagonal.

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

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

val idx [n]: (i64, i64) -> mat [n] -> t

idx (i,j) m produces the element at logical position (i,j) in the triangular matrix m, returning zero.

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

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

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

Element-wise addition.

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

Element-wise subtraction.

val map [n]: (t -> t) -> mat [n] -> mat [n]

Map a function across the elements of the matrix.

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

Number of non-zero elements.

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

Matrix multiplication.

module type triangular

The type of modules implementing triangular matrices, with distinct submodules and types for lower and upper triangular matrices.

type t

Matrix element type.

type~ lower [n]

A lower triangular matrix.

type~ upper [n]

An upper triangular matrix.

module lower

Operations on lower triangular matrices.

include triangular_matrix with t = t with mat [n] = lower [n]
val transpose [n]: lower [n] -> upper [n]

Transpose lower triangular matrix, producing upper triangular matrix. O(1).

module upper

Operations on upper triangular matrices.

include triangular_matrix with t = t with mat [n] = upper [n]
val transpose [n]: upper [n] -> lower [n]

Transpose upper triangular matrix, producing lower triangular matrix. O(1).

module mk_triangular

Create a module implementing the triangular module type. Usage: module m = mk_triangular f64.