Class Modulo2SparseSystem


  • public class Modulo2SparseSystem
    extends java.lang.Object
    • Constructor Detail

      • Modulo2SparseSystem

        public Modulo2SparseSystem​(int numVars)
    • Method Detail

      • print

        public void print()
      • solve

        public boolean solve​(int[] solution)
      • size

        public int size()
      • 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)