Package it.unimi.dsi.sux4j.mph.solve

Class Modulo2System

java.lang.Object

it.unimi.dsi.sux4j.mph.solve.Modulo2System

public class Modulo2System
extends java.lang.Object

Solver for linear systems on F₂. Variables are ^k-dimensional vectors on F₂, with 0 ≤ k ≤ 64.

Author:

Sebastiano Vigna

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	Modulo2System.Modulo2Equation	An equation on F2.

Constructor Summary

Constructors

Modifier	Constructor	Description
	Modulo2System(int numVars)
protected	Modulo2System(int numVars, java.util.ArrayList<Modulo2System.Modulo2Equation> equations)

Method Summary

Modifier and Type	Method	Description
void	add(Modulo2System.Modulo2Equation equation)	Adds an equation to the system.
boolean	check(long[] solution)
Modulo2System	copy()
static boolean	gaussianElimination(int[][] var2Eq, long[] c, int[] variable, long[] solution)
boolean	gaussianElimination(long[] solution)	Solves the system using Gaussian elimination.
static boolean	lazyGaussianElimination(int[][] var2Eq, long[] c, int[] variable, long[] solution)	Solves a system using lazy Gaussian elimination.
boolean	lazyGaussianElimination(long[] solution)	Solves the system using lazy Gaussian elimination.
static boolean	lazyGaussianElimination(Modulo2System system, int[][] var2Eq, long[] c, int[] variable, long[] solution)	Solves a system using lazy Gaussian elimination.
java.lang.String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

Modulo2System

public Modulo2System(int numVars)

Modulo2System

protected Modulo2System(int numVars,
                        java.util.ArrayList<Modulo2System.Modulo2Equation> equations)

Method Detail

copy

public Modulo2System copy()

add

public void add(Modulo2System.Modulo2Equation equation)

Adds an equation to the system.

Parameters:

equation - an equation with the same number of variables of the system.

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

check

public boolean check(long[] solution)

gaussianElimination

public boolean gaussianElimination(long[] solution)

Solves the system using Gaussian elimination.

Parameters:

solution - an array where the solution will be written.

Returns:

true if the system is solvable.

lazyGaussianElimination

public boolean lazyGaussianElimination(long[] solution)

Solves the system using lazy Gaussian elimination.

Warning: this method is very inefficient, as it scans linearly the equations, builds from scratch the var2Eq parameter of lazyGaussianElimination(Modulo2System, int[][], long[], int[], long[]), and finally calls it. It should be used mainly to write unit tests.

Parameters:

solution - an array where the solution will be written.

Returns:

true if the system is solvable.

lazyGaussianElimination

public static boolean lazyGaussianElimination(int[][] var2Eq,
                                              long[] c,
                                              int[] variable,
                                              long[] solution)

Solves a system using lazy Gaussian elimination.

Parameters:

var2Eq - an array of arrays describing, for each variable, in which equation it appears; equation indices must appear in nondecreasing order; an equation may appear several times for a given variable, in which case the final coefficient of the variable in the equation is given by the number of appearances modulo 2 (this weird format is useful when calling this method from a Linear3SystemSolver). Note that this array will be altered if some equation appears multiple time associated with a variable.

c - the array of known terms, one for each equation.

variable - the variables with respect to which the system should be solved (variables not appearing in this array will be simply assigned zero).

solution - an array where the solution will be written.

Returns:

true if the system is solvable.

lazyGaussianElimination

public static boolean lazyGaussianElimination(Modulo2System system,
                                              int[][] var2Eq,
                                              long[] c,
                                              int[] variable,
                                              long[] solution)

Solves a system using lazy Gaussian elimination.

Parameters:

system - a modulo-2 system, or null, in which case the system will be rebuilt from the other variables.

var2Eq - an array of arrays describing, for each variable, in which equation it appears; equation indices must appear in nondecreasing order; an equation may appear several times for a given variable, in which case the final coefficient of the variable in the equation is given by the number of appearances modulo 2 (this weird format is useful when calling this method from a Linear3SystemSolver). The resulting system must be identical to system. Note that this array will be altered if some equation appears multiple time associated with a variable.

c - the array of known terms, one for each equation.

variable - the variables with respect to which the system should be solved (variables not appearing in this array will be simply assigned zero).

solution - an array where the solution will be written.

Returns:

true if the system is solvable.

gaussianElimination

public static boolean gaussianElimination(int[][] var2Eq,
                                          long[] c,
                                          int[] variable,
                                          long[] solution)