Data Structures | Files | Defines | Typedefs | Functions | Variables

LLL Basis Reduction

Data Structures

struct  EGdBsRed_t
 structure to hold all necesary data to perform the LLL's basis reduction algorithm. More...

Files

file  eg_dbasis_red.c
file  eg_dbasis_red.h
 

This file provide the user interface and function definitions for the so-called LLL Basis Reduction Algorithm. This algorithm was first presented in the paper "Factoring polynomials with rational coefficients", Mathematische Annalen 261 (1981), p515-534. and has been extensivelly studied elsewere. for more details just Google-it.


Defines

#define EG_DBSRED_ALPHA   0x7ffffp-20
 Value used in condition two of the LLL algorithm, remember that this number should be between $(1/4,1)$. By default we choose $\lambda = \frac{2^{20}-1}{2^{20}} \approx .99999904632568359375 $.
#define EG_DBSRED_VERBOSE   0
 verbosity level
#define EGdBsRedAddElement(__bsred, __new_elem)
 add a new vector to the basis.
#define EGdBsRedClear(__bsred)
 Free any internally allocated memory in a EGdBsRed_t structure.
#define EGdBsRedInit(__bsred)
 Initialize an EGdBsRed_t structure, as a basis with zero elements of dimension zero.
#define EGdBsRedReset(__bsred)   ((__bsred)->dim = 0)
 reset an EGdBsRed_t structure as a basis without elements (note that we do not reset the length of the vectors, just the number of vectors in the basis).
#define EGdBsRedSetLength(__bsred, __new_length)   ((__bsred)->length = (__new_length))
 set the length of the vectors used in the basis for an EGdBsRed_t structure.

Typedefs

typedef struct EGdBsRed_t EGdBsRed_t
 structure to hold all necesary data to perform the LLL's basis reduction algorithm.

Functions

int EGdBsRed (EGdBsRed_t *const __bsred, unsigned *const dim, const EGlpNum_t zero_tol, int *const status)
 This function performs the so-called LLL basis reduction algorithm.
static void EGdBsRedBuildGM (EGdMatrix_t *const GM, const size_t full_dim, const size_t length, EGlpNum_t **const basis, EGlpNum_t orilen, EGlpNum_t tmpval)
 , build (from scratch) the GM matrix

Variables

uintmax_t EGdBsRedStats [10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
 where to hold the profile information

Profiling structures and functions for the basis reduction algorithm.



uintmax_t EGdBsRedStats [10]
 where to hold the profile information
#define EG_BSRED_CALLS   0
 where we store the number of calls to EGdBsRed
#define EG_BSRED_SZRED   1
 where we store the total number of size reductions performed in EGdBsRed
#define EG_BSRED_INTR   2
 where we store the total number of interchanges performed in EGdBsRed
#define EG_BSRED_ITT   3
 where we store the total number of innermost loops performed in EGdBsRed
#define EGdBsRedProfile(__ofile)
 Print into the given file stream, the current statistics related to the EGdBsRed algorithm. And reset all counters to zero.

Detailed Description

Here we define a common interface for dense matrices (i.e. a structure), and some common operations over dense matrices. The definition uses EGlpNum as reference number type, this allow for template initializations.

History:
Revision 0.0.2
  • 2005-10-28
    • First implementation.

Define Documentation

#define EG_BSRED_CALLS   0

where we store the number of calls to EGdBsRed

Definition at line 62 of file eg_dbasis_red.h.

#define EG_BSRED_INTR   2

where we store the total number of interchanges performed in EGdBsRed

Definition at line 72 of file eg_dbasis_red.h.

#define EG_BSRED_ITT   3

where we store the total number of innermost loops performed in EGdBsRed

Definition at line 77 of file eg_dbasis_red.h.

#define EG_BSRED_SZRED   1

where we store the total number of size reductions performed in EGdBsRed

Definition at line 67 of file eg_dbasis_red.h.

#define EG_DBSRED_ALPHA   0x7ffffp-20

Value used in condition two of the LLL algorithm, remember that this number should be between $(1/4,1)$. By default we choose $\lambda = \frac{2^{20}-1}{2^{20}} \approx .99999904632568359375 $.

Definition at line 97 of file eg_dbasis_red.h.

#define EG_DBSRED_VERBOSE   0

verbosity level

Definition at line 50 of file eg_dbasis_red.h.

#define EGdBsRedAddElement (   __bsred,
  __new_elem 
)
Value:
do{\
  EGdBsRed_t*const __EGdbs = (__bsred);\
  if(__EGdbs->basis_sz <= __EGdbs->dim){\
    __EGdbs->basis_sz += 10U;\
    EGrealloc(__EGdbs->basis,sizeof(EGlpNum_t*)*__EGdbs->basis_sz);}\
  __EGdbs->basis[__EGdbs->dim++] = (__new_elem);} while(0)

add a new vector to the basis.

Parameters:
__bsred pointer to an EGdBsRed_t structure.
__new_elem new vector to add to the basis.
Examples:
eg_dmatrix.ex.c.

Definition at line 159 of file eg_dbasis_red.h.

Referenced by main().

#define EGdBsRedClear (   __bsred  ) 
Value:
do{\
  EGdBsRed_t*const __EGdbs = (__bsred);\
  if(__EGdbs->basis) EGfree(__EGdbs->basis);\
  EGdMatrixClear(&(__EGdbs->GM));} while(0)

Free any internally allocated memory in a EGdBsRed_t structure.

Parameters:
__bsred pointer to an EGdBsRed_t structure.
Examples:
eg_dmatrix.ex.c.

Definition at line 133 of file eg_dbasis_red.h.

Referenced by main().

#define EGdBsRedInit (   __bsred  ) 
Value:
do{\
  EGdBsRed_t*const __EGdbs = (__bsred);\
  memset(__EGdbs,0,sizeof(EGdBsRed_t));\
  EGdMatrixInit(&(__EGdbs->GM));} while(0)

Initialize an EGdBsRed_t structure, as a basis with zero elements of dimension zero.

Parameters:
__bsred pointer to an EGdBsRed_t structure.
Examples:
eg_dmatrix.ex.c.

Definition at line 124 of file eg_dbasis_red.h.

Referenced by main().

#define EGdBsRedProfile (   __ofile  ) 
Value:
do{\
  fprintf(__ofile,"LLL Basis Reduction Statistics:\n");\
  fprintf(__ofile,"\tNumber Calls    : %ju\n", EGdBsRedStats[EG_BSRED_CALLS]);\
  fprintf(__ofile,"\tLoops           : %ju\n", EGdBsRedStats[EG_BSRED_ITT]);\
  fprintf(__ofile,"\tSize Reductions : %ju\n", EGdBsRedStats[EG_BSRED_SZRED]);\
  fprintf(__ofile,"\tInterchanges    : %ju\n", EGdBsRedStats[EG_BSRED_INTR]);\
  memset(EGdBsRedStats,0,sizeof(EGdBsRedStats));} while(0)

Print into the given file stream, the current statistics related to the EGdBsRed algorithm. And reset all counters to zero.

Parameters:
__ofile where we want to print the profile information.
Examples:
eg_dmatrix.ex.c.

Definition at line 83 of file eg_dbasis_red.h.

Referenced by main().

#define EGdBsRedReset (   __bsred  )     ((__bsred)->dim = 0)

reset an EGdBsRed_t structure as a basis without elements (note that we do not reset the length of the vectors, just the number of vectors in the basis).

Parameters:
__bsred pointer to an EGdBsRed_t structure.

Definition at line 144 of file eg_dbasis_red.h.

#define EGdBsRedSetLength (   __bsred,
  __new_length 
)    ((__bsred)->length = (__new_length))

set the length of the vectors used in the basis for an EGdBsRed_t structure.

Parameters:
__bsred pointer to an EGdBsRed_t structure.
__new_length length of the vectors in the basis.
Examples:
eg_dmatrix.ex.c.

Definition at line 152 of file eg_dbasis_red.h.

Referenced by main().

Typedef Documentation

typedef struct EGdBsRed_t EGdBsRed_t

structure to hold all necesary data to perform the LLL's basis reduction algorithm.

Function Documentation

int EGdBsRed ( EGdBsRed_t *const   __bsred,
unsigned *const   dim,
const EGlpNum_t  zero_tol,
int *const   status 
)

This function performs the so-called LLL basis reduction algorithm.

Parameters:
__bsred pointer to an EGdBsRed_t structure.
status where we return the status of the algorithm, if the algorithm finish with non-zero reduced elements, the status is EG_ALGSTAT_SUCCESS. if the algorithm finish with some zero reduced vector, the status is EG_ALGSTAT_PARTIAL. if the algorithm stop because of numerical problems, the status is EG_ALGSTAT_NUMERROR.
zero_tol threshold for a number to be considered as zero.
dim pointer to a number where we return the dimension of the basis that the algorithm could prove before running in any numerical problem. If the algorithm stop with status EG_ALGSTAT_SUCCESS, then this number should be equal to EGdBsRed_t::dim. The vectors that we finish reducing are stored in EGdMatrix_t::row_ord[0], ... , EGdMatrix_t::row_ord[dim], in the EGdBsRed_t::GM matrix.
Returns:
zero if the algorithm finish, non-zero if an unforeseen error occure during execution.
Details:
The implementation that we use introduce (as an heuristic step) the sorting of the original basis vectors in increasing order according to their norms, this simple step reduced the total running time of the algorithm, but does not improve the theoretical running time. A second detail is that we only compute the Gram-Schmidth coefficients only once (at the beggining of the program), and then, we only update the changed entries for both operations size reduction and interchange. The advantage of the approach is that we save most Gram-Schmidth computations and also all the recomputations of the inner products of the elements currently in the basis. Again, this are improvements form the practical point of view, but not in practice. The dissadvantage of this approach is that we do accumulate rounding errors in the Gram-Schmidth coefficients allong the way, but if all original vectors coefficients where integer (and not too big), then the error should not grow too much. Still this may happen if the input basis is ill conditioned.
Examples:
eg_dmatrix.ex.c.

Referenced by main().

static void EGdBsRedBuildGM ( EGdMatrix_t *const   GM,
const size_t  full_dim,
const size_t  length,
EGlpNum_t **const   basis,
EGlpNum_t  orilen,
EGlpNum_t  tmpval 
) [static]

, build (from scratch) the GM matrix

Definition at line 30 of file eg_dbasis_red.c.

References EGdMatrix_t::col_ord, EGlpNumInnProd, EGutilPermSort(), EGdMatrix_t::matrow, and EGdMatrix_t::row_ord.

Here is the call graph for this function:

Variable Documentation

uintmax_t EGdBsRedStats[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

where to hold the profile information

Definition at line 26 of file eg_dbasis_red.c.

uintmax_t EGdBsRedStats[10]

where to hold the profile information

Definition at line 26 of file eg_dbasis_red.c.

Generated on Thu Mar 29 2012 10:10:22 for EGlib by  doxygen 1.7.1