##
Solvers for diophantine equations

By choosing "Solve" in the main window of DISCRETA, you get the menu above. Here you have the choice between different solvers for integer matrix equations.

All but one solver are implemented by Alfred Wassermann

**LLL print solutions**

This method is based on lattice basis reduction (see A. K. Lenstra, H. W. Lenstra Jr. and L. Lovász) together with an exhaustive enumeration of all solutions. This solver is recommended for problems with large*lambda*.**LLL**

This is the same algorithm as above, with the exception that the solutions are only counted, not printed.**LLL parameters**

Here, some parameters for the lattice basis reduction and the large set algorithms (see below) can be adjusted.**c0_factor**: If this number is too small, the LLL-algorithm fails to compute a complete basis of the kernel. If this number is too large there may be an integer overflow on 32 bit computers.**beta, p**: These numbers determine the quality of the lattice basis reduction. Large values give a better lattice, at the cost of computing time.

**McKay (backtrack)**

This solver was implemented by Brendan McKay and adapted to DISCRETA by Alfred Wassermann. It is very good, if the Kramer-Mesner matrix is not too big and*lambda*is small. Meanwhile, this method is beaten by the algorithm*spread*.**Spread**

This solver is based on backtracking along the rows of the linear system and was proposed by Rudolf Mathon. It is the method of choice for problems with*lambda=1*.**Large set (deterministic)**

This method computes all solutions for the required value of*lambda*(with the algorithm*LLL*). Then we apply the algorithm*spread*to collect a set of solutions which gives a large set. This method was proposed by Spyros Magliveras. It is feasible, if there are at most about 10000 solutions of the original system.**Large set (random)**

This method is due to an idea of Reinhard Laue: The method tries to find*max_solutions*solutions for the required value of*lambda*(with the algorithm*LLL*). Then one solutions out of these solutions is chosen randomly. The corresponding columns of the linear system are deleted, then we try to find a design for the required value of*lambda*in the remaining system. This is iterated until all columns are deleted or there are no solutions. In the first case we have found a large set, in the second case we start again from the beginning. We do this at the most*max_round*times. In each step we stop after*max_loops*loops of the LLL-algorithm.**Attention:**The value*N*of the large set*LS[N](t,k,v)*and the parameters*max_solutions*,*max_round*,*max_loops*have to be adjusted in the submenu**LLL parameter**.- The last thing to do is to check the computed solutions: first press "get solutions from solver" to get the solutions explicitely, then choose "check solutions" to check the correctness of the results.

Remark: You have to click on the pictures to get them largely.

Back to the
description .

Back to the
DISCRETA homepage .

Last updated: September 8, 1999,
Alfred Wassermann