Functions
cf_hnf.cc File Reference

HNF/LLL of NTL. More...

#include "config.h"
#include "NTLconvert.h"
#include "canonicalform.h"
#include "cf_defs.h"
#include "cf_hnf.h"
#include <NTL/mat_ZZ.h>
#include <NTL/HNF.h>
#include <NTL/LLL.h>

Go to the source code of this file.

Functions

CFMatrixcf_HNF (CFMatrix &A)
 The input matrix A is an n x m matrix of rank m (so n >= m), and D is a multiple of the determinant of the lattice L spanned by the rows of A. More...
 
CFMatrixcf_LLL (CFMatrix &A)
 performs LLL reduction. More...
 

Detailed Description

HNF/LLL of NTL.

Header file: cf_hnf.h

Definition in file cf_hnf.cc.

Function Documentation

◆ cf_HNF()

CFMatrix* cf_HNF ( CFMatrix A)

The input matrix A is an n x m matrix of rank m (so n >= m), and D is a multiple of the determinant of the lattice L spanned by the rows of A.

The input matrix A is square matrix of integers output: the Hermite Normal Form of A; that is, the unique m x m matrix whose rows span L, such that.

W is computed as the Hermite Normal Form of A; that is, W is the unique m x m matrix whose rows span L, such that

  • W is lower triangular,
  • the diagonal entries are positive,
  • any entry below the diagonal is a non-negative number strictly less than the diagonal entry in its column.

Definition at line 38 of file cf_hnf.cc.

39 {
40  mat_ZZ *AA=convertFacCFMatrix2NTLmat_ZZ(A);
41  ZZ DD=convertFacCF2NTLZZ(determinant(A,A.rows()));
42  mat_ZZ WW;
43  HNF(WW,*AA,DD);
44  delete AA;
46 }
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
Definition: NTLconvert.cc:664
int rows() const
Definition: ftmpl_matrix.h:43
mat_ZZ * convertFacCFMatrix2NTLmat_ZZ(const CFMatrix &m)
Definition: NTLconvert.cc:1137
CanonicalForm determinant(const CFMatrix &M, int n)
Definition: cf_linsys.cc:222
CFMatrix * convertNTLmat_ZZ2FacCFMatrix(const mat_ZZ &m)
Definition: NTLconvert.cc:1152

◆ cf_LLL()

CFMatrix* cf_LLL ( CFMatrix A)

performs LLL reduction.

B is an m x n matrix, viewed as m rows of n-vectors. m may be less than, equal to, or greater than n, and the rows need not be linearly independent. B is transformed into an LLL-reduced basis, and the return value is the rank r of B. The first m-r rows of B are zero.

More specifically, elementary row transformations are performed on B so that the non-zero rows of new-B form an LLL-reduced basis for the lattice spanned by the rows of old-B. The default reduction parameter is delta=3/4, which means that the squared length of the first non-zero basis vector is no more than 2^{r-1} times that of the shortest vector in the lattice.

Note
: uses NTL

Definition at line 48 of file cf_hnf.cc.

49 {
50  mat_ZZ *AA=convertFacCFMatrix2NTLmat_ZZ(A);
51  #if 0
52  LLL_RR(*AA);
53  #else
54  ZZ det2;
55  LLL(det2,*AA,0L);
56  #endif
58  delete AA;
59  return r;
60 }
mat_ZZ * convertFacCFMatrix2NTLmat_ZZ(const CFMatrix &m)
Definition: NTLconvert.cc:1137
CFMatrix * convertNTLmat_ZZ2FacCFMatrix(const mat_ZZ &m)
Definition: NTLconvert.cc:1152