Two types of lattice vector enumeration are provided:-
The following intrinsics for enumerating short vectors in a lattice can be executed in parallel:-
A sequence containing all vectors in the lattice L having norm less than or equal to the integer B.
A sequence containing all vectors in the lattice L having norm equal of greater then the integer A and less than or equal to the integer B.
A sequence containing all vectors in the lattice L having minimum non-zero norm.If the vectors of minimal norm are required then the intrinsic ShortestVectors(L) should be used as it is faster. The above intrinsics all include a parameter Max which terminates the enumeration and returns the vectors found once Max vectors satisfying the conditions have been enumerated.
The reader should consult Chapter LATTICES on Lattices for a full description of these functions. In particular, each of them has several parameters giving the user some control over the enumeration. The progress of an enumeration can be tracked using SetVerbose("Enum", 2) .
> SetNthreads(32); > L := Lattice(LatticeDatabase(), 64, 6); > time sv6 := ShortVectors(L, 6); > #sv6; 1305600
So the 1,305,600 non-zero vectors having norm 6 or less in L were enumerated in 63,278 seconds.
For some applications it suffices to find a single vector satisfying the norm condition. There at least three ways of doing this efficiently.
A single non-zero vector of the lattice L having norm at most B, or the zero vector if there is no such vector.
A single non-zero vector v of the lattice L having norm such that A ≥(Norm)(v) ≤B, where A and B are integers.
A single non-zero vector of the lattice L having minimum norm.
The theta series for lattice number 1 of rank 105 in the Nebe-Sloane lattice database shows that there are vectors of norm 40. We find one such vector using 32 threads on a 16 core machine.
> SetNthreads(32);
> L := Lattice(LatticeDatabase(), 105, 1);
> sv40 := ShortVector(L, 40, 40);
> sv40;
(1 -15 9 -10 0 3 -6 4 -2 6 2 0 3 -3 1 -3 -1 4 4 -5 7 10 3 -2 5 -2 7
-5 -1 1 7 -2 -2 -3 -3 -1 0 1 -1 2 -2 1 1 2 0 0 3 0 0 -1 1 1 1 0
0 1 1 2 2 2 -1 0 0 0 1 2 0 0 -1 1 0 -1 -1 2 -1 -3 1 -2 1 -2 -1
0 0 -1 1 -2 -2 1 0 1 -2 1 2 1 0 0 0 0 1 -1 0 0 -2 1 0)
> Norm(sv40);
40
The computation took 901 seconds real time.
The intrinsics for enumerating close vectors are similar to those for enumerating short vectors. Again the parameter Max allows early termination.
The following functions which enumerate close vectors in a lattice can be executed in parallel:-
A sequence containing all vectors v in the lattice L close to the vector w such that Norm(v - w) ≤B. The vector w need not belong to the lattice L.
A sequence containing all vectors v in the lattice L close to the vector w such that A ≤(Norm)(v - w) ≤B. The vector w need not belong to the lattice L.
A sequence containing all vectors v in the lattice L such that Norm(v, w) is a minimum. The vector w need not belong to the lattice L.
Lattice number 1 of rank 105 in the Nebe-Sloane lattice database is created and an arbitrary vector w is found. We then enumerate the vectors of norm 40 using 32 hyperthreads on a machine with 16 cores.
> SetNthreads(32); > L := Lattice(LatticeDatabase(), 105, 1); > B := Basis(L); > w := 3* B[23] + 7*B[37]; > time cv40 := CloseVectors(L, w, 40, 40); Time: 1820.750[r] > #cv40; 478548
So there are 478,548 vectors at distance 40 from the vector w. The real time for the computation was 1,854 seconds while the total CPU time was 55,825 seconds.
The following were executed on the master machine node1:-
> SetNthreads(32);
> StartWorkers("node2", 32); // start worker with 32 threads on node2
> StartWorkers("node3", 32); // start worker with 32 threads on node3
> StartWorkers("node4", 32); // start worker with 32 threads on node4
> StartWorkers("node5", 32); // start worker with 32 threads on node5
> L := Lattice(LatticeDatabase(),"Leech");
> D := DirectSum([L, L, L, L, L]);
> w := (D.9+D.24+D.31+D.44+D.67+D.60+D.75+D.82+D.97)/2;
> Time cv, m := ClosestVectors(D, w);
Time: 45008.000[r]
> #cv;
10616832
The enumeration found 10, 616, 832 = 2 x 484 lattice vectors each of distance 9 from the vector w. The real time for the computation was 45,008 seconds while the total CPU time was 1,377,986 seconds.
A single non-zero vector w of the lattice L such that Norm(v - w) ≤B, or the zero vector if there is no such vector.
A single non-zero vector w of the lattice L such that A ≤(Norm)(v - w) ≤B or the zero vector if there is no such vector.
A single non-zero vector of the lattice L that is closest to w.
> SetNthreads(32);
> d := 60;
> B:= Matrix(d, d, [Random([-99..99]) : i in [1..d^2]]);
> L := LatticeWithBasis(B);
> L:Minimal;
Lattice of rank 60 and degree 60
> w := Vector([Random([-99..99]) : i in [1..d]]);
> w;
(50 -85 -21 -40 4 -72 32 -90 51 -78 -93 -84 -12 60 90 35 55 91 -54 -87 -92 -82
-92 -7 75 72 -4 55 22 -81 88 56 23 94 1 -91 -16 -8 38 -93 -26 -41 -75 57 49
-6 -55 56 31 41 -34 -28 34 -22 -74 23 24 31 -80 -35)
> Norm(w);
210094
> time sv := ClosestVector(L, w);
Time: 90.270[r]
> sv;
(68 -68 -130 -10 -68 -154 88 -76 122 -113 -156 -37 34 43 77 -17 -9 -119 -202 -79
-117 -86 -77 -1 53 41 24 -64 34 -106 125 101 79 -11 143 -12 62 -9 -13 -131
-47 -19 47 140 73 -39 -25 4 -94 1 -104 -45 -83 -52 -89 -18 -41 30 -86 66)
> Norm(sv);
400300
> Norm(sv - w);
270010
The total CPU time was 1540 seconds while the real time was 90 seconds.
If parallelism is turned on then the computation of each of the following lattice properties is parallelised to the extent that vector enumeration is used:-
Note that lattices loaded from the database often contain some properties of the lattice and so these need to be removed in order to avoid Magma using the data from the database instead of computing it.
> // Serial computation (1 thread) > L := Lattice(LatticeDatabase(), 64, 6); > time m := Minimum(L); m; Time: 2566.750 8 > // Parallel computation (32 threads) > SetNthreads(32); > L := Lattice( LatticeDatabase(), 64, 6); > time m := Minimum(L); m; Time: 125.850 8
The multithread calculation is 20.4 times faster than the serial computation. For harder problems the ratio of serial time to multicore time approaches n, where n is the number of threads being used. When using a machine with hyperthreading there may be benefit in setting the number of threads to be used higher than the number of cores as in the case above.
The manager input is:
> SetNthreads(32);
> StartWorkers("node2", 32); // start worker with 32 threads on node2
> L := Lattice( LatticeDatabase(), 64, 4);
> time m := Minimum(L);
This is a hard enumeration as the minimum turns out to be 12 and so all possible combinations of basis vectors that could produce a vector of norm less than 12 have to be considered. The serial time is 239,741 seconds while the real time for the parallel run is 5,647 seconds. The use of 32 POSIX threads on the manager reduces the runtime by a factor of 21. Using a second machine (a worker) cuts that time in half, giving us a speed up by factor of 42.45, which is what we expect. A small amount of data suggests that using two identical workers results in cutting the single machine using POSIX threads time by a factor close to 3.
We determine the kissing number of the first lattice of dimension 48 in the Nebe-Sloane database. We use 32 threads on a 16-core machine.
> SetNthreads(32); > L := Lattice( LatticeDatabase(), 48, 1 ); > kn := KissingNumber(L : NormBound := 8); > kn; 9828000
The minimum of the lattice is 8 and we find that the kissing number is 9,828,000. The runtime was 87,940 seconds. As a comparison, computing the minimum took 3,295 seconds also using 32 threads.
If the first few terms of the theta series of a lattice can be computed cheaply then it provides some important information about the lattice. The intrinsic for computing the first n terms of the theta series for lattice L is ThetaSeries (L, n). The direct computation of the terms is similar to an application of ShortVectors and so it benefits directly from the parallelisation of enumeration.
The theta series of an integral lattice L is (the q-expansion of) a modular form whose weight is half the dimension of the lattice. The space of modular forms having even weight, level and character is finite dimensional, which means that the theta series is uniquely characterised as an element of that space from a knowledge of finitely many of its coefficients. Techniques for identifying the modular form in that space are being developed and this is likely to be a useful method when calculating the theta series of many lattices. One benefit of this approach is that it yields the entire theta series in the sense that the user can request any number of terms given the modular form of the lattice.
> SetNthreads(32); > L := Lattice(LatticeDatabase() 40, 10); > time ts<t> := ThetaSeries(L, 8);
The real time for the computation was 1,936 seconds and the CPU time was 57,722 seconds. The computation produces the following terms of the theta series:- 1 + 39600 t4 + 1048576 t5 + 45916160 t6 + 817889280 t7 + 10378028080 t8 + O(t9)
> SetNthreads(32); > L := Lattice(LatticeDatabase() 105, 1); > time ts<t> := ThetaSeries(L, 46); > ts;
The computation was done on a single 16-core machine using Pthreads.
The real time for the computation was 16,944 seconds and the CPU time was
524,539 seconds. The computation produces the following terms of the theta
series:-
displaylines(1 + 1890 t24 + 3780 t28 + 15120 t34 + 57960 t36 + 45360 t38
+ 478548 t40 +
635040 t42 +
2381400 t44
+ 5276880 t46 + O(t47))
This calculation made heavy use of the parallel enumeration code and the real time was 276,498 seconds on a 16 core machine running no other jobs.