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".
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:
$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 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 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-2019 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.