public class Linear3SystemSolver
extends java.lang.Object
Instances of this class contain the data necessary to generate the random system and solve it. At construction time, you provide just the desired number of equations and variables; then, you have two possibilities:
generateAndSolve(Iterable, long, LongBigList)
providing a value list;
it will generate
a random linear system on F_{2} with three variables per equation; the constant term for the
kth equation will be the kth element of the provided list. This kind of
system is useful for computing a GOV3Function
.
generateAndSolve(Iterable, long, LongBigList)
with a null
value list;
it will generate a random linear
system on F_{3} with three variables per equation;
to compute the constant term, the system is viewed as a 3hypergraph on the set of variable,
and it is oriented—to
each equation with associate one of its variables, and distinct equations are associated with distinct
variables. The index (0, 1 or 2) of the variable associated to an equation becomes the constant part.
This kind of system is useful for computing a GOVMinimalPerfectHashFunction
.
In both cases, the number of elements returned by the provide Iterable
must
be equal to the number of equation passed at construction time.
To guarantee consistent results when reading a GOV3Function
or GOVMinimalPerfectHashFunction
,
the method tripleToEquation(long[], long, int, int[])
can be used to retrieve, starting from
the triple of hashes generated by a bit vector, the corresponding equation. While having a function returning the edge starting
from a key would be more objectoriented and avoid hidden dependencies, it would also require
storing the transformation provided at construction time, which would make this class nonthreadsafe.
Just be careful to transform the keys into bit vectors using
the same TransformationStrategy
and the same hash function used to generate the random linear system.
This class provides two special access points for classes that have predigested their keys. The methods
generation methods and tripleToEquation(long[], long, int, int[])
use
fixedlength 192bit keys under the form of triples of longs. The intended usage is that of
turning the keys into such a triple using SpookyHash and
then operating directly on the hash codes. This is particularly useful in chunked constructions, where
the keys are replaced by their 192bit hashes in the first place. Note that the hashes are actually
rehashed using Hashes.spooky4(long[], long, long[])
—this is necessary to vary the linear system
whenever it is unsolvable (or the associated hypergraph is not orientable).
Warning: you cannot mix the bitvectorbased and the triplebased constructors and static methods. It is your responsibility to pair them correctly.
We use Jenkins's SpookyHash to compute three 64bit hash values.
Before proceeding with the actual solution of the linear system, we perform a peeling of the hypergraph associated with the system, which iteratively removes edges that contain a vertex of degree one. Since the list of edges incident to a vertex is accessed during the peeling process only when the vertex has degree one, we can actually store in a single integer the XOR of the indices of all edges incident to the vertex. This approach significantly simplifies the code and reduces memory usage. It is described in detail in “Cacheoblivious peeling of random hypergraphs”, by Djamal Belazzougui, Paolo Boldi, Giuseppe Ottaviano, Rossano Venturini, and Sebastiano Vigna, Proc. Data Compression Conference 2014, 2014.
We push further this idea by observing that since one of the vertices of an edge incident to x is exactly x, we can even avoid storing the edges at all and just store for each vertex two additional values that contain a XOR of the other two vertices of each edge incident on the node. This approach further simplifies the code as every 3hyperedge is presented to us as a distinguished vertex (the hinge) plus two additional vertices.
Building and sorting a large 3regular linear system is difficult, as solving linear systems is superquadratic. This classes uses techniques introduced in the paper quoted in the introduction (and in particular broadword programming and lazy Gaussian elimination) to speed up the process by orders of magnitudes.
Note that we might generate nonorientable hypergraphs, or nonsolvable systems, in which case one has to try again with a different seed.
To help diagnosing problem with the generation process, this class will log at debug level what's happening.
Modifier and Type  Field  Description 

long 
numPeeled 
The number of peeled nodes.

long[] 
solution 
The vector of solutions.

int 
unorientable 
The number of generated unorientable graphs.

int 
unsolvable 
The number of generated unsolvable systems.

Constructor  Description 

Linear3SystemSolver(int numVariables,
int numEquations) 
Creates a linear 3regular system solver for a given number of variables and equations.

Modifier and Type  Method  Description 

boolean 
generateAndSolve(java.lang.Iterable<long[]> iterable,
long seed,
LongBigList valueList) 
Generates a random 3regular linear system on F_{2} or F_{3}
and tries to solve it.

boolean 
generateAndSolve(java.lang.Iterable<long[]> triples,
long seed,
LongBigList valueList,
Codec.Coder coder,
int m,
int w) 

boolean 
generateAndSolve(java.lang.Iterable<long[]> triples,
long seed,
LongBigList valueList,
Codec.Coder coder,
int m,
int w,
boolean peelOnly) 

static void 
tripleToEquation(long[] triple,
long seed,
int numVariables,
int[] e) 
Turns a triple of longs into an equation.

public long[] solution
public int unsolvable
public int unorientable
public long numPeeled
public Linear3SystemSolver(int numVariables, int numEquations)
numVariables
 the number of variables.numEquations
 the number of equations.public static void tripleToEquation(long[] triple, long seed, int numVariables, int[] e)
If there are no variables the vector e
will be filled with 1.
triple
 a triple of intermediate hashes.seed
 the seed for the hash function.numVariables
 the nonzero number of variables in the system.e
 an array to store the resulting equation.public boolean generateAndSolve(java.lang.Iterable<long[]> iterable, long seed, LongBigList valueList)
The constant part is provided by valueList
. If it is null
, the system
will be on F_{3} and the constant
part will be obtained by orientation, otherwise the system will be on F_{2}.
iterable
 an iterable returning triples of longs.seed
 a 64bit random seed.valueList
 a value list containing the constant part, or null
if the
constant part should be computed by orientation.Linear3SystemSolver
public boolean generateAndSolve(java.lang.Iterable<long[]> triples, long seed, LongBigList valueList, Codec.Coder coder, int m, int w)
public boolean generateAndSolve(java.lang.Iterable<long[]> triples, long seed, LongBigList valueList, Codec.Coder coder, int m, int w, boolean peelOnly)