Lattice Builder Manual Software Package for Constructing Rank-1 Lattices
LatCommon::Reducer Class Reference

For a given lattice, this class implements methods to reduce its basis in the sense of Minkowski and to find the shortest non-zero vector of the lattice using pre-reductions and a branch-and-bound (BB) algorithm  . More...

#include <Reducer.h>

## Public Member Functions

Reducer (IntLattice &lat)
Constructor. More...

Reducer (const Reducer &red)
Copy constructor.

~Reducer ()
Destructor.

Reduceroperator= (const Reducer &red)
Assignment operator.

void copy (const Reducer &red)
Copies the reducer red into this object. More...

void transformStage3 (std::vector< long > &z, int &k)
Method used in reductMinkowski to perform a transformation of stage 3 described in  . More...

bool calculCholeski (RVect &DC2, RMat &C0)
Finds a Choleski decomposition of the basis. More...

bool tryZ (int j, int i, int Stage, bool &smaller, Base &WTemp)
Tries to find shorter vectors in reductMinkowski.

bool tryZ0 (int j, bool &smaller)
Tries to find a shorter vector in shortestVector.

bool shortestVector (NormType norm)
Computes the shortest non-zero vector of this lattice with respect to norm norm using branch-and-bound and the algorithm described in  . More...

bool shortestVectorDieter (NormType norm)
Similar to ShortestVector but uses the algorithm of Dieter ,  .

bool redBB (int i, int d, int Stage, bool &smaller)
Tries to shorten the vectors of the primal basis using branch-and-bound, in reductMinkowski.

bool redBB0 (NormType norm)
Tries to shorten the smallest vector of the primal basis using branch-and-bound, in ShortestVector.

void preRedDieter (int d)
Performs the reductions of the preceding two methods using cyclically all values of $$i$$ (only for $$i > d$$ in the latter case) and stops after either MaxPreRed successful transformations have been achieved or no further reduction is possible. More...

bool redDieter (NormType norm)
Finds the shortest non-zero vector using norm norm. More...

void redLLL (double fact, long maxcpt, int dim)
Performs a LLL (Lenstra-Lenstra-Lovasz) basis reduction up to dimension dim with coefficient fact, which must be smaller than 1. More...

bool reductMinkowski (int d)
Reduces the current basis to a Minkowski reduced basis with respect to the Euclidean norm, assuming that the first $$d$$ vectors are already reduced and sorted. More...

void pairwiseRedPrimal (int i, int d)
Performs pairwise reductions. More...

void pairwiseRedDual (int i)
Performs pairwise reductions, trying to reduce every other vector of the {dual\/} basis by adding multiples of the $$i$$-th vector. More...

NScal getMinLength ()
Returns the length of the shortest basis vector in the lattice.

void setBoundL2 (const NVect &V, int dim1, int dim2)
Sets the lower bound on the square length of the shortest vector in dimension $$i$$ to $$V[i]$$, for $$i$$ going from dim1 to dim2.

void trace (char *mess)
Debug function that print the primal and dual bases.

## Static Public Attributes

static const long SHORT_DIET = 1000
Whenever the number of nodes in the branch-and-bound tree exceeds SHORT_DIET in the method ShortestVector, PreRedDieterSV is automatically set to true for the next call; otherwise it is set to false. More...

static const long SHORT_LLL = 1000
Whenever the number of nodes in the branch-and-bound tree exceeds SHORT_LLL in the method ShortestVector, PreRedLLLSV is automatically set to true for the next call; otherwise it is set to false. More...

static const long MINK_LLL = 500000
Whenever the number of nodes in the branch-and-bound tree exceeds MINK_LLL in the method reductMinkowski, PreRedLLLRM is automatically set to true for the next call; otherwise it is set to false.

static const long MAX_PRE_RED = 1000000
Maximum number of transformations in the method PreRedDieter. More...

static long maxNodesBB
The maximum number of nodes % that we are ready to accept in the branch-and-bound tree when calling ShortestVector or reductMinkowski. More...

static bool PreRedDieterSV
These boolean variables indicate which type of pre-reduction is to be performed for ShortestVector (SV) and for reductMinkowski (RM). More...

static bool PreRedLLLSV

static bool PreRedLLLRM

## Detailed Description

For a given lattice, this class implements methods to reduce its basis in the sense of Minkowski and to find the shortest non-zero vector of the lattice using pre-reductions and a branch-and-bound (BB) algorithm  .

It also implements the method of Lenstra, Lenstra and Lovasz (LLL)  as well as the method of Dieter  to reduce a lattice basis. The reduction algorithms in this class use both the primal and the dual lattices, so both lattices must be defined.

## Constructor & Destructor Documentation

 LatCommon::Reducer::Reducer ( IntLattice & lat )

Constructor.

Initializes the reducer to work on lattice lat.

## Member Function Documentation

 bool LatCommon::Reducer::calculCholeski ( RVect & DC2, RMat & C0 )

Finds a Choleski decomposition of the basis.

Returns in C0 the elements of the upper triangular matrix of the Choleski decomposition that are above the diagonal. Returns in DC2 the squared elements of the diagonal.

 void LatCommon::Reducer::copy ( const Reducer & red )

Copies the reducer red into this object.

Note
Richard: Encore utile?
 void LatCommon::Reducer::pairwiseRedDual ( int i )

Performs pairwise reductions, trying to reduce every other vector of the {dual\/} basis by adding multiples of the $$i$$-th vector.

That may change the $$i$$-th vector in the primal basis. Each such dual reduction is actually performed only if that does not increase the length of vector $$i$$ in the primal basis. Always uses the Euclidean norm.

 void LatCommon::Reducer::pairwiseRedPrimal ( int i, int d )

Performs pairwise reductions.

This method tries to reduce each basis vector with index larger than $$d$$ and distinct from $$i$$ by adding to it a multiple of the $$i$$-th vector. Always uses the Euclidean norm.

 void LatCommon::Reducer::preRedDieter ( int d )

Performs the reductions of the preceding two methods using cyclically all values of $$i$$ (only for $$i > d$$ in the latter case) and stops after either MaxPreRed successful transformations have been achieved or no further reduction is possible.

Always use the Euclidean norm.

 bool LatCommon::Reducer::redDieter ( NormType norm )

Finds the shortest non-zero vector using norm norm.

Does not modify the basis. Stops and returns false if not finished after examining possib. Returns true upon success., and returns length in Lmin. Uses the algorithm of Dieter  given in Knuth  .

 void LatCommon::Reducer::redLLL ( double fact, long maxcpt, int dim )

Performs a LLL (Lenstra-Lenstra-Lovasz) basis reduction up to dimension dim with coefficient fact, which must be smaller than 1.

If fact is closer to 1, the basis will be (typically) more reduced'', but that will require more work. The reduction algorithm is applied until maxcpt successful transformations have been done. Always uses the Euclidean norm.

 bool LatCommon::Reducer::reductMinkowski ( int d )

Reduces the current basis to a Minkowski reduced basis with respect to the Euclidean norm, assuming that the first $$d$$ vectors are already reduced and sorted.

If MaxNodesBB is exceeded during {one} of the branch-and-bound step, the method aborts and returns false. Otherwise it returns true, the basis is reduced and sorted by vector lengths (the shortest vector is V and the longest is V[Dim]). % This method does not care about numerical imprecision due to the % (64-bit) floating-point representation. % In this sense, the results are not 100% reliable.

 bool LatCommon::Reducer::shortestVector ( NormType norm )

Computes the shortest non-zero vector of this lattice with respect to norm norm using branch-and-bound and the algorithm described in  .

The Norm member of this object will be changed to norm. If MaxNodesBB is exceeded during {one} of the branch-and-bounds, the method aborts and returns false. Otherwise, it returns true. Uses the pre-reduction algorithms of Dieter and of Lenstra-Lenstra-Lovasz.

 void LatCommon::Reducer::transformStage3 ( std::vector< long > & z, int & k )

Method used in reductMinkowski to perform a transformation of stage 3 described in  .

Also used in ShortestVector. Assumes that $$\sum_{i=1}^t z_i V_i$$ is a short vector that will enter the basis. Tries to reduce some vectors by looking for indices $$i < j$$ such that $$|z_j| > 1$$ and $$q=\lfloor z_i/z_j\rfloor \not=0$$, and adding $$q V_i$$ to $$V_j$$ when this happens. Returns in $$k$$ the last index $$j$$ such that $$|z_j|=1$$.

## Member Data Documentation

 const long LatCommon::Reducer::MAX_PRE_RED = 1000000
static

Maximum number of transformations in the method PreRedDieter.

After MAX_PRE_RED successful transformations have been performed, the prereduction is stopped.

 long LatCommon::Reducer::maxNodesBB
static

The maximum number of nodes % that we are ready to accept in the branch-and-bound tree when calling ShortestVector or reductMinkowski.

When this number is exceeded, the method aborts and returns false.

 bool LatCommon::Reducer::PreRedDieterSV
static

These boolean variables indicate which type of pre-reduction is to be performed for ShortestVector (SV) and for reductMinkowski (RM).

Dieter means the pairwise pre-reduction as in the method PreRedDieter. LLL means the LLL reduction of Lenstra, Lenstra, and Lov\'asz. The variable PreRedDieterSV is originally set to true and the two others are originally set to false. These variables are reset automatically depending on the thresholds MinkLLL, ShortDiet, ShortLLL as explained above.

 const long LatCommon::Reducer::SHORT_DIET = 1000
static

Whenever the number of nodes in the branch-and-bound tree exceeds SHORT_DIET in the method ShortestVector, PreRedDieterSV is automatically set to true for the next call; otherwise it is set to false.

The default value is 1000.

 const long LatCommon::Reducer::SHORT_LLL = 1000
static

Whenever the number of nodes in the branch-and-bound tree exceeds SHORT_LLL in the method ShortestVector, PreRedLLLSV is automatically set to true for the next call; otherwise it is set to false.

% The default value is 1000.

The documentation for this class was generated from the following file:
• latcommon/include/latcommon/Reducer.h