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 F2. Variables are k-dimensional vectors on F2, 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
All Methods Static Methods Instance Methods Concrete Methods 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()
-
-
-
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 classjava.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 oflazyGaussianElimination(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 aLinear3SystemSolver
). 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, ornull
, 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 aLinear3SystemSolver
). The resulting system must be identical tosystem
. 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)
-
-