eg_dbasis_red.h File Reference

Detailed Description

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.

Definition in file eg_dbasis_red.h.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <float.h>
#include "eg_macros.h"
#include "eg_mem.h"
#include "eg_lpnum.h"
#include "eg_dmatrix.h"
#include "eg_numutil.h"

Include dependency graph for eg_dbasis_red.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

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.

Generated on Mon Jan 30 08:49:43 2006 for EGlib by  doxygen 1.4.5