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 $K(s,\delta)$ is that lattices of this class have a generator matrix for which the 1-norm of each row is exactly $\delta$ 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.