# NAME

Math::FastGF2::Matrix - Matrix operations for fast Galois Field arithmetic

# SYNOPSIS

`````` use Math::FastGF2::Matrix;

\$m=Math::FastGF2::Matrix->
new(rows => \$r, cols => \$c, width => \$w, org => "rowwise");
\$i=Math::FastGF2::Matrix->
new_identity(size => \$size, width => \$w, org => "rowwise");
\$copy=\$m->copy( ... );
\$copy=\$m->copy_rows(\$row1, \$row2, ... );
\$copy=\$m->copy_cols(\$col1, \$col2, ... );
\$copy=\$m->submatrix(\$row1,\$col1,\$row2,\$col2);
\$copy=\$m->flip(...);
\$copy=\$m->transpose;
\$copy=\$m->reorganise;

\$rows = \$m->ROWS;   \$cols  = \$m->COLS;
\$org  = \$m->ORG;    \$width = \$m->WIDTH;

\$val=\$m->getval(\$row,\$col);
\$m->setval(\$row,\$col,\$val);
\$m->zero;

@vals=\$m->getvals(\$row,\$col,\$words,\$order);
\$vals=\$m->getvals(\$row,\$col,\$words,\$order);
\$vals=\$m->setvals(\$row,\$col,\@vals,\$order);
\$vals=\$m->setvals(\$row,\$col,\$vals,\$order);

\$product=\$m->multiply(\$m);
\$inverse=\$m->invert;
\$solution=\$m->solve;``````

# DESCRIPTION

This module provides basic functionality for handling matrices of Galois Field elements. It is a fairly "close to the metal" implementation using the C language to store the underlying object and handle performance-critical tasks such as bulk input/output of values and matrix multiplication. Less critical tasks are handled by Perl methods.

All matrix elements are treated as polynomials in GF(2^m), with all calculations on them being done using the Math::FastGF2 module.

# CONSTRUCTORS

## new

New Math::FastGF2::Matrix objects are created and initialised to with zero values with the `new()` constructor method:

`````` \$m=Math::FastGF2::Matrix->
new(rows => \$r, cols => \$c, width => \$w, org => "rowwise");``````

The rows and cols parameters specify how many rows and columns the new matrix should have. The width parameter must be set to 1, 2 or 4 to indicate Galois Fields of that many bytes in size.

The `org` parameter is optional and defaults to "rowwise" if unset. This parameter specifies how the matrix should be organised in memory, which affects how the bulk data input/output routines `setvals` and `getvals` enter data and retrieve it from the matrix. With "rowwise" organisation, values are written in left-to-right order first, moving down to the next row as each row becomes full. With "colwise" organisation, values are written top-to-bottom first, moving right to the next column as each column becomes full.

## new_identity

To create a new identity matrix with `\$size` rows and columns, width `\$w` and organisation `\$org`:

`````` \$i=Math::FastGF2::Matrix->
new_identity(size => \$size, width => \$w, org => \$org);``````

As with the `new` constructor, the `org` parameter is optional and default to "rowwise".

## new_cauchy

Create a Cauchy matrix from a set of x and y values:

`````` my @xvals = (1..7);        # all values must be distinct across
my @yvals = (8..10);       # the combined list

# Passing separate x and y lists (rows/cols inferred)
\$i=Math::FastGF2::Matrix->
new_cauchy(width => 1, org => "rowwise",
xvals => \@xvals, yvals => \@yvals
);

# Passing combined list and at least one of rows/cols
\$i=Math::FastGF2::Matrix->
new_cauchy(width => 1, org => "rowwise",
xyvals => [@xvals, @yvals],
rows => scalar(@xvals),
cols => scalar(@yvals),
);``````

Cauchy matrices have the useful property that for a matrix of n rows and k columns, all subsets of k rows are linearly independent with respect to each other. Thus this submatrix is invertible. This has applications in constructing error-correcting codes. See the Crypt::IDA manual page for details.

## new_inverse_cauchy

Creates an inverse Cauchy matrix from a set of y values and an subset of x values:

`````` my @xvals = (20..27);        # all values must be distinct across
my @yvals = (28..30);        # the combined list

\$i=Math::FastGF2::Matrix->
new_inverse_cauchy(width => 1, org => "rowwise",
xylist => [ @xvals, @yvals ],
size => 3,       # size of y list
xvals => [0..3], # indexes into x list
);``````

Note that the xvals parameter in this case is a set of indices into the `@xvals` array. Effectively, it selects 'size' rows from the Cauchy matrix described by `[ @xvals, @yvals ]` and inverts that matrix.

This uses an algorithm described in volume 1 of Knuth's "The Art of Computer Programming", which should run faster than the regular Gaussian elimination method implemented by the `invert` method.

## new_vandermonde

Create a Vandermonde matrix from a list of x values

`````` \$i=Math::FastGF2::Matrix->
new_vandermonde(width => 1, org => "rowwise",
xvals => [ 0..6 ],  # 7 rows
cols   => 3,
);``````

For each x_i value, creates a row of the form:

``````        |     0    1    2          cols-1  |
|   x    x    x   ...    x         |
|    i    i    i          i        |``````

If all the x_i values in the list are distinct, then, like the Cauchy matrix above, taking any 'cols' subset of rows from the matrix gives you an invertible matrix. This is the form of matrix generally used for Reed-Solomon error-correcting codes.

To create the inverse of some cols x cols submatrix, just use the standard `invert` method on it.

## copy

The copy method copy of some or all elements of an existing matrix. The template for a call, showing the default values of all parameters is as follows:

`````` \$new_matrix = \$m->copy(
rows => undef,         # [ \$row1, \$row2, ... ]
cols => undef,         # [ \$col1, \$col2, ... ]
submatrix => undef,    # [ \$row1, \$col1, \$row2, \$col2 ]
);``````

If no parameters are set, then then the entire matrix is copied. The `rows` and `cols` parameters can be set individually or in combination with each other, to copy only the selected rows or columns to the new matrix. The `submatrix` parameter copies a rectangular region of the original matrix into the new matrix. The `submatrix` option cannot be used in combination with the `rows` or `cols` options.

The new matrix will have the same values set for the `width` and `org` parameters as the original matrix.

The `copy_rows`, `copy_cols` and `submatrix` methods are implemented as small wrapper functions which call the `copy` method with the appropriate parameters.

## copy_rows

`` \$new_matrix = \$m->copy_rows (\$row1, \$row2, ... );``

Create a new matrix from the selected rows of the original matrix.

## copy_cols

`` \$new_matrix = \$m->copy_cols (\$col1, \$col2, ... );``

Create a new matrix from the selected columns of the original matrix.

## submatrix

`` \$new_matrix = \$m->submatrix (\$row1, \$col1, \$row2, \$col2);``

Create a new matrix from the selected rectangular region of the original matrix.

## transpose

Return a new matrix which is the transpose of the original matrix. The organisation of the original matrix is carried over to the new matrix:

`` \$new_matrix = \$m->transpose;``

## reorganise

Return a new matrix which has the opposite organisation to the original matrix:

`` \$new_matrix = \$m->reorganise;``

## flip

Carry out transpose and/or reorganise operations in one step:

`````` \$new_matrix = \$m->flip( transpose = > (0 or 1),
org => ("rowwise" or "colwise") );``````

The org parameter is the organisation to use for the new matrix.

# GETTING AND SETTING VALUES

Getting and setting individual values in the matrix is handled by the `getval` and `setval` methods:

`````` \$val=\$m->getval(\$row,\$col);
\$m->setval(\$row,\$col,\$val);``````

Multiple values can be got/set at once, using the more efficient `getvals`/`setvals` methods:

`````` @vals=\$m->getvals(\$row,\$col,\$words,\$order);
\$vals=\$m->getvals(\$row,\$col,\$words,\$order);
\$vals=\$m->setvals(\$row,\$col,\@vals,\$order);
\$vals=\$m->setvals(\$row,\$col,\$vals,\$order);``````

These methods copy the values out of/into the C data structure. The `\$words` parameter to `getvals` specifies how many values to extract from the Matrix.

These methods can take an optional `\$order` parameter which can be used to perform byte-swapping on 2-byte and 4-byte words where it is needed. The possible values are:

0. input is/output should be in native byte order (no byte-swapping)
1. input is/output should be in little-endian byte order
2. input is/output should be in big-endian byte order

## Examples

To swap two rows of a "rowwise" matrix using temporary lists

`````` die "Expected matrix to be ROWWISE\n" unless \$m->ORG eq "rowwise"
@list1 = \$m->getvals(\$row1,0,\$m->COLS);
@list2 = \$m->getvals(\$row2,0,\$m->COLS);
\$m->setvals(\$row1,0,\@list2);
\$m->setvals(\$row2,0,\@list1);``````

The same example using slightly more efficient string form:

`````` die "Expected matrix to be ROWWISE\n" unless \$m->ORG eq "rowwise"
\$str1 = \$m->getvals(\$row1,0,\$m->COLS);
\$str2 = \$m->getvals(\$row2,0,\$m->COLS);
\$m->setvals(\$row1,0,\$str2);
\$m->setvals(\$row2,0,\$str1);``````

This is an example of how not to implement the above. It fails because getvals is being called in a list context. Beware:

`````` (\$str1,\$str2) = ( \$m->getvals(\$row1,0,\$m->COLS),
\$m->getvals(\$row2,0,\$m->COLS) );
\$m->setvals(\$row1,0,\$str2);
\$m->setvals(\$row2,0,\$str1);``````

Likewise, this common idiom also implies a list context:

`` my (\$var) = ...``

When in doubt about list/scalar context, always use a simple assignment to a scalar variable. Alternatively, scalar context can be enforced by using Perl's `scalar` keyword, eg:

`` my (\$str) = (scalar \$m->getvals(...));``

Read in some little-endian values from a file, and have them converted to Perl's internal format if necessary:

`````` # assume ROWWISE, writing values into row \$row of matrix
sysread \$fh, \$str, \$m->COLS * \$m->WIDTH;
\$m->setvals(\$row,0,\$str,1);``````

Take values from a matrix and output them to a file as a list of little-endian values:

`````` # assume ROWWISE, reading values from row \$row of matrix
\$str=\$m->getvals(\$row,0,\$str,1);
syswrite \$fh, \$str, \$m->COLS * \$m->WIDTH;``````

Zero all elements in a matrix (works regardless of matrix organisation):

`` \$m->setvals(0,0,(0) x (\$m->ROWS * \$m->COLS));``

or:

``  \$m->setvals(0,0,"\0" x (\$self->ROWS * \$self->COLS * \$self->WIDTH));``

(which is exactly what the `zero` method does.)

# MATRIX OPERATIONS

## Multiply

To multiply two matrices \$m1 (on left) and \$m2 (on right), use:

`` \$result=\$m1->multiply(\$m2);``

This returns a new matrix in `\$result` or undef on error. The number of columns in `\$m1` must equal the number of rows in `\$m2`. The resulting matrix will have the same number of rows as \$m1 and the same number of columns as \$m2. An alternative form allows storing the result in an existing matrix (of the appropriate dimensions), thus avoiding the overhead of allocating a new one:

`` \$m1->multiply(\$m2,\$result);``

The `\$result` matrix is also returned, though it can be safely ignored.

## Invert

To invert a square matrix (using Gauss-Jordan method):

`` \$inverse=\$m->invert;``

A new inverse matrix is returned if the matrix was invertible, or undef otherwise.

## Concat(enate)

To create a new matrix which has matrix \$m1 on the left and \$m2 on the right, use:

The number of rows in `\$m1` and `\$m2` must be the same. Returns a new matrix or undef in the case of an error.

## Solve

Treat matrix as a set of simultaneous equations and attempt to solve it using Gaussian elimination:

`` \$solution=\$m->solve;``

The result is a new matrix, or undef if the equations have no solution. The input matrix must have at least one more column than rows, with the first \$m->ROWS columns being the coefficients of the equations to be solved (ie, the left-hand side of equations), and the remaining column(s) being the value(s) the equations evaluate to (ie, the right-hand side of equations).

## Equality

To test whether two matrices have the same values:

`````` if (\$m1->eq(\$m2)) {
# Matrices are equal
...
}``````

Testing for inequality:

`````` if (\$m1->ne(\$m2)) {
# Matrices are not equal
...
}``````

See Math::FastGF2 for details of the underlying Galois Field arithmetic.

See Math::Matrix for storing and manipulating matrices of regular numbers.

# AUTHOR

Declan Malone, <idablack@users.sourceforge.net>