|
Two types of lattice vector enumeration are provided:-
- (a)
- Enumeration of all vectors in a lattice L having norm
less than or equal to n.
- (b)
- Enumeration of all vectors in a lattice L whose distance from
a non-zero vector w is equal or less than n. Note that the vector
w does not have to be in L.
The enumeration of vectors in a lattice is usually very expensive both
in terms of CPU time and memory. The kernel of Magma contains code for
POSIX threads parallelisation for both short and close vector enumerations.
Further, kernel code is provided for distributed computation on top of
the POSIX threads. Enumeration lends itself to very efficient parallelisation
and the speedup factor achieved is close to the number of cores being used.
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) .
We enumerate all non-zero vectors having norm 6 or less in lattice number 6
of rank 64 in the Magma version of the Nebe-Sloane database of lattices using
32 threads on a 16 core machine.
> 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.
- (i)
- If a non-zero vector of minimum norm is sought when the
minimum is known, then an application of strong lattice reduction, for
example using LLL or BKZ reduction, may produce such a vector much
more cheaply than enumeration.
- (ii)
- If a non-zero vector of minimum norm is sought when an
upper bound on the mimimum is known, then the intrinsic Minimum,
which determines the minimum non-zero norm of a lattice, can be used. It
has a parameter NormBound which allows the user to supply an upper
bound on the size of the minimum norm. The intrinsic Minimum returns
the minimum together with a vector having minimum norm. When the minimum
in known this could provide a relatively fast method for obtaining a
vector of minimum norm.
- (iii)
- The intrinsics listed below perform a normal short vctor
enumeration but terminate as soon as one non-zero vector satisfying the
norm condition has been found. It is equivalent to using the
ShortVectors or ShortestVectors intrinsics with the parameter
Max set to 1.
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.
A lattice D of dimension 120 is constructed by forming the direct
sum of five copies on the 24-dimensional Leech lattice. A vector w
is constructed and the non-zero vectors closest to it are enumerated.
The computation was run on a manager machine node1 with
16 cores/32 hyperthreads
together with 4 worker machines each with 16 cores/32 hyperthreads.
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.
A vector closest to a random vector w is found in a random lattice L
of rank 60. The computation was run using 32 hyperthreads on a machine
with 16 cores.
> 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:-
- 1.
- Minimum: Minimum
- 2.
- Kissing number: KissingNumber
- 3.
- Packing radius: PackingRadius
- 4.
- Hermite invariant: HermiteNumber
- 5.
- Centre density: CentreDensity
- 6.
- Density of the lattice packing: Density
- 7.
- Covering radius: CoveringRadius
- 8.
- Theta series: ThetaSeries
Computing each of the above items involves the enumeration of lattice
vectors. In some, such as PackingRadius it is the dominant part
of the computation, while in others, such as KissingNumber and
CoveringRadius, it may be only a small part.
We compute the minimum of lattice number 6 of dimension 64 in the
Magma version of the Nebe-Sloane database by firstly doing a serial
computation and then using 32 POSIX threads on a single 16-core/32
hyperthreads machine.
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.
In this example we use two machines each with 16 cores and 32
hyperthreads to compute the minimum of another lattice of
dimension 64 from the Nebe-Sloane database of lattices.
So we have a manager and one worker each using 32 threads.
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.
We compute 8 terms of the theta series for a lattice of
dimension 40 using Pthreads on a single 16-core machine.
> 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)
The coefficients of the theta series of the lattice of dimension
105
in the Nebe--Sloane database grow very slowly and so determining the first
46 terms can be achieved using direct enumeration:-
> 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))
In the case of a lattice of dimension 72 recently studied by
G. Nebe and M. Watkins the only property that could be determined directly
was
its minimum. However, the modular form method does succeed in computing its
theta
series after a rather lengthy computation. Here we display the first 40
terms:-
displaylines(1 + 6218175600 t 8 + 15281788354560 t 10 + 9026867482214400 t 12 +
1989179450818560000 t 14 + 213006159759990870000 t 16 +
3144087517631410995200 t 18 + 525100718690287495741440 t 20 +
14756609779472604266496000 t 22 + 310160311536865273422120000 t 24 +
5108106498702230684344320000 t 26 + 68347693198345293752360140800 t 28
+
764604200349778385836033966080 t 30 + 7318835829467289011348969122800
t 32 +
61087852878139533146733527040000 t 34 + 451627409037619180720939253760000
t 36 +
2996530109404572751301781710438400 t 38 +
1372164648655533855 t 40 + O(t 42))
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.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|