My Project
Functions
cf_hnf.cc File Reference

HNF/LLL of NTL. More...

#include "config.h"
#include "canonicalform.h"
#include "cf_defs.h"
#include "cf_hnf.h"
#include "cf_util.h"
#include "NTLconvert.h"
#include <NTL/mat_ZZ.h>
#include <NTL/HNF.h>
#include <NTL/LLL.h>
#include "FLINTconvert.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 44 of file cf_hnf.cc.

45 {
46 #ifdef HAVE_FLINT
47  fmpz_mat_t FLINTM;
49  fmpz_mat_hnf(FLINTM,FLINTM);
51  fmpz_mat_clear(FLINTM);
52  return r;
53 #elif defined(HAVE_NTL)
54  mat_ZZ *AA=convertFacCFMatrix2NTLmat_ZZ(A);
55  ZZ DD=convertFacCF2NTLZZ(determinant(A,A.rows()));
56  mat_ZZ WW;
57  HNF(WW,*AA,DD);
58  delete AA;
60 #else
61  factoryError("NTL/FLINT missing: cf_HNF");
62  return NULL; // avoid warning
63 #endif
64 }
void convertFacCFMatrix2Fmpz_mat_t(fmpz_mat_t M, const CFMatrix &m)
conversion of a factory matrix over Z to a fmpz_mat_t
CFMatrix * convertFmpz_mat_t2FacCFMatrix(const fmpz_mat_t m)
conversion of a FLINT matrix over Z to a factory matrix
CFMatrix * convertNTLmat_ZZ2FacCFMatrix(const mat_ZZ &m)
Definition: NTLconvert.cc:1153
mat_ZZ * convertFacCFMatrix2NTLmat_ZZ(const CFMatrix &m)
Definition: NTLconvert.cc:1138
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
Definition: NTLconvert.cc:670
CanonicalForm FACTORY_PUBLIC determinant(const CFMatrix &M, int n)
Definition: cf_linsys.cc:222
VAR void(* factoryError)(const char *s)
Definition: cf_util.cc:80
#define NULL
Definition: omList.c:12
#define A
Definition: sirandom.c:24

◆ 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 or FLINT

Definition at line 66 of file cf_hnf.cc.

67 {
68 #ifdef HAVE_FLINT
69  fmpz_mat_t FLINTM;
71  fmpq_t delta,eta;
72  fmpq_init(delta); fmpq_set_si(delta,1,1);
73  fmpq_init(eta); fmpq_set_si(eta,3,4);
74  fmpz_mat_lll_storjohann(FLINTM,delta,eta);
76  fmpz_mat_clear(FLINTM);
77  return r;
78 #elif defined(HAVE_NTL)
79  mat_ZZ *AA=convertFacCFMatrix2NTLmat_ZZ(A);
80  ZZ det2;
81  LLL(det2,*AA,0L);
83  delete AA;
84  return r;
85 #else
86  factoryError("NTL/FLINT missing: cf_LLL");
87  return NULL; // avoid warning
88 #endif
89 }
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160