## How the search is done

### Brief outline of basic algorithm

A set of s linearly independent vectors provides a basis for an s-dimensional
lattice. If we arrange these vectors as rows in an s by s matrix this
matrix is called a generator matrix for the lattice.
There is a beautiful theory stating that a lattice is an
integration lattice if and only if the generator matrix of its reciprocal
lattice is an integer matrix.
The idea behind the set
is that lattices of this class have a generator matrix for which the 1-norm
of each row is exactly
We can then carry out a search by creating all such lattices, checking
their abscissas count, and if it is a potenial good one, compute its degree.
To speed up the search a number of short cuts are taken.
These are described in a paper by
Ronald Cools and
James Lyness available
here.
### Parallelization

Think about the entire search as s nested loops each generating all
possible rows in the generator matrix. We have collapsed the two outer loops
and parallelized over these. Each parallel 'task' is then identified
by its loop index. Solving a 'task' is equivalent to creating all possible
combination of the s-2 last rows and do the above described computation.
The work of a task is large, but not known explicitly in advance, as it
does depend on how effective the different shortcuts are for this
particular task.
Thus to efficiently load balancing the computation,
the distribution of tasks needs to be done dynamically.
### The distributed search

The search is orchestrated by a 'master' who keeps the pool of tasks,
keeps track of what's done and not done, and update the current best
solution. It cooperate with many slaves who does the actual computation.
Each slave is running a Java program taking care of the communication.
As soon as this starts it sends a message to the master saying,
'Hi, I'm ready'. RMI is used for the communication. When a task id
and limits for the abscissa count is received, the Java program kicks
off a Fortran program which do the actual calculations.
The master is another Java program.
If a slave is turned off and never return it's result, the master
just continue through its list. When it has distributed all the initial
tasks and a slave report back ready for more work it just resend
the task not yet completed until all tasks are completed.