BasisConstruction.h File Reference

Static functions to construct a basis from a set of generating vectors that are not necessarily independent, to construct a triangular basis, to construct the basis for a projection over a given subset of coordinates, and to obtain the \(m\)-dual of a given basis. More...

Namespaces
namespace	LatticeTester
	LatticeTester namespace.

Functions
template<typename Int , typename Real >
static long	LatticeTester::LLLConstruction0 (IntMat &gen, const double delta=0.9, long r=0, long c=0, RealVec *sqlen=0)
	This function takes a set of generating vectors of a lattice in matrix gen and finds a lattice basis by applying LLL reduction with the given value of delta, using the NTL implementation specified by prec.
template<typename Int , typename Real >
static void	LatticeTester::LLLBasisConstruction (IntMat &gen, const Int &m, const double delta=0.9, long r=0, long c=0, RealVec *sqlen=0)
	Similar to LLLConstruction0, except that this function adds implicitly the vectors \(m \mathbf{e}_i\) to the generating set, so it always returns a square matrix.
template<typename Int >
static void	LatticeTester::lowerTriangularBasis (IntMat &basis, IntMat &gen, const Int &m, long r=0, long c=0)
	Takes a set of generating vectors in the matrix gen and iteratively transforms it into a lower triangular lattice basis into the matrix basis.
template<typename Int >
static void	LatticeTester::upperTriangularBasis (IntMat &basis, IntMat &gen, const Int &m, long r=0, long c=0)
	Same as lowerTriangularBasis, except that the returned basis is upper triangular.
template<typename Int >
static void	LatticeTester::upperTriangularBasisOld96 (IntMat &basis, IntMat &gen, const Int &m, long r=0, long c=0)
	The old version from [3] and [6].
template<typename Int >
static void	LatticeTester::mDualLowerTriangular (IntMat &basisDual, const IntMat &basis, const Int &m, long dim=0)
	Takes a lower-triangular basis matrix basis and computes the m-dual basis basisDual.
template<typename Int >
static void	LatticeTester::mDualUpperTriangular (IntMat &basisDual, const IntMat &basis, const Int &m, long dim=0)
	Takes a upper triangular basis matrix basis and computes the m-dual basis basisDual.
template<typename Int >
static void	LatticeTester::mDualUpperTriangularOld96 (IntMat &basisDual, const IntMat &basis, const Int &m, long dim=0)
	This function does essentially the same thing as mDualUpperTriangular, but the algorithm is slightly different.
template<typename Int >
static void	LatticeTester::mDualBasis (IntMat &basisDual, const IntMat &basis, const Int &m)
	This function assumes that basis contains a basis of the primal lattice scaled by the factor m, not necessarily triangular, and it returns in basisDual the m-dual basis.
template<typename Int >
static void	LatticeTester::projectMatrix (IntMat &out, const IntMat &in, const Coordinates &proj, long r=0)
	This function overwrites the first r rows of matrix 'out' by a matrix formed by the first r rows of the c columns of matrix in that are specified by proj, where ‘c = size(proj)’ is the cardinality of the projection proj.
template<typename Int , typename Real >
static void	LatticeTester::projectionConstructionLLL (IntMat &projBasis, const IntMat &inBasis, const Coordinates &proj, const Int &m, const double delta=0.9, long r=0, RealVec *sqlen=0)
	Constructs a basis for the projection proj of the lattice with basis inBasis, using LLLBasisConstruction, and returns it in projBasis.
template<typename Int >
static void	LatticeTester::projectionConstructionUpperTri (IntMat &projBasis, const IntMat &inBasis, IntMat &genTemp, const Coordinates &proj, const Int &m, long r=0)
	Same as projectionConstructionLLL, but the construction is made using upperTriangularBasis, so the returned basis is upper triangular.
template<typename Int >
static void	LatticeTester::projectionConstructionUpperTri (IntMat &projBasis, const IntMat &inBasis, const Coordinates &proj, const Int &m, long r=0)
template<typename Int >
static void	LatticeTester::projectionConstruction (IntMat &projBasis, const IntMat &inBasis, const Coordinates &proj, const Int &m, const ProjConstructType projType=LLLPROJ, const double delta=0.9)
	In this version, the construction method is passed as a parameter.
template<>
long	LatticeTester::LLLConstruction0 (NTL::Mat< long > &gen, const double delta, long r, long c, NTL::Vec< double > *sqlen)
template<>
long	LatticeTester::LLLConstruction0 (NTL::Mat< NTL::ZZ > &gen, const double delta, long r, long c, NTL::Vec< double > *sqlen)
template<>
long	LatticeTester::LLLConstruction0 (NTL::Mat< NTL::ZZ > &gen, const double delta, long r, long c, NTL::Vec< xdouble > *sqlen)
template<>
long	LatticeTester::LLLConstruction0 (NTL::Mat< NTL::ZZ > &gen, const double delta, long r, long c, NTL::Vec< quad_float > *sqlen)
template<>
long	LatticeTester::LLLConstruction0 (NTL::Mat< NTL::ZZ > &gen, const double delta, long r, long c, NTL::Vec< NTL::RR > *sqlen)
template<typename Int , typename Real >
void	LatticeTester::LLLBasisConstruction (IntMat &gen, const Int &m, double delta, long r, long c, RealVec *sqlen)
	Similar to LLLConstruction0, except that this function adds implicitly the vectors \(m \mathbf{e}_i\) to the generating set, so it always returns a square matrix.
template<typename Int >
void	LatticeTester::lowerTriangularBasis (IntMat &basis, IntMat &gen, const Int &m, long dim1, long dim2)
	Takes a set of generating vectors in the matrix gen and iteratively transforms it into a lower triangular lattice basis into the matrix basis.
template<typename Int >
void	LatticeTester::upperTriangularBasis (IntMat &basis, IntMat &gen, const Int &m, long dim1, long dim2)
	Same as lowerTriangularBasis, except that the returned basis is upper triangular.
template<typename Matr , typename Int >
void	LatticeTester::upperTriangularBasisOld96 (Matr &V, Matr &W, const Int &m, int64_t lin, int64_t col)
template<typename Int >
void	LatticeTester::mDualLowerTriangular (IntMat &B, const IntMat &A, const Int &m, long dim)
	Takes a lower-triangular basis matrix basis and computes the m-dual basis basisDual.
template<typename Int >
void	LatticeTester::mDualUpperTriangular (IntMat &B, const IntMat &A, const Int &m, long dim)
	Takes a upper triangular basis matrix basis and computes the m-dual basis basisDual.
template<typename Int >
void	LatticeTester::mDualUpperTriangularOld96 (IntMat &basisDual, const IntMat &basis, const Int &m, long dim)
	This function does essentially the same thing as mDualUpperTriangular, but the algorithm is slightly different.
template<>
void	LatticeTester::mDualUpperTriangularOld96 (NTL::Mat< NTL::ZZ > &basisDual, const NTL::Mat< NTL::ZZ > &basis, const NTL::ZZ &m, long dim)
template<typename Int >
void	LatticeTester::mDualBasis (NTL::Mat< Int > &basisDual, const NTL::Mat< Int > &basis, const Int &m)
template<>
void	LatticeTester::mDualBasis (NTL::Mat< NTL::ZZ > &basisDual, const NTL::Mat< NTL::ZZ > &basis, const NTL::ZZ &m)
template<typename Int >
void	LatticeTester::projectMatrix (IntMat &out, const IntMat &in, const Coordinates &proj, long r)
	This function overwrites the first r rows of matrix 'out' by a matrix formed by the first r rows of the c columns of matrix in that are specified by proj, where ‘c = size(proj)’ is the cardinality of the projection proj.
template<typename Int , typename Real >
void	LatticeTester::projectionConstructionLLL (IntMat &projBasis, const IntMat &inBasis, const Coordinates &proj, const Int &m, const double delta, long r, RealVec *sqlen)
	Constructs a basis for the projection proj of the lattice with basis inBasis, using LLLBasisConstruction, and returns it in projBasis.
template<typename Int >
void	LatticeTester::projectionConstructionUpperTri (IntMat &projBasis, const IntMat &inBasis, IntMat &genTemp, const Coordinates &proj, const Int &m, long r)
	Same as projectionConstructionLLL, but the construction is made using upperTriangularBasis, so the returned basis is upper triangular.
template<typename Int >
void	LatticeTester::projectionConstructionUpperTri (IntMat &projBasis, const IntMat &inBasis, const Coordinates &proj, const Int &m, long r)
template<typename Int >
void	LatticeTester::projectionConstruction (IntMat &projBasis, const IntMat &inBasis, const Coordinates &proj, const Int &m, const ProjConstructType projType, const double delta)
	In this version, the construction method is passed as a parameter.

Detailed Description

Static functions to construct a basis from a set of generating vectors that are not necessarily independent, to construct a triangular basis, to construct the basis for a projection over a given subset of coordinates, and to obtain the \(m\)-dual of a given basis.

The algorithms are described in the Lattice Tester guide [iLEC26ltg]. The implementation relies on NTL and uses NTL matrices. When the basis turns out to have fewer rows than columns, most of the functions here add implicitly the rescaled unit vectors to the set of generating vectors. In that case, the basis matrix is always square and all the vectors of the form \(m \mathbf{e}_i\) belong to the lattice.

NTL already offers an efficient procedure to construct an LLL-reduced basis from a set of generating vectors. It is encapsulated in the LLLConstruction0 function given below. This function does not assume that the rescaled unit vectors \(m \mathbf{e}_i \) belong to the lattices and it does not even know about \(m\). The function LLLBasisConstruction adds those vectors to the set of generating vectors, so it always returns a square basis.

We also offer an alternative functions that construct a triangular basis from a set of generating vectors. These functions are usually faster. They always add the rescaled unit vectors implicitly to the set. The function lowerTriangularBasis constructs a lower-triangular basis, while upperTriangularBasis constructs an upper-triangular basis.

To compute the \(m\)-dual of a given basis, we have a general (but slow) function implemented in mDualBasis, and much faster functions in mDualLowerTriangular and mDualUpperTriangular that works only when the basis is triangular.

We also have functions to compute the basis of a projection of a given lattice over a specified set of coordinates. The function projectionConstructionLLL does this by using LLL to construct the basis of the projection, while projectionConstructionUpperTri constructs an upper-triangular basis for the projection. The function projectionConstruction takes the construction method as a parameter.

All functions take as input a IntMat object that contains either a basis or a set of generating vectors. By default, all rows and columns of this matrix object are used. But in most functions, the user can ask to use only a subset of these rows and columns, via the optional parameters r and c. This can permit one to use the same IntMat object for several numbers of dimensions, to avoid doing many object creations or resizing.

All functions in this file are static, so there is no notion of BasisConstruction object. We also avoid to create new objects (such as vectors and matrices) inside these functions. These functions can be called thousands or millions of times in a program, and we want the user to be able to re-use the same vectors and matrices over and over again instead of creating new ones.

Note that when one of these functions is used for an IntMat object that store the primal or \(m\)-dual basis inside an IntLattice object, only the primal or the \(m\)-dual basis is changed, and therefore the \(m\)-dual relationship will no longer hold after the call. The user must be aware of that. Most of the time, there is no need to reinstate this relationship, because for example if we want to compute a shortest nonzero vector is the \(m\)-dual lattice, then once we have an \(m\)-dual basis we no longer need a primal basis.

The programs TestBasisConstructSmall and TestBasisConstructSpeed in the examples illustrate how to use these functions and make speed comparisons.