Abstract

Operations for performing LU-decomposition with partial (row) pivoting and operations for solving systems of linear equations using the LU-decomposition functionality. The module mk_lup is parameterised over an ordered field. Examples of ordered fields include f64 and f32.

Synopsis

local module type lup = {
type t
val lup [n]: (mat: *[n][n]t) -> ([n][n]t, perm.t [n])
val forsolve [n]: [n][n]t -> [n]t -> [n]t
val backsolve [n]: [n][n]t -> [n]t -> [n]t
val ols [n]: *[n][n]t -> *[n]t -> *[n]t
val lu [n]: (mat: *[n][n]t) -> [n][n]t
val lower [n]: [n][n]t -> [n][n]t
val upper [n]: [n][n]t -> [n][n]t
}
module mk_lup: (T: ordered_field) -> lup with t = T.t

Description

↑local module type lup
↑type t

Type of elements

↑val lup [n]: (mat: *[n][n]t) -> ([n][n]t, perm.t [n])

Perform LU-decomposition with partial (row) pivoting. A call lup A returns a pair (LU,P) of a matrix LU and a permutation P, such that permute P A = matmul (lower LU) (upper LU). Notice that both the lower and upper triangular matrices are embedded in the resulting matrix LU; see the functions lower and upper below.

↑val forsolve [n]: [n][n]t -> [n]t -> [n]t

Forward solving. The expression forsolve L b solves (Lx = b, x), where x and b are vectors and L is a lower-triangular matrix. Reads only lower part of L, excluding the diagonal, and assumes implicit unit diagonal elements.

↑val backsolve [n]: [n][n]t -> [n]t -> [n]t

Backward solving. The expression backsolve U y solves (Ux = y, x), where x and y are vectors and U is an upper-triangular square matrix. Reads only upper part of U, including the diagonal.

↑val ols [n]: *[n][n]t -> *[n]t -> *[n]t

Solve a linear system using LU-decomposition with partial (row) pivoting.

↑val lu [n]: (mat: *[n][n]t) -> [n][n]t

Perform LU-decomposition without pivoting. A call lu A returns a matrix LU containing the lower and upper parts of the decomposition. Due to the lack of pivoting, this function is unstable. Perhaps use the lup function instead. On success, if lu A = LU then A = matmul (lower LU) (upper LU).

↑val lower [n]: [n][n]t -> [n][n]t

Return the unit-lower matrix embedded in the argument matrix. Extracts all lower, non-diagonel elements and returns a matrix containing the unit element in diagonal entries and the zero element in strict-upper entries.

↑val upper [n]: [n][n]t -> [n][n]t

Return the upper matrix embedded in the argument matrix. Extracts all upper elements, including the diagonal elements. The resulting matrix has the zero element in all strict-lower entries.

↑module mk_lup

LU-decomposition module parameterised over an ordered field.