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...
Inheritance diagram for LatticeTester::Normalizer:
Public Member Functions | |
| Normalizer (double logm, int64_t k, int64_t maxDim, NormType norm=L2NORM) | |
| This is the preferred constructor in all the subclasses. | |
| Normalizer (double logDensity, int64_t maxDim, NormType norm=L2NORM) | |
| This old (legacy) constructor assumes that the lattice is not rescaled and that the (log)density is the same in all dimensions, which is practically never true when rescaling. | |
| Normalizer (int64_t maxDim, NormType norm=L2NORM) | |
| This constructor creates a Normalizer object without computing any bounds. | |
| virtual | ~Normalizer () |
| Destructor. | |
| void | computeBounds (double logm, int64_t k) |
| This method 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. | |
| virtual void | computeBounds (double logDensity) |
This method computes bounds by assuming that the log density is logDensity for all dimensions up to the maximal dimension maxDim, which is rarely true. | |
| 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 |
| This virtual function must be implemented in subclasses. | |
Static Public Attributes | |
| static const int64_t | MAX_DIM = 48 |
| The maximum dimension of the lattices for which this class can compute a 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 \( \tilde\eta_t = \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) := \gamma_t^{1/2} \eta_t^{-1/t}, \]
where the constants \( \gamma_t \) are called the Hermite constants. For the rescaled primal lattice, the density \( \eta_t \) must be replaced by \( \tilde\eta_t\) defined above. The Hermite constants are known exactly only for \( t\leq 8\) and $t=24$. For other 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 particular, if we use \(t\gamma_t\) in place of \(\gamma_t\) in the bounds for the \( L^2\) norm, we get bounds for the \( L^1\) norm.
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) := \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 good lattices, these measures should be close to 1.
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, | ||
| 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]
This old (legacy) constructor assumes that the lattice is not rescaled and that the (log)density is the same in all dimensions, which is practically never true when rescaling.
It creates a Normalizer by assuming that the density is \(\eta=\exp(\text{logDensity})\) in all dimensions. The bounds are 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 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, and also by some constructors in subclasses.
◆ ~Normalizer()
|
inlinevirtual |
Destructor.
Member Function Documentation
◆ computeBounds() [1/2]
| void LatticeTester::Normalizer::computeBounds | ( | double | logm, |
| int64_t | k ) |
This method 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.
It is called by the constructors of subclasses, in which the constants gamma_t are known. The values of \(\log m\) (in natural basis) and \(k\) are passed 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).
◆ computeBounds() [2/2]
|
virtual |
This method computes bounds by assuming that the log density is logDensity for all dimensions up to the maximal dimension maxDim, which is rarely true.
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.
◆ toString()
| std::string LatticeTester::Normalizer::toString | ( | ) | const |
Returns a string that describes this object.
◆ getNorm()
|
inline |
Returns the norm associated with this object.
◆ getMaxDim()
|
inline |
Returns the maximal dimension for this object.
This is the maxDim parameter of the constructors.
◆ 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.
◆ getBound()
|
virtual |
Returns the bound on the length of the shortest nonzero vector in j dimensions.
◆ getGamma()
|
virtual |
This virtual function must be implemented in subclasses.
Returns the estimated value of the Hermite constant \(\gamma_j\) from the subclass. The usual Hermite constants are for the \(L^2\) norm. When they are used for the \(L^1\) norm instead, each \(\gamma_j\) is multiplied by \(j\), as explained in the guide, and this function must return these inflated values denoted \(\gamma_j^{(1)}\) in the guide. This is done in the subclasses. These constants are used by computeBounds.
Reimplemented in LatticeTester::NormaBestLat, LatticeTester::NormaLaminated, LatticeTester::NormaMinkHlaw, and LatticeTester::NormaRogers.
Member Data Documentation
◆ MAX_DIM
|
static |
The maximum dimension of the lattices for which this class can compute a bound.
◆ m_name
|
protected |
Name of the normalizer.
◆ m_norm
|
protected |
Norm type associated with this object.
◆ m_maxDim
|
protected |
Maximum dimension.
Only elements 1 to m_maxDim (inclusive) of m_bounds below will be pre-computed.
◆ 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.
The documentation for this class was generated from the following file:
- include/latticetester/Normalizer.h
