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

Download:
Math-FastGF2/Math-FastGF2-0.04.tar.gz

Dependencies

Annotate this POD

View/Report Bugs
Module Version: 0.04   Source  

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

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:

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

Solve

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

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

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>

COPYRIGHT AND LICENSE ^

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.

DISCLAIMER ^

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: