Lattice Builder Manual Software Package for Constructing Rank-1 Lattices

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Examples

- Class List
- Class Index
- Class Hierarchy
- Class Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Modules Pages
Public Member Functions | Static Public Attributes | List of all members
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 [11] . More...

`#include <Reducer.h>`

## Public Member Functions
| Reducer (IntLattice &lat)
| Constructor. More...
| Reducer (const Reducer &red)
| Copy constructor.
| ~Reducer ()
| Destructor.
Reducer & | operator= (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 [1] . 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 [11] . More...
bool | shortestVectorDieter (NormType norm)
| Similar to `ShortestVector` but uses the algorithm of Dieter [6], [10] .
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 [11] .

It also implements the method of Lenstra, Lenstra and Lovasz (LLL) [15] as well as the method of Dieter [6] 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 [6] given in Knuth [10] .

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`[1] 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 [11] .

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 [1] .

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