This is a base class for implementing normalization constants used in figures of merit, to normalize the length of the shortest nonzero vector in either the primal or dual lattice. More...
#include <latticetester/Normalizer.h>
Inheritance diagram for LatticeTester::Normalizer:
Public Member Functions | |
| Normalizer (double logm, int64_t k, int64_t maxDim, std::string name="", NormType norm=L2NORM) | |
| This is the preferred constructor in all the subclasses. | |
| Normalizer (double logDensity, int64_t maxDim, std::string name="", NormType norm=L2NORM) | |
| ***** DEPRECATED ***** | |
| Normalizer (int64_t maxDim, std::string name, NormType norm=L2NORM) | |
| This constructor creates a Normalizer object without computing any bounds. | |
| virtual | ~Normalizer () |
| Destructor. | |
| virtual void | computeBounds (double logDensity) |
This method is rarely applicable! It computes bounds by assuming that the log density is logDensity for all dimensions up to the maximal dimension maxDim. | |
| void | computeBounds (double logm, int64_t k) |
This method is called by the constructors of subclasses, in which the constants gamma_t are known. | |
| std::string | toString () const |
| Returns a string that describes this object. | |
| NormType | getNorm () const |
| Returns the norm associated with this object. | |
| int64_t | getMaxDim () const |
| Returns the maximal dimension for this object. | |
| virtual double * | getBounds () const |
| Returns the array that contains the bounds on the lengths of the shortest nonzero vectors. | |
| virtual double | getBound (int64_t j) const |
Returns the bound on the length of the shortest nonzero vector in j dimensions. | |
| virtual double | getGamma (int64_t j) const |
| Returns the value of a lattice constant \(\gamma\) in dimension \(j\). | |
Static Public Attributes | |
| static const int64_t | MAX_DIM = 48 |
| The maximum dimension of the lattices for which this class can give an upper bound. | |
Protected Attributes | |
| std::string | m_name |
| Name of the normalizer. | |
| NormType | m_norm |
| Norm type associated with this object. | |
| int64_t | m_maxDim |
| Maximum dimension. | |
| double * | m_bounds |
Contains the bounds on the length of the shortest nonzero vector in the lattice in each dimension up to maxDim. | |
Detailed Description
This is a base class for implementing normalization constants used in figures of merit, to normalize the length of the shortest nonzero vector in either the primal or dual lattice.
These constants are based on upper bounds (or approximations) on the best possible length, for given lattice density and dimension. The constructors in the various subclasses compute the specific bounds, as explained in Section 9 of the user's guide.
The preferred constructor assumes that the rescaled primal lattice has scaling factor \(m\) and order \(k\), so its density is \(\min(1, m^{k-t})\) in \(t\geq 1\) dimensions, and cannot exceed 1 for projections in \(s < k\) dimensions. This constructor take \( \log m \) and \(k\) as inputs. It invokes computeBounds internally to compute the bounds. We work with the log density instead of the density itself because the latter is sometimes extremely large or extremely small.
Given a (non-rescaled) lattice of density \( \eta_t \) in \(t\) dimensions, the Euclidean length \( d_t \) of a shortest nonzero lattice vector is upper-bounded as follows:
\[ d_t \le d_t^*(\eta_t) \eqdef \gamma_t^{1/2} \eta_t^{-1/t}, \]
where the constants \( \gamma_t \) are known exactly only for \( t\leq 8\). For larger values of \( t \), we use bounds or approximations of these constants, which are defined in subclasses of Normalizer. These bounds also hold for the \( L^1\) lengths of the shortest vectors, but with different constants \( \gamma_t \). In the dual lattice, the density is \(1/\eta_t\) instead, and the Euclidean length \( \ell_t \) of a shortest nonzero lattice vector then obeys:
\[ \ell_t \le \ell_t^*(\eta_t) \eqdef \gamma_t^{1/2} \eta_t^{1/t}. \]
The bounds \( d_t^*(\eta_t)\) and \( \ell_t^*(\eta_t)\) are used to normalize the values of \( d_t \) or \( \ell_t \) computed by the software for given lattices to obtain standardized measures that lie between 0 and 1. For the best lattices, these measures should be close to 1.
The bounds that we actually use are a bit different and are described in Section 9 of the guide. ******
In subclasses, it suffices to implement the getGamma(int) const function and the specialized constructors. The constructors in the present abstract class do not compute any bounds, they basically just reserve the space (an array) for the bounds.
When making a search and examining millions of lattices, it is important to re-use the same Normalizer object, and not construct a new one (and recompute the constants) for each lattice that is examined.
Constructor & Destructor Documentation
◆ Normalizer() [1/3]
| LatticeTester::Normalizer::Normalizer | ( | double | logm, |
| int64_t | k, | ||
| int64_t | maxDim, | ||
| std::string | name = "", | ||
| NormType | norm = L2NORM ) |
This is the preferred constructor in all the subclasses.
It assumes that the rescaled primal lattice has scaling factor \(m\) and order \(k\), so its density is \(m^{k-t}\) for \(t\geq k\), and cannot exceed 1 for projections in \(s < k\) dimensions. The bounds \( d_t^*(\eta)\) will then be computed by assuming those densities. To compute bounds for the m-dual, pass -logm instead of logm. The values of \(\log m\) (in natural basis) and \(k\) must be given as inputs.
◆ Normalizer() [2/3]
| LatticeTester::Normalizer::Normalizer | ( | double | logDensity, |
| int64_t | maxDim, | ||
| std::string | name = "", | ||
| NormType | norm = L2NORM ) |
***** DEPRECATED *****
This old (legacy) constructor assumes that the lattice is not rescaled. It creates a Normalizer by assuming that the density is \(\eta=\exp(\text{logDensity})\) in all dimensions. This is (probably) never true when there is rescaling. The bounds will be computed in up to maxDim dimensions. To compute bounds for the dual, use -logDensity instead of logDensity. Only subclasses can actually compute the bounds. The name parameter gives name that will be printed by the ToString() method. The norm parameter is the NormType used by this object.
◆ Normalizer() [3/3]
This constructor creates a Normalizer object without computing any bounds.
This is used in the case of rank 1 lattices in the NormaPalpha class with a prime density.
◆ ~Normalizer()
|
inlinevirtual |
Destructor.
Member Function Documentation
◆ computeBounds() [1/2]
|
virtual |
This method is rarely applicable! It computes bounds by assuming that the log density is logDensity for all dimensions up to the maximal dimension maxDim.
It ignores all rescaling. This will become the new logDensity in this object. To compute bounds for the dual, use -logDensity instead of logDensity. This method is called by the constructors of subclasses, in which the constants gamma_t are known.
Reimplemented in LatticeTester::NormaPalpha.
◆ computeBounds() [2/2]
| void LatticeTester::Normalizer::computeBounds | ( | double | logm, |
| int64_t | k ) |
This method is called by the constructors of subclasses, in which the constants gamma_t are known.
It computes the bounds that this normalizer will return, by assuming that the primal lattice was rescaled by the factor \(m\) and has order \(k\), so its density is \(m^{k-t}\) for \(t\geq k\), and cannot exceed \(m^s\) for projections in \(s < k\) dimensions. The values of \(\log m\) (in natural basis) and \(k\) must be given as inputs. To compute bounds for the m-dual, just pass -logm instead of logm. The bounds can be retrieved via getBounds() or getBound(j).
◆ getBound()
|
virtual |
Returns the bound on the length of the shortest nonzero vector in j dimensions.
◆ getBounds()
|
virtual |
Returns the array that contains the bounds on the lengths of the shortest nonzero vectors.
Element j of the array is for j dimensions (element 0 is not used). These bounds must have been computed before.
◆ getGamma()
|
virtual |
Returns the value of a lattice constant \(\gamma\) in dimension \(j\).
These constants can be used by subclasses to implement computeBounds(). For this base class, always returns 1.
Reimplemented in LatticeTester::NormaBestLat, LatticeTester::NormaLaminated, LatticeTester::NormaMinkL2, and LatticeTester::NormaRogers.
◆ getMaxDim()
|
inline |
Returns the maximal dimension for this object.
This is the maxDim parameter of the constructors.
◆ getNorm()
|
inline |
Returns the norm associated with this object.
◆ toString()
| std::string LatticeTester::Normalizer::toString | ( | ) | const |
Returns a string that describes this object.
Member Data Documentation
◆ m_bounds
|
protected |
Contains the bounds on the length of the shortest nonzero vector in the lattice in each dimension up to maxDim.
This array is initialized by the computeBounds methods and its values can be accessed via getBound.
◆ m_maxDim
|
protected |
Maximum dimension.
Only elements 1 to m_maxDim (inclusive) of m_bounds below will be pre-computed.
◆ m_name
|
protected |
Name of the normalizer.
◆ m_norm
|
protected |
Norm type associated with this object.
◆ MAX_DIM
|
static |
The maximum dimension of the lattices for which this class can give an upper bound.
The documentation for this class was generated from the following file:
- include/latticetester/Normalizer.h
