Declan Malone >
Math-FastGF2 >
Math::FastGF2::Matrix

Module Version: 0.04
Math::FastGF2::Matrix - Matrix operations for fast Galois Field arithmetic

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; $adjoined=$m->concat($m); $solution=$m->solve;

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.

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.

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".

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.

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

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

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

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

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

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

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;

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

$new_matrix = $m->reorganise;

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 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

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.)

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.

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.

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

$adjoined = $m1->concat($m2);

The number of rows in `$m1`

and `$m2`

must be the same. Returns a new matrix or undef in the case of an error.

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

$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).

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.

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

Copyright (C) 2009 by Declan Malone

This package is free software; you can redistribute it and/or modify it under the terms of the "GNU General Public License" ("GPL").

Please refer to the file "GNU_GPL.txt" in this distribution for details.

This package is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

See the "GNU General Public License" for more details.

syntax highlighting: