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

Class Modulo2SparseSystem

java.lang.Object

it.unimi.dsi.sux4j.mph.solve.Modulo2SparseSystem

public class Modulo2SparseSystem
extends java.lang.Object

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	Modulo2SparseSystem.Modulo2Equation

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
void	add(Modulo2SparseSystem.Modulo2Equation equation)
boolean	check(long[] solution)
Modulo2SparseSystem	copy()
static boolean	gaussianElimination(int[][] var2Eq, long[] c, int[] variable, long[] solution)
boolean	gaussianElimination(long[] solution)
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(Modulo2SparseSystem system, int[][] var2Eq, long[] c, int[] variable, long[] solution)	Solves a system using lazy Gaussian elimination.
void	print()
int	size()
boolean	solve(int[] solution)

Methods inherited from class java.lang.Object

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

Constructor Detail

Modulo2SparseSystem

public Modulo2SparseSystem(int numVars)

Modulo2SparseSystem

protected Modulo2SparseSystem(int numVars,
                              java.util.ArrayList<Modulo2SparseSystem.Modulo2Equation> system)

Method Detail

print

public void print()

add

public void add(Modulo2SparseSystem.Modulo2Equation equation)

solve

public boolean solve(int[] solution)

size

public int size()

copy

public Modulo2SparseSystem copy()

check

public boolean check(long[] solution)

gaussianElimination

public boolean gaussianElimination(long[] solution)

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

Solves a system using lazy Gaussian elimination.

Parameters:

system - a modulo-3 system.

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.

gaussianElimination

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