Class Modulo3System

java.lang.Object
it.unimi.dsi.sux4j.mph.solve.Modulo3System

public class Modulo3System extends Object
Solver for linear systems on F3.
Author:
Sebastiano Vigna
  • Constructor Details

  • 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.