The kaMatrix functor

Synopsis

signature kaMATRIX
functor kaMatrix (KA) : kaMATRIX


This functor generates the Kleenean algebra of matrices over a Kleenean algebra.

Functor result interface

structure Ring : KA
type t
val dimension : t -> int * int
val tabulate : int * int -> (int * int -> Ring.t) -> t
val sub : t * (int * int) -> Ring.t
val map : (Ring.t -> Ring.t) -> t -> t
val zero : int * int -> t
val unit : int * int -> t
val sum : t * t -> t
val prod : t * t -> t
val star : t -> t


Description

type t


the type of all matrices with entries from Ring.t.

dimension A

returns the dimension of matrix A.

tabulate (i, j) f

returns a matrix whose field (i,j) contains the value f(i,j).

sub (A, (i, j))

returns the value in field (i,j) of matrix A.

map f t

returns the matrix obtained from A by applying f to its entries.

zero (i, j)

returns the matrix of dimension (i,j) whose fields contain Ring.zero.

unit (i, j)

returns the matrix of dimension (i,j) whose fields (k,k) contain Ring.unit, and all other fiels contain Ring.zero.

sum (A, B)

returns the sum of A and B, by using pointwise addition Ring.sum.

prod (A, B)

returns the product of matrices A and B.

star t

returns the Kleenean closure of matrix A, defined by recursion on the dimension (for square matrices only).

See Also

KA, Path

Discussion

Example:

The matrix algebra can be used for an efficient `all_pairs_shortest_paths'-algorithm: To compute the minimal weight of paths between nodes i and j in a graph, the weights of arcs are coded as a matrix P over the Kleenean algebra Path. The minimal weights of paths between i and j are then the entries of P* in field (i,j).

structure PathMat = kaMatrix(Path);

let 
    val z = Path.zero 
    val P = (PathMat.tabulate) (5,5) 
                 (fn (0,0) => 0 | (0,1) => 3 | (0,2) => 8 | (0,3) => z | (0,4) => ~4
	           | (1,0) => z | (1,1) => 0 | (1,2) => z | (1,3) => 1 | (1,4) => 7
		   | (2,0) => z | (2,1) => 4 | (2,2) => 0 | (2,3) => z | (2,4) => z
		   | (3,0) => 2 | (3,1) => z | (3,2) => ~5| (3,3) => 0 | (3,4) => z
		   | (4,0) => z | (4,1) => z | (4,2) => z | (4,3) => 6 | (4,4) => 0
		   | _ => raise Size)
in 
    PathMat.star P
end

This matrix P* is sometimes computed iteratively by

fun fast_path M =
    let
	val (n,k) = PathMat.dimension M
	fun f (m,M) = if n-1 <= m then M
			else f(2*m, PathMat.prod(M,M))
    in
	f (1,M) 
    end;