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

Class Modulo3System

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

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void add​(Modulo3System.Modulo3Equation equation)
      Adds an equation to the system.
      boolean check​(long[] solution)  
      boolean check​(it.unimi.dsi.bits.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​(it.unimi.dsi.bits.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.
      java.lang.String toString()  

      • Methods inherited from class java.lang.Object

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

    • Constructor Detail

      • Modulo3System

        public Modulo3System​(int numVars)

    • Method Detail

      • 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 java.lang.String toString()
        Overrides:
        toString in class java.lang.Object

      • check

        public boolean check​(long[] solution)

      • check

        public boolean check​(it.unimi.dsi.bits.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​(it.unimi.dsi.bits.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.