Lattice Tester Online Documentation unknown
Software Package For Testing The Uniformity Of Integral Lattices In The Real Space
Loading...
Searching...
No Matches
LatticeTester::FigureOfMeritM< Int, Real > Class Template Reference

This class provides tools to calculate the figure of merit (FOM) \( M_{t_1,\dots,t_d}\) for any given IntLatticeExt object. More...

+ Inheritance diagram for LatticeTester::FigureOfMeritM< Int, Real >:

Public Member Functions

 FigureOfMeritM (const NTL::Vec< int64_t > &t, Weights &w, Normalizer &norma, ReducerBB< Int, Real > *red=0, bool includeFirst=false)
 This constructor will call setTVector (t, includeFirst), then set the 'Weights', Normalizer, and ReducerBB to the given values.
 
virtual ~FigureOfMeritM ()
 
void setTVector (const NTL::Vec< int64_t > &t, bool includeFirst)
 Sets the vector \((t_1,..., t_d)\) in the FOM definition to the vector t.
 
void setWeights (Weights &w)
 Sets the weights used for calculating the FoM.
 
void setNormalizer (Normalizer &norma)
 Sets the normalizer to norma.
 
void setLLL (double delta=0.99999)
 Sets the parameters for the LLL reduction.
 
void setBKZ (double delta=0.99999, int64_t blocksize=10)
 Sets the parameters for the BKZ reduction.
 
void setBB (bool redBB)
 The BB method will be applied iff this flag is set to true (the default value).
 
void setReducerBB (ReducerBB< Int, Real > *red)
 Sets the ReducerBB object that will be used for BB.
 
void setLowBound (double low)
 Sets the low bound for the FOM.
 
void setVerbosity (int64_t verbose)
 The level of verbosity in the terminal output.
 
void setCollectLevel (int64_t collect)
 The level of details in the informations that are collected, such as the worst-case projection, the corresponding shortest vector, its square length, etc.
 
double getMinMeritSqlen ()
 Returns the square length of the shortest vector for the worst-case projection.
 
Coordinates getMinMeritProj ()
 Returns the projection that gives the worst merit value.
 
double computeMeritOneProj (IntLattice< Int, Real > &proj, const Coordinates &coord, double minmerit=DBL_MAX)
 This function computes and returns the merit value for a single projection represented in lattice proj, in dim dimensions.
 
virtual double computeMeritSucc (IntLatticeExt< Int, Real > &lat, double minmerit=DBL_MAX)
 This function computes and returns the FOM only for the projections over sets of successive coordinates of the form {1, 2, ..., m_t.length()} to {1, 2, ..., m_t[0]}, and returns the minimum.
 
virtual double computeMeritNonSucc (IntLatticeExt< Int, Real > &lat, IntLattice< Int, Real > &proj, double minmerit=DBL_MAX)
 This function computes and returns the FOM only for the projections over sets on non-successive coordinates determined by \(S(s,t_s)\) or \(S^{(1)}(s,t_s)\).
 
double computeMerit (IntLatticeExt< Int, Real > &lat, IntLattice< Int, Real > &proj, double minmerit=DBL_MAX)
 This function computes and returns the value of the FOM for the given lattice 'lat', using the norm associated with that lattice.
 

Protected Attributes

NTL::Vec< int64_t > m_t
 
int64_t m_tsize = 0
 
Weightsm_weights
 
Normalizerm_norma
 
double m_deltaLLL = 0.0
 
double m_deltaBKZ = 0.99999
 
int64_t m_blocksizeBKZ = 10
 
bool m_redBB = true
 
CoordinateSets::FromRangesm_coordRange
 
ReducerBB< Int, Real > * m_red
 
NTL::Vec< Real > m_sqlen
 
bool m_includeFirst = false
 
double m_lowbound = 0.0
 
double m_minMerit = DBL_MAX
 
double m_minMeritSqlen = 0
 
Coordinates m_minMeritProj
 
Coordinates m_worstproj
 
int64_t m_verbose = 0
 
int64_t m_collectLevel = 0
 

Detailed Description

template<typename Int, typename Real>
class LatticeTester::FigureOfMeritM< Int, Real >

This class provides tools to calculate the figure of merit (FOM) \( M_{t_1,\dots,t_d}\) for any given IntLatticeExt object.

This FOM is defined as

\[ M_{t_1,\dots,t_d} = \min\left[ \min_{I\in S(t_1)} \frac{\ell_I}{ \omega_I\, \ell_I^*(\eta_I)},\; \min_{2\le s\le d}\, \min_{I\in S(s,t_s)} \frac{\ell_I}{\omega_I \,\ell_I^*(\eta_I)} \right]. \]

In this class, it is computed for the (rescaled) primal lattice and the m-dual is never used. To compute the FOM for the m-dual, see the class FigureOfMeritMDual. Just using the present class for the dualized primal lattice object will not give correct results, because the projections of the m-dual lattice are not the same as the m-duals of the projections.

In the formula, the projections in \(S(t_1)\) are those over successive coordinates in up to \(t_1\) dimensions, while those is \(S(s,t_s)\) are projections over \(s\) distinct coordinates that are non necessarily successive and are all in the set \(\{1,\dots,t_s\}\), for each order \(s > 1\). There are two variants for the latter: the first (default) variant takes \(S(s,t_s)\) as just defined, and the other considers only the set \(S^{(1)}(s,t_s)\) of projections that contain coordinate 1. The parameter includeFirst in the constructor determines which variant is taken: the latter option is taken when includeFirst is set to true. See the guide for more details and examples.

The lengths of the shortest vectors in the projections can be calculated exactly by using the BB algorithm after applying pre-reductions such as LLL or BKZ, or they can be just approximated by the lengths of the shortest basis vector after applying the pre-reductions only. The latter is faster but may not give a shortest vector. The norm used to compute the vector lengths is always the one inside the IntLattice object for which we compute the FOM.

The constructor has two template parameters to specify which Int and Real types are used. It also requires the vector \((t_1,\dots,t_d)\), a Weights object to specify the weights \(\omega_I\), a Normalizer object used to normalize the merit values, a ReducerBB object used for the reduction in case we want to apply BB, and the includeFirst parameter in case we want to change it to true. The last two parameters are optional. The BB is applied if and only if a (nonzero) ReducerBB is given. Otherwise, we just use static methods for the reduction and need no Reducer. By default, the pre-reduction method is BKZ with delta = 0.99999 and blocksize = 10. To change these values and/or apply LLL, one can use setBKZ and/or setLLL. The reductions are always applied in the order: LLL, BKZ, BB. To remove LLL or BKZ, it suffices to set its delta parameter to 0.0.

After a FigureOfMeritM has been created by the constructor, one can use setTVector to set (or reset) the vector \((t_1,\dots,t_d)\), setWeights to change the weights, setLLL or setBKZ to change the LLL or BKZ parameters, etc.

The method computeMerit computes the FOM for a given lattice. The computation is stopped (early exit) as soon as we know that the value of the FOM will be below the lower bound, whose value can be changed via setLowBound. The default value is 0.

Constructor & Destructor Documentation

◆ FigureOfMeritM()

template<typename Int , typename Real >
LatticeTester::FigureOfMeritM< Int, Real >::FigureOfMeritM ( const NTL::Vec< int64_t > & t,
Weights & w,
Normalizer & norma,
ReducerBB< Int, Real > * red = 0,
bool includeFirst = false )

This constructor will call setTVector (t, includeFirst), then set the 'Weights', Normalizer, and ReducerBB to the given values.

◆ ~FigureOfMeritM()

template<typename Int , typename Real >
LatticeTester::FigureOfMeritM< Int, Real >::~FigureOfMeritM ( )
virtual

Member Function Documentation

◆ setTVector()

template<typename Int , typename Real >
void LatticeTester::FigureOfMeritM< Int, Real >::setTVector ( const NTL::Vec< int64_t > & t,
bool includeFirst )

Sets the vector \((t_1,..., t_d)\) in the FOM definition to the vector t.

Note that the values of \(t_1,..., t_d\) are taken from t[0],...,t[d-1], respectively. When includeFirst is true, we consider only the non-successive projections that contain coordinate 1. See the doc of the class FromRanges in CoordinateSets for more details.

◆ setWeights()

template<typename Int , typename Real >
void LatticeTester::FigureOfMeritM< Int, Real >::setWeights ( Weights & w)
inline

Sets the weights used for calculating the FoM.

◆ setNormalizer()

template<typename Int , typename Real >
void LatticeTester::FigureOfMeritM< Int, Real >::setNormalizer ( Normalizer & norma)
inline

Sets the normalizer to norma.

◆ setLLL()

template<typename Int , typename Real >
void LatticeTester::FigureOfMeritM< Int, Real >::setLLL ( double delta = 0.99999)
inline

Sets the parameters for the LLL reduction.

If delta = 0, LLL is not applied.

◆ setBKZ()

template<typename Int , typename Real >
void LatticeTester::FigureOfMeritM< Int, Real >::setBKZ ( double delta = 0.99999,
int64_t blocksize = 10 )
inline

Sets the parameters for the BKZ reduction.

If delta = 0, BKZ is not applied.

◆ setBB()

template<typename Int , typename Real >
void LatticeTester::FigureOfMeritM< Int, Real >::setBB ( bool redBB)
inline

The BB method will be applied iff this flag is set to true (the default value).

◆ setReducerBB()

template<typename Int , typename Real >
void LatticeTester::FigureOfMeritM< Int, Real >::setReducerBB ( ReducerBB< Int, Real > * red)
inline

Sets the ReducerBB object that will be used for BB.

◆ setLowBound()

template<typename Int , typename Real >
void LatticeTester::FigureOfMeritM< Int, Real >::setLowBound ( double low)
inline

Sets the low bound for the FOM.

The FOM computation is stopped as soon as we know it is below this bound. The default value is 0.

◆ setVerbosity()

template<typename Int , typename Real >
void LatticeTester::FigureOfMeritM< Int, Real >::setVerbosity ( int64_t verbose)
inline

The level of verbosity in the terminal output.

The default value is 0 (minimal output). Values from 1 to 4 give increasingly more details.

◆ setCollectLevel()

template<typename Int , typename Real >
void LatticeTester::FigureOfMeritM< Int, Real >::setCollectLevel ( int64_t collect)
inline

The level of details in the informations that are collected, such as the worst-case projection, the corresponding shortest vector, its square length, etc.

The default value is 0 (minimal information, only the FOM). With values from 1 to 4, we collect increasingly more details.

◆ getMinMeritSqlen()

template<typename Int , typename Real >
double LatticeTester::FigureOfMeritM< Int, Real >::getMinMeritSqlen ( )
inline

Returns the square length of the shortest vector for the worst-case projection.

The returned value is valid only if the collection level was at least 1.

◆ getMinMeritProj()

template<typename Int , typename Real >
Coordinates LatticeTester::FigureOfMeritM< Int, Real >::getMinMeritProj ( )
inline

Returns the projection that gives the worst merit value.

The returned value is valid only if the collection level was at least 1.

◆ computeMeritOneProj()

template<typename Int , typename Real >
double LatticeTester::FigureOfMeritM< Int, Real >::computeMeritOneProj ( IntLattice< Int, Real > & proj,
const Coordinates & coord,
double minmerit = DBL_MAX )

This function computes and returns the merit value for a single projection represented in lattice proj, in dim dimensions.

It returns 0 if the computation is not completed for any reason.

◆ computeMeritSucc()

template<typename Int , typename Real >
double LatticeTester::FigureOfMeritM< Int, Real >::computeMeritSucc ( IntLatticeExt< Int, Real > & lat,
double minmerit = DBL_MAX )
virtual

This function computes and returns the FOM only for the projections over sets of successive coordinates of the form {1, 2, ..., m_t.length()} to {1, 2, ..., m_t[0]}, and returns the minimum.

It returns 0 if the computation was not completed for some reason.

Reimplemented in LatticeTester::FigureOfMeritDualM< Int, Real >.

◆ computeMeritNonSucc()

template<typename Int , typename Real >
double LatticeTester::FigureOfMeritM< Int, Real >::computeMeritNonSucc ( IntLatticeExt< Int, Real > & lat,
IntLattice< Int, Real > & proj,
double minmerit = DBL_MAX )
virtual

This function computes and returns the FOM only for the projections over sets on non-successive coordinates determined by \(S(s,t_s)\) or \(S^{(1)}(s,t_s)\).

It returns 0 if the computation was not completed for some reason. The parameter proj is like for computeMerit.

Reimplemented in LatticeTester::FigureOfMeritDualM< Int, Real >.

◆ computeMerit()

template<typename Int , typename Real >
double LatticeTester::FigureOfMeritM< Int, Real >::computeMerit ( IntLatticeExt< Int, Real > & lat,
IntLattice< Int, Real > & proj,
double minmerit = DBL_MAX )

This function computes and returns the value of the FOM for the given lattice 'lat', using the norm associated with that lattice.

The function returns 0 if the computation was not completed for some reason (early exit, error, etc.). The parameter proj points to a secondary IntLattice object used to store the projections when computing the FOM. The maxDim in this object must be large enough so it can store any of the projections: maxDim \(\ge \max(s,t_1)\). Re-using this object permits one to avoid creating new objects internally. We need a full IntLattice object (not only a basis) for when we apply BB to the projection.

Member Data Documentation

◆ m_t

template<typename Int , typename Real >
NTL::Vec<int64_t> LatticeTester::FigureOfMeritM< Int, Real >::m_t
protected

◆ m_tsize

template<typename Int , typename Real >
int64_t LatticeTester::FigureOfMeritM< Int, Real >::m_tsize = 0
protected

◆ m_weights

template<typename Int , typename Real >
Weights* LatticeTester::FigureOfMeritM< Int, Real >::m_weights
protected

◆ m_norma

template<typename Int , typename Real >
Normalizer* LatticeTester::FigureOfMeritM< Int, Real >::m_norma
protected

◆ m_deltaLLL

template<typename Int , typename Real >
double LatticeTester::FigureOfMeritM< Int, Real >::m_deltaLLL = 0.0
protected

◆ m_deltaBKZ

template<typename Int , typename Real >
double LatticeTester::FigureOfMeritM< Int, Real >::m_deltaBKZ = 0.99999
protected

◆ m_blocksizeBKZ

template<typename Int , typename Real >
int64_t LatticeTester::FigureOfMeritM< Int, Real >::m_blocksizeBKZ = 10
protected

◆ m_redBB

template<typename Int , typename Real >
bool LatticeTester::FigureOfMeritM< Int, Real >::m_redBB = true
protected

◆ m_coordRange

template<typename Int , typename Real >
CoordinateSets::FromRanges* LatticeTester::FigureOfMeritM< Int, Real >::m_coordRange
protected

◆ m_red

template<typename Int , typename Real >
ReducerBB<Int, Real>* LatticeTester::FigureOfMeritM< Int, Real >::m_red
protected

◆ m_sqlen

template<typename Int , typename Real >
NTL::Vec<Real> LatticeTester::FigureOfMeritM< Int, Real >::m_sqlen
protected

◆ m_includeFirst

template<typename Int , typename Real >
bool LatticeTester::FigureOfMeritM< Int, Real >::m_includeFirst = false
protected

◆ m_lowbound

template<typename Int , typename Real >
double LatticeTester::FigureOfMeritM< Int, Real >::m_lowbound = 0.0
protected

◆ m_minMerit

template<typename Int , typename Real >
double LatticeTester::FigureOfMeritM< Int, Real >::m_minMerit = DBL_MAX
protected

◆ m_minMeritSqlen

template<typename Int , typename Real >
double LatticeTester::FigureOfMeritM< Int, Real >::m_minMeritSqlen = 0
protected

◆ m_minMeritProj

template<typename Int , typename Real >
Coordinates LatticeTester::FigureOfMeritM< Int, Real >::m_minMeritProj
protected

◆ m_worstproj

template<typename Int , typename Real >
Coordinates LatticeTester::FigureOfMeritM< Int, Real >::m_worstproj
protected

◆ m_verbose

template<typename Int , typename Real >
int64_t LatticeTester::FigureOfMeritM< Int, Real >::m_verbose = 0
protected

◆ m_collectLevel

template<typename Int , typename Real >
int64_t LatticeTester::FigureOfMeritM< Int, Real >::m_collectLevel = 0
protected

The documentation for this class was generated from the following file: