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

Class Modulo3System

java.lang.Object

it.unimi.dsi.sux4j.mph.solve.Modulo3System

public class Modulo3System
extends Object

Solver for linear systems on F₃.

Author:

Sebastiano Vigna

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	Modulo3System.Modulo3Equation	An equation on F3.

Constructor Summary

Constructors

Modifier	Constructor	Description
	Modulo3System(int numVars)
protected	Modulo3System(int numVars, ArrayList<Modulo3System.Modulo3Equation> system)

Method Summary

Modifier and Type	Method	Description
void	add(Modulo3System.Modulo3Equation equation)	Adds an equation to the system.
boolean	check(long[] solution)
boolean	check(LongArrayBitVector solutions)
Modulo3System	copy()
boolean	gaussianElimination(long[] solution)	Solves the system using Gaussian elimination and write the solution in an array of longs (mainly for testing purposes).
boolean	gaussianElimination(LongArrayBitVector solution)	Solves the system using Gaussian elimination and write the solution in a bit vector.
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(Modulo3System system, int[][] var2Eq, long[] c, int[] variable, long[] solution)	Solves a system using lazy Gaussian elimination.
String	toString()

Methods inherited from class java.lang.Object

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

Constructor Details

Modulo3System

public Modulo3System(int numVars)

Modulo3System

protected Modulo3System(int numVars,
 ArrayList<Modulo3System.Modulo3Equation> system)

Method Details

copy

public Modulo3System copy()

add

public void add(Modulo3System.Modulo3Equation equation)

Adds an equation to the system.

Parameters:

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

toString

public String toString()

Overrides:

toString in class Object

check

public boolean check(long[] solution)

check

public boolean check(LongArrayBitVector solutions)

gaussianElimination

public boolean gaussianElimination(long[] solution)

Solves the system using Gaussian elimination and write the solution in an array of longs (mainly for testing purposes).

Parameters:

solution - an array where the solution will be written.

Returns:

true if the system is solvable.

gaussianElimination

public boolean gaussianElimination(LongArrayBitVector solution)

Solves the system using Gaussian elimination and write the solution in a bit vector.

Parameters:

solution - a bit vector where the solution will be written using two bits per value.

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(Modulo3System, 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 3 (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(Modulo3System system,
 int[][] var2Eq,
 long[] c,
 int[] variable,
 long[] solution)

Solves a system using lazy Gaussian elimination.

Parameters:

system - a modulo-3 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 3 (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.