MatGSO< ZT, FT > Class Template Reference

#include <gso.h>

Public Member Functions
	MatGSO (Matrix< ZT > &arg_b, Matrix< ZT > &arg_u, Matrix< ZT > &arg_uinv_t, int flags)
virtual ZT &	sqnorm_coordinates (ZT &sqnorm, vector< ZT > coordinates)
virtual long	get_max_exp_of_b ()
virtual bool	b_row_is_zero (int i)
virtual int	get_cols_of_b () const
virtual int	get_rows_of_b () const
virtual void	negate_row_of_b (int i)
virtual void	create_rows (int n_new_rows)
virtual void	remove_last_rows (int n_removed_rows)
virtual void	move_row (int old_r, int new_r)
virtual void	row_addmul_we (int i, int j, const FT &x, long expo_add)
virtual void	row_add (int i, int j)
virtual void	row_sub (int i, int j)
virtual FT &	get_gram (FT &f, int i, int j)
virtual ZT &	get_int_gram (ZT &z, int i, int j)
virtual void	row_swap (int i, int j)
void	to_canonical (vector< FT > &w, const vector< FT > &v, long start=0)
void	from_canonical (vector< FT > &v, const vector< FT > &w, long start=0, long dimension=-1)
virtual void	babai (vector< ZT > &v, int start=0, int dimension=-1, bool gso=false)
virtual void	babai (vector< ZT > &w, const vector< FT > &v, int start=0, int dimension=-1, bool gso=false)
Public Member Functions inherited from MatGSOInterface< ZT, FT >
virtual	~MatGSOInterface ()
	MatGSOInterface (Matrix< ZT > &arg_u, Matrix< ZT > &arg_uinv_t, int flags)
virtual ZT &	sqnorm_coordinates (ZT &sqnorm, vector< ZT > coordinates)=0
virtual long	get_max_exp_of_b ()=0
virtual bool	b_row_is_zero (int i)=0
virtual int	get_cols_of_b () const =0
virtual int	get_rows_of_b () const =0
virtual void	negate_row_of_b (int i)=0
void	row_op_begin (int first, int last)
void	row_op_end (int first, int last)
virtual FT &	get_gram (FT &f, int i, int j)=0
virtual ZT &	get_int_gram (ZT &z, int i, int j)=0
const Matrix< FT > &	get_mu_matrix () const
const Matrix< FT > &	get_r_matrix () const
const Matrix< ZT > &	get_g_matrix () const
const FT &	get_mu_exp (int i, int j, long &expo) const
const FT &	get_mu_exp (int i, int j) const
FT &	get_mu (FT &f, int i, int j)
ZT	get_max_gram ()
FT	get_max_bstar ()
const FT &	get_r_exp (int i, int j, long &expo) const
const FT &	get_r_exp (int i, int j) const
FT &	get_r (FT &f, int i, int j)
long	get_max_mu_exp (int i, int n_columns)
bool	update_gso_row (int i, int last_j)
bool	update_gso_row (int i)
bool	update_gso ()
void	discover_all_rows ()
void	set_r (int i, int j, FT &f)
virtual void	move_row (int old_r, int new_r)=0
virtual void	row_addmul (int i, int j, const FT &x)
virtual void	row_addmul_we (int i, int j, const FT &x, long expo_add)=0
virtual void	row_add (int i, int j)=0
virtual void	row_sub (int i, int j)=0
void	lock_cols ()
void	unlock_cols ()
void	create_row ()
virtual void	create_rows (int n_new_rows)=0
void	remove_last_row ()
virtual void	remove_last_rows (int n_removed_rows)=0
void	apply_transform (const Matrix< FT > &transform, int src_base, int target_base)
void	apply_transform (const Matrix< FT > &transform, int src_base)
void	dump_mu_d (double *mu, int offset=0, int block_size=-1)
void	dump_mu_d (vector< double > mu, int offset=0, int block_size=-1)
void	dump_r_d (double *r, int offset=0, int block_size=-1)
void	dump_r_d (vector< double > &r, int offset=0, int block_size=-1)
double	get_current_slope (int start_row, int stop_row)
	Return slope of the curve fitted to the lengths of the vectors from start_row to stop_row. More...
FT	get_root_det (int start_row, int end_row)
	Return (squared) root determinant of the basis. More...
FT	get_log_det (int start_row, int end_row)
	Return log of the (squared) determinant of the basis. More...
FT	get_slide_potential (int start_row, int end_row, int block_size)
	Return slide potential of the basis. More...
void	print_mu_r_g (ostream &os)
virtual void	babai (vector< ZT > &v, int start=0, int dimension=-1)
virtual void	babai (vector< ZT > &w, const vector< FT > &v, int start=0, int dimension=1)
void	symmetrize_g ()
virtual void	row_swap (int i, int j)=0

Data Fields
Matrix< ZT > &	b
Matrix< ZT >	g
Data Fields inherited from MatGSOInterface< ZT, FT >
int	d
vector< long >	row_expo
const bool	enable_int_gram
const bool	enable_row_expo
const bool	enable_transform
const bool	enable_inverse_transform
const bool	row_op_force_long
Matrix< ZT > *	gptr

Additional Inherited Members
Protected Member Functions inherited from MatGSOInterface< ZT, FT >
virtual void	size_increased ()=0
virtual void	discover_row ()=0
void	invalidate_gso_row (int i, int new_valid_cols=0)
virtual void	update_bf (int i)=0
virtual void	invalidate_gram_row (int i)=0
virtual void	row_addmul_si (int i, int j, long x)=0
ZT &	sym_g (int i, int j)
Protected Attributes inherited from MatGSOInterface< ZT, FT >
Matrix< FT >	bf
Matrix< ZT > &	u
Matrix< ZT > &	u_inv_t
vector< int >	init_row_size
int	n_known_rows
int	n_source_rows
int	n_known_cols
bool	cols_locked
int	alloc_dim
Matrix< FT >	mu
Matrix< FT >	r
Matrix< FT >	gf
vector< int >	gso_valid_cols
FT	ftmp1
FT	ftmp2
ZT	ztmp1
ZT	ztmp2
vector< long >	tmp_col_expo

Detailed Description

template<class ZT, class FT>
class MatGSO< ZT, FT >

MatGSO provides an interface for performing elementary operations on a basis and computing its Gram matrix and its Gram-Schmidt orthogonalization. The Gram-Schmidt coefficients are computed on demand. The object keeps track of which coefficients are valid after each row operation.

Constructor & Destructor Documentation

MatGSO()

template<class ZT , class FT >

MatGSO< ZT, FT >::MatGSO ( Matrix< ZT > &  arg_b, Matrix< ZT > &  arg_u, Matrix< ZT > &  arg_uinv_t, int  flags  )

inline

Constructor. The precision of FT must be defined before creating an instance of the class and must remain the same until the object is destroyed (or no longer needed).

Parameters

b	The matrix on which row operations are performed. It must not be empty.
u	If u is not empty, operations on b are also done on u (in this case both must have the same number of rows). If u is initially the identity matrix, multiplying transform by the initial basis gives the current basis.
u_inv_t	Inverse transform (should be empty, which disables the computation, or initialized with identity matrix). It works only if u is not empty.
enable_int_gram	If true, coefficients of the Gram matrix are computed with exact integer arithmetic (type ZT). Otherwise, they are computed in floating-point (type FT). Note that when exact arithmetic is used, all coefficients of the first n_known_rows are continuously updated, whereas in floating-point, they are computed only on-demand. This option cannot be enabled if enable_row_expo=true.
enable_row_expo	If true, each row of b is normalized by a power of 2 before doing conversion to floating-point, which hopefully avoids some overflows. This option cannot be enabled if enable_int_gram=true and works only with FT=double and FT=long double. It is useless and MUST NOT be used for FT=dpe or FT=mpfr_t.
row_op_force_long	Affects the behaviour of row_addmul(_we). See the documentation of row_addmul.

Member Function Documentation

b_row_is_zero()

template<class ZT , class FT >

bool MatGSO< ZT, FT >::b_row_is_zero ( int  i )

inlinevirtual

Returns true if the ith row of b is zero. In the gram version it returns true if g(i,i) is zero.

Implements MatGSOInterface< ZT, FT >.

babai() [1/2]

template<class ZT , class FT >

void MatGSO< ZT, FT >::babai ( vector< ZT > &  v, int  start = 0, int  dimension = -1, bool  gso = false  )

virtual

Updatev to w s.t. ‖w⋅B - v‖ is small using Babai's nearest plane algorithm.

Parameters

v	a vector
start	only consider subbasis starting at start
dimension	only consider dimension vectors or all if -1
gso	if true then input v is considered to be expressed to B*

babai() [2/2]

template<class ZT , class FT >

void MatGSO< ZT, FT >::babai ( vector< ZT > &  w, const vector< FT > &  v, int  start = 0, int  dimension = -1, bool  gso = false  )

virtual

Return vector w s.t. ‖w⋅B - v‖ is small using Babai's nearest plane algorithm.

Parameters

w	a vector
v	a vector
start	only consider subbasis starting at start
dimension	only consider dimension vectors or all if -1
gso	if true then input v is considered to be expressed wrt B*

create_rows()

template<class ZT , class FT >

void MatGSO< ZT, FT >::create_rows ( int  n_new_rows )

inlinevirtual

Implements MatGSOInterface< ZT, FT >.

from_canonical()

template<class ZT , class FT >

void MatGSO< ZT, FT >::from_canonical	(	vector< FT > &	v,
		const vector< FT > &	w,
		long	start = 0,
		long	dimension = -1
	)

Given a vector w wrt the canonical basis ZZ^n return a vector v wrt the Gram-Schmidt basis B^*.

Parameters

v	a tuple-like object of dimension M.B.ncols
start	only consider subbasis starting at start
dimension	only consider dimension vectors or all if -1

get_cols_of_b()

template<class ZT , class FT >

int MatGSO< ZT, FT >::get_cols_of_b ( ) const

inlinevirtual

Returns number of columns of b. In the gram version it returns the number of columns of g.

Implements MatGSOInterface< ZT, FT >.

get_gram()

template<class ZT , class FT >

FT & MatGSO< ZT, FT >::get_gram ( FT &  f, int  i, int  j  )

inlinevirtual

Returns Gram matrix coefficients (0 <= i < n_known_rows and 0 <= j <= i). If enable_row_expo=false, returns the dot product (b[i], b[j]). If enable_row_expo=true, returns (b[i], b[j]) / 2 ^ (row_expo[i] + row_expo[j]).

Returns reference to f.

Implements MatGSOInterface< ZT, FT >.

get_int_gram()

template<class ZT , class FT >

ZT & MatGSO< ZT, FT >::get_int_gram ( ZT &  z, int  i, int  j  )

inlinevirtual

Returns integer Gram matrix coefficients (0 <= i < n_known_rows and 0 <= j <= i). If (enable_int_gram = true), it returns the i,j-th coordinate of the Gram matrix else it computes the inner product of b_i and b_j Returns reference to z.

Implements MatGSOInterface< ZT, FT >.

get_max_exp_of_b()

template<class ZT , class FT >

long MatGSO< ZT, FT >::get_max_exp_of_b ( )

inlinevirtual

Returns maximum exponent of b. In the gram version it returns a half times the maximum exponent of g.

Implements MatGSOInterface< ZT, FT >.

get_rows_of_b()

template<class ZT , class FT >

int MatGSO< ZT, FT >::get_rows_of_b ( ) const

inlinevirtual

Returns number of rows of b. In the gram version it returns the number of of rows of g. This function is made to reduce code repetition (dump_mu/dump_r)

Implements MatGSOInterface< ZT, FT >.

move_row()

template<class ZT , class FT >

void MatGSO< ZT, FT >::move_row ( int  old_r, int  new_r  )

virtual

Row old_r becomes row new_r and intermediate rows are shifted. If new_r < old_r, then old_r must be < n_known_rows.

Implements MatGSOInterface< ZT, FT >.

negate_row_of_b()

template<class ZT , class FT >

void MatGSO< ZT, FT >::negate_row_of_b ( int  i )

inlinevirtual

Negates the ith row of b. Needed by dbkz_postprocessing.

Implements MatGSOInterface< ZT, FT >.

remove_last_rows()

template<class ZT , class FT >

void MatGSO< ZT, FT >::remove_last_rows ( int  n_removed_rows )

inlinevirtual

Implements MatGSOInterface< ZT, FT >.

row_add()

template<class ZT , class FT >

void MatGSO< ZT, FT >::row_add ( int  i, int  j  )

virtual

Implements MatGSOInterface< ZT, FT >.

row_addmul_we()

template<class ZT , class FT >

void MatGSO< ZT, FT >::row_addmul_we ( int  i, int  j, const FT &  x, long  expo_add  )

virtual

b[i] := b[i] + x * b[j]. After one or several calls to row_addmul, row_op_end must be called. Special cases |x| <= 1 and |x| <= LONG_MAX are optimized. x should be an integer. If row_op_force_long=true, x is always converted to (2^expo * long) instead of (2^expo * ZT), which is faster if ZT=mpz_t but might lead to a loss of precision (in LLL, more Babai iterations are needed). b[i] := b[i] + x * 2^expo_add * b[j]. After one or several calls to row_addmul_we, row_op_end must be called. Special cases |x| <= 1 and |x| <= LONG_MAX are optimized. x should be an integer. If row_op_force_long=true, x is always converted to (2^expo * long) instead of (2^expo * ZT), which is faster if ZT=mpz_t but might lead to a loss of precision (in LLL, more Babai iterations are needed).

Implements MatGSOInterface< ZT, FT >.

row_sub()

template<class ZT , class FT >

void MatGSO< ZT, FT >::row_sub ( int  i, int  j  )

virtual

Implements MatGSOInterface< ZT, FT >.

row_swap()

template<class ZT , class FT >

void MatGSO< ZT, FT >::row_swap ( int  i, int  j  )

virtual

Implements MatGSOInterface< ZT, FT >.

sqnorm_coordinates()

template<class ZT , class FT >

ZT & MatGSO< ZT, FT >::sqnorm_coordinates ( ZT &  sqnorm, vector< ZT >  coordinates  )

inlinevirtual

Basis of the lattice The next five functions make calls from lll.cpp and bkz.cpp indirect. Returns || sum_i x_i b_i ||^2 on vectorial input (x_i)_i in the Gram version, it returns x^T G x

Implements MatGSOInterface< ZT, FT >.

to_canonical()

template<class ZT , class FT >

void MatGSO< ZT, FT >::to_canonical	(	vector< FT > &	w,
		const vector< FT > &	v,
		long	start = 0
	)

Given a vector v wrt the Gram-Schmidt basis B^* return a vector w wrt the canonical basis ZZ^n, i.e. solve w = v⋅B^*.

Parameters

v	a tuple-like object of dimension M.d
start	only consider subbasis starting at start

Field Documentation

b

template<class ZT , class FT >

Matrix<ZT>& MatGSO< ZT, FT >::b

Basis of the lattice

g

template<class ZT , class FT >

Matrix<ZT> MatGSO< ZT, FT >::g

Integer Gram matrix of the lattice

---

The documentation for this class was generated from the following files:

• fplll/gso.h
• fplll/gso.cpp