NAME

Algorithm::GaussianElimination::GF2 - Solve linear systems of equations on GF(2)

SYNOPSIS

  use Algorithm::GaussianElimination::GF2;

  my $age = Algorithm::GaussianElimination::GF2->new;
  $age->new_equation(1, 0, 0, 1 => 1);
  $age->new_equation(0, 0, 1, 1 => 0);
  my ($sol, @base0) = $age->solve;

  # or you can also create the equations setting elements at given
  # positions:

  my $age = Algorithm::GaussianElimination::GF2->new;
  my $eq1 = $age->new_equation;
  $eq1->a(0, 1);
  $eq1->a(3, 1);
  $eq1->b(1);
  my $eq2 = $age->new_equation;
  $eq2->a(2, 1);
  $eq2->a(3, 1);
  $eq2->b(0);
  my ($sol, @base0) = $age->solve;

DESCRIPTION

This module implements a variation of the Gaussian Elimination algorithm that allows to solve systems of linear equations over GF(2).

Algorithm::GaussianElimination::GF2 methods

Those are the interesting methods:

$age = Algorithm::GaussianElimination::GF2->new;

$eq = $age->new_equation(@a, $b)

$eq = $age->new_equation()

Creates and adds a new equation to the algorithm.

The returned value is a reference to the equation object that can be used to change the equation coeficients before calling the solve method.

($sol, @base0) = $age->solve

$sol = $age->solve

This method solves the system of equations.

When the system is inconsistent it returns an empty list.

When the system is consistent and uniquely determined it returns the solution as an array reference.

When the system is consistent and underdetermined it returns one solution as an array reference and a base of the vector space formed by the solutions of the homogeneous system. In scalar context, only the solution vector is returned.

Algorithm::GaussianElimination::GF2::Equation methods

Those are the methods available to manipulate the equation objects:

$a = $eq->a($ix)

$eq->a($ix, $a)

Retrieves or sets the value of the equation coeficient at the given index.

$b = $eq->b

$eq->b($b)

Retrieves or sets the value of the constant term of the equation.

$eq->len

Returns the internal length of the coeficients vector.

Note that this value is just a hint as the internal representation grows transparently when new coeficients are set or inside the solve method.

SEE ALSO

The Wikipedia page about systems of linear equations: http://en.wikipedia.org/wiki/System_of_linear_equations.

The Wikipedia page about the Galois Field of two elements GF(2): http://en.wikipedia.org/wiki/GF%282%29.

The Wikipedia page about the Gaussian Elimination algorithm: http://en.wikipedia.org/wiki/Gaussian_elimination.

The inception of this module lays on this PerlMonks post: http://perlmonks.org/?node_id=940327.

Math::FastGF2 implements a much richer and faster set of operations for GF(2).

COPYRIGHT AND LICENSE

Copyright (C) 2011, 2012 by Salvador Fandiño (sfandino@yahoo.com)

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.14.2 or, at your option, any later version of Perl 5 you may have available.