LLL Basis Reduction

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.

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.

Data Structures

struct EGdBsRed_t

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

Profiling structures and functions for the basis reduction algorithm.

#define EG_BSRED_CALLS   0

where we store the number of calls to 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 EG_BSRED_SZRED   1

where we store the total number of size reductions 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.

uintmax_t EGdBsRedStats [10]

where to hold the profile information

Defines

#define EG_DBSRED_ALPHA   0x3ffp-10

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 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, 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 unsigned full_dim, const unsigned 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

Define Documentation

#define EG_BSRED_CALLS 0

where we store the number of calls to EGdBsRed

Definition at line 67 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 77 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 82 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 72 of file eg_dbasis_red.h.

#define EG_DBSRED_ALPHA 0x3ffp-10

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 102 of file eg_dbasis_red.h.

#define EG_DBSRED_VERBOSE 0

verbosity level

Definition at line 55 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 164 of file eg_dbasis_red.h.

#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 138 of file eg_dbasis_red.h.

#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 129 of file eg_dbasis_red.h.

#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 88 of file eg_dbasis_red.h.

#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 149 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 157 of file eg_dbasis_red.h.

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,

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.

Definition at line 66 of file eg_dbasis_red.c.
Here is the call graph for this function:

static void EGdBsRedBuildGM ( EGdMatrix_t *const GM,

const unsigned full_dim,

const unsigned 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.
Here is the call graph for this function:

Variable Documentation

uintmax_t EGdBsRedStats[10]

where to hold the profile information

Definition at line 26 of file eg_dbasis_red.c.

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.

Generated on Mon Jan 30 08:55:27 2006 for EGlib by

1.4.5


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.
Data Structures
struct	EGdBsRed_t
	structure to hold all necesary data to perform the LLL's basis reduction algorithm. More...
Profiling structures and functions for the basis reduction algorithm.
#define	EG_BSRED_CALLS 0
	where we store the number of calls to 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	EG_BSRED_SZRED 1
	where we store the total number of size reductions 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.
uintmax_t	EGdBsRedStats [10]
	where to hold the profile information
Defines
#define	EG_DBSRED_ALPHA 0x3ffp-10
	Value used in condition two of the LLL algorithm, remember that this number should be between . 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 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, 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 unsigned full_dim, const unsigned 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