Stoat - Where?

An Erlang Matrix Module

As part of a recent investigation into counting Hamiltonian Paths in undirected graphs, I began researching the work of Eric Bax, whose paper on Inclusion Exclusion promised to yield a quick solution. Although I ended up going in a different direction, his reliance on adjacency matrices that would be processed 2ⁿ times required a matrix module that was as efficient as possible. Writing the solution in Erlang, I found a surprising lack of matrix code on the web, with the most developed I could find being here.

Erlang perhaps isn’t the best language for dealing with matrices, with its ‘one-time’ mathematical approach to assignment, however the existing methods all seemed to make use of tuple_to_list(), list_to_tuple() conversion and excessive list copying. Below I present a simple module which is at least more efficient than the above, and relies on a list of lists, using lists:nth() to retrieve elements. Perhaps in the future this will be superceded by new array syntax, but for now it suits my needs.

Matrices are generally stable, by which I mean unchanging in dimensions. Of course matrices can be different sizes, but the majority of matrix operations that return a matrix result return one the same size as at least one of the inputs. Given that we know the matrix dimensions, in theory this makes tuples a suitable choice for implementation, but in practice the immutability of tuples (even more immutable than lists) make them unwieldy and involve a lot of overhead when building them. And with Erlang’s binding there will be lots of rebuilding.

The main approach is to accept that we will be rebuilding the matrix in full each time and generalise to a standard matrix building function that takes matrix size and cell content generator function parameters:

[erlang]
new(Columns, Rows, ContentGenerator) ->
[
[ContentGenerator(Column, Row, Columns, Rows)
|| Column <- lists:seq(1, Columns)
]
|| Row <- lists:seq(1, Rows)
].
[/erlang]
which reads roughly “for each row, for each column on that row, call the content generation function for that cell”.

Each content generator function has the following spec:
[erlang]
fun((pos_integer(), pos_integer(), pos_integer(), pos_integer()) -> any()
[/erlang]

where the four parameters are current column, current row, number of columns, number of rows. A simple identity function is as follows:
[erlang]
fun(Column, Row, _, _) ->
case Column of Row -> 1; _ -> 0 end
end
[/erlang]
which will generate the identity matrix:
[erlang]
[[1 0 0]
[0 1 0]
[0 0 1]]
[/erlang]
A sequential matrix might be generated with the following function:
[erlang]
fun(Column, Row, Columns, _) ->
Columns * (Row – 1) + Column
end
[/erlang]
giving:
[erlang]
[[1 2 3]
[4 5 6]
[7 8 9]]
[/erlang]
while a matrix composed of pseudo-random numbers 1 to MaxValue could be:
[erlang]
fun(_, _, _, _) ->
random:uniform(MaxValue)
end
[/erlang]
where MaxValue is bound in a closure, giving (for example):
[erlang]
[[3 9 6]
[1 1 4]
[6 2 1]]
[/erlang]

With this general mechanism, matrix operations such and addition or multiplication become a lot simpler. All that is required is to define a generator function that sets each cell correctly according to whatever operation you are performing. Matrix addition is defined thus:
[erlang]
% Adds two matrices together.
-spec add(num_matrix(), num_matrix()) -> num_matrix().
add(A, B) ->
new(length(lists:nth(1, A)), length(A),
fun(Column, Row, _, _) ->
element_at(Column, Row, A) + element_at(Column, Row, B)
end
).
[/erlang]

Performance isn’t great for modification of a single cell, as it rebuilds the entire matrix. A future optimisation could include recognising that an entire row hasn’t changed and simply rebinding that. However, for my current use cases, I haven’t needed efficient single-cell manipulation. There are specs for the functions, but very little in the way of error checking. There are no checks for the addition of matrices of two different sizes, for example.

Future extensions will include the ‘Hungarian’ approach to the assignment problem, retrieval functions for entire columns or rows, some unit testing code, and confirmed support for NxM matrices. (Non-square matrices currently work in theory, but not all functions have been tested to work with them.) Check out the code on GitHub. It’s freely available to use and fork, and if you do, be sure to send a pull request!