#include <gso_interface.h>
Public Member Functions | |
| 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 | |
| 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 |
Protected Member Functions | |
| 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 | |
| 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
class MatGSOInterface< ZT, FT >
MatGSOInterface 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
◆ ~MatGSOInterface()
|
inlinevirtual |
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. In other words, u will contain the transformation matrix used on the basis b that was used to obtain 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.
◆ MatGSOInterface()
|
inline |
Member Function Documentation
◆ apply_transform() [1/2]
|
inline |
◆ apply_transform() [2/2]
| void MatGSOInterface< ZT, FT >::apply_transform | ( | const Matrix< FT > & | transform, |
| int | src_base, | ||
| int | target_base | ||
| ) |
Executes transformation by creating extra rows, Calculating new entries, swapping the new rows with previous ones, And then removing the excess rows
◆ b_row_is_zero()
|
pure virtual |
Returns true if the ith row of b is zero. In the gram version it returns true if g(i,i) is zero.
Implemented in MatGSO< ZT, FT >, and MatGSOGram< ZT, FT >.
◆ babai() [1/2]
|
virtual |
Updatev to w s.t. ‖w⋅B - v⋅B^*‖ is small using Babai's nearest plane algorithm.
- Parameters
-
v a vector, both input and output start only consider subbasis starting at start dimension only consider dimension vectors or all if -1
◆ babai() [2/2]
|
virtual |
Return vector w s.t. ‖w⋅B - v⋅B^*‖ 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
◆ create_row()
|
inline |
Adds a zero row to b (and to u if enableTranform=true). One or several operations can be performed on this row with row_addmul(_we), then row_op_end must be called. Do not use if enable_inverse_transform=true.
◆ create_rows()
|
pure virtual |
Implemented in MatGSO< ZT, FT >, and MatGSOGram< ZT, FT >.
◆ discover_all_rows()
|
inline |
Allows row_addmul(_we) for all rows even if the GSO has never been computed.
◆ discover_row()
|
protectedpure virtual |
◆ dump_mu_d() [1/2]
|
inline |
Dump mu matrix to parameter mu.
When a double pointer is provided the caller must ensure it can hold block_size^2 entries. When a vector is provided new entries are pushed to the end. In particular, existing entries are not overwritten or cleared.
- Note
- No row discovery or update is performed prior to dumping the matrix.
◆ dump_mu_d() [2/2]
|
inline |
◆ dump_r_d() [1/2]
|
inline |
Dump r vector to parameter r.
When a double pointer is provided the caller must ensure it can hold block_size entries. When a vector is provided new entries are pushed to the end. In particular, existing entries are not overwritten or cleared.
- Note
- No row discovery or update is performed prior to dumping the matrix.
◆ dump_r_d() [2/2]
|
inline |
◆ get_cols_of_b()
|
pure virtual |
Returns number of columns of b. In the gram version it returns the number of columns of g.
Implemented in MatGSO< ZT, FT >, and MatGSOGram< ZT, FT >.
◆ get_current_slope()
| double MatGSOInterface< ZT, FT >::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.
The slope gives an indication of the quality of the basis.
- Parameters
-
start_row start row (inclusive) stop_row stop row (exclusive)
- Returns
◆ get_g_matrix()
|
inline |
Returns the g matrix (Z_NR version of r) Coefficients of the Gram Schmidt Orthogonalization (lower triangular matrix)
◆ get_gram()
|
pure virtual |
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.
Implemented in MatGSO< ZT, FT >, and MatGSOGram< ZT, FT >.
◆ get_int_gram()
|
pure virtual |
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.
Implemented in MatGSO< ZT, FT >, and MatGSOGram< ZT, FT >.
◆ get_log_det()
| FT MatGSOInterface< ZT, FT >::get_log_det | ( | int | start_row, |
| int | end_row | ||
| ) |
Return log of the (squared) determinant of the basis.
- Parameters
-
start_row start row (inclusive) end_row stop row (exclusive)
◆ get_max_bstar()
|
inline |
Return maximum bstar_i for all i
◆ get_max_exp_of_b()
|
pure virtual |
Returns maximum exponent of b. In the gram version it returns a half times the maximum exponent of g.
Implemented in MatGSO< ZT, FT >, and MatGSOGram< ZT, FT >.
◆ get_max_gram()
|
inline |
Return maximum bstar_i for all i
◆ get_max_mu_exp()
| long MatGSOInterface< ZT, FT >::get_max_mu_exp | ( | int | i, |
| int | n_columns | ||
| ) |
Returns expo such that mu(i, j) < 2^expo for all j < n_columns. It is assumed that mu(i, j) is valid for all j < n_columns.
◆ get_mu()
|
inline |
Returns f = (b_i, b*_j) / ||b*_j||^2.
Returns reference to f.
◆ get_mu_exp() [1/2]
|
inline |
◆ get_mu_exp() [2/2]
|
inline |
Returns f = mu(i, j) and expo such that f * 2^expo = (b_i, b*_j) / ||b*_j||^2. If enable_row_expo=false, expo is always 0. If enable_row_expo=true, expo = row_expo[i] - row_expo[j] It is assumed that mu(i, j) is valid. The returned value is a reference to the coefficient of the internal matrix, which may change if the matrix is modified.
◆ get_mu_matrix()
|
inline |
Returns the mu matrix Coefficients of the Gram Schmidt Orthogonalization (lower triangular matrix) mu(i, j) = r(i, j) / ||b*_j||^2.
◆ get_r()
|
inline |
Returns f = (b_i, b*_j).
Returns reference to f.
◆ get_r_exp() [1/2]
|
inline |
◆ get_r_exp() [2/2]
|
inline |
Returns f = r(i, j) and expo such that (b_i, b*_j) = f * 2^expo. If enable_row_expo=false, expo is always 0. If enable_row_expo=true, expo = row_expo[i] + row_expo[j] If is assumed that r(i, j) is valid. The returned value is a reference to the coefficient of the internal matrix, which may change if the matrix is modified
◆ get_r_matrix()
|
inline |
Returns the r matrix Coefficients of the Gram Schmidt Orthogonalization (lower triangular matrix)
◆ get_root_det()
| FT MatGSOInterface< ZT, FT >::get_root_det | ( | int | start_row, |
| int | end_row | ||
| ) |
Return (squared) root determinant of the basis.
- Parameters
-
start_row start row (inclusive) end_row stop row (exclusive)
◆ get_rows_of_b()
|
pure virtual |
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)
Implemented in MatGSO< ZT, FT >, and MatGSOGram< ZT, FT >.
◆ get_slide_potential()
| FT MatGSOInterface< ZT, FT >::get_slide_potential | ( | int | start_row, |
| int | end_row, | ||
| int | block_size | ||
| ) |
Return slide potential of the basis.
- Parameters
-
start_row start row (inclusive) end_row stop row (exclusive) block_size block size
◆ invalidate_gram_row()
|
protectedpure virtual |
◆ invalidate_gso_row()
|
inlineprotected |
◆ lock_cols()
| void MatGSOInterface< ZT, FT >::lock_cols |
Early reduction Allowed when enable_int_gram=false, n_known_cols large enough to compute all the g(i,j)
◆ move_row()
|
pure 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.
Implemented in MatGSO< ZT, FT >, and MatGSOGram< ZT, FT >.
◆ negate_row_of_b()
|
pure virtual |
Negates the ith row of b. Needed by dbkz_postprocessing.
Implemented in MatGSO< ZT, FT >, and MatGSOGram< ZT, FT >.
◆ print_mu_r_g()
|
inline |
Prints mu,r and g matrix to ostream os.
◆ remove_last_row()
|
inline |
Removes the last row of b (and of u if enable_transform=true). Do not use if enable_inverse_transform=true.
◆ remove_last_rows()
|
pure virtual |
Implemented in MatGSO< ZT, FT >, and MatGSOGram< ZT, FT >.
◆ row_add()
|
pure virtual |
Implemented in MatGSO< ZT, FT >, and MatGSOGram< ZT, FT >.
◆ row_addmul()
|
inlinevirtual |
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).
◆ row_addmul_si()
|
protectedpure virtual |
◆ row_addmul_we()
|
pure virtual |
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).
Implemented in MatGSO< ZT, FT >, and MatGSOGram< ZT, FT >.
◆ row_op_begin()
|
inline |
Must be called before a sequence of row_addmul(_we).
◆ row_op_end()
| void MatGSOInterface< ZT, FT >::row_op_end | ( | int | first, |
| int | last | ||
| ) |
Must be called after a sequence of row_addmul(_we). This invalidates the i-th line of the GSO.
◆ row_sub()
|
pure virtual |
Implemented in MatGSO< ZT, FT >, and MatGSOGram< ZT, FT >.
◆ row_swap()
|
pure virtual |
Implemented in MatGSO< ZT, FT >, and MatGSOGram< ZT, FT >.
◆ set_r()
|
inline |
Sets the value of r(i, j). During the execution of LLL, some coefficients are computed by the algorithm. They are set directly to avoid double computation.
◆ size_increased()
|
protectedpure virtual |
Allocates matrices and arrays whose size depends on d (all but tmp_col_expo). When enable_int_gram=false, initializes bf.
◆ sqnorm_coordinates()
|
pure virtual |
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
Implemented in MatGSO< ZT, FT >, and MatGSOGram< ZT, FT >.
◆ sym_g()
|
inlineprotected |
◆ symmetrize_g()
|
inline |
◆ unlock_cols()
| void MatGSOInterface< ZT, FT >::unlock_cols |
◆ update_bf()
|
protectedpure virtual |
◆ update_gso()
|
inline |
Updates all GSO coefficients (mu and r).
◆ update_gso_row() [1/2]
|
inline |
Updates r(i, j) and mu(i, j) if needed for all j. All coefficients of r and mu above the i-th row in columns [0, min(last_j, i - 1)] must be valid. If i=n_known_rows, n_known_rows is increased by one.
◆ update_gso_row() [2/2]
| bool MatGSOInterface< ZT, FT >::update_gso_row | ( | int | i, |
| int | last_j | ||
| ) |
Updates r(i, j) and mu(i, j) if needed for all j in [0, last_j]. All coefficients of r and mu above the i-th row in columns [0, min(last_j, i - 1)] must be valid. If i=n_known_rows, n_known_rows is increased by one.
Field Documentation
◆ alloc_dim
|
protected |
◆ bf
|
protected |
◆ cols_locked
|
protected |
◆ d
| int MatGSOInterface< ZT, FT >::d |
Number of rows of b (dimension of the lattice). Can be changed with create_row or remove_last_row.
◆ enable_int_gram
| const bool MatGSOInterface< ZT, FT >::enable_int_gram |
Exact computation of dot products (i.e. with type ZT instead of FT)
◆ enable_inverse_transform
| const bool MatGSOInterface< ZT, FT >::enable_inverse_transform |
Computation of the inverse transform matrix (transposed). This works only if enable_transform=true. This matrix has very large coefficients, computing it is slow.
◆ enable_row_expo
| const bool MatGSOInterface< ZT, FT >::enable_row_expo |
Normalization of each row of b by a power of 2.
◆ enable_transform
| const bool MatGSOInterface< ZT, FT >::enable_transform |
Computation of the transform matrix.
◆ ftmp1
|
protected |
◆ ftmp2
|
protected |
◆ gf
|
protected |
◆ gptr
| Matrix<ZT>* MatGSOInterface< ZT, FT >::gptr |
Replaced the gram matrix by a pointer. In the gso-class there is also a matrix g, and in the constructor gptr is defined to be equal to &g. In the ggso-class a gram matrix is given (arg_g), and gptr is defined as &arg_g.
◆ gso_valid_cols
|
protected |
◆ init_row_size
|
protected |
◆ mu
|
protected |
Coefficients of the Gram-Schmidt orthogonalization (lower triangular matrix).
If enable_row_expo=false, mu(i, j) = (b_i, b*_j) / ||b*_j||^2. If enable_row_expo=true, mu(i, j) = (b_i, b*_j) / ||b*_j||^2 / 2 ^ (row_expo[i] - row_expo[j]).
mu(i, j) is valid if 0 <= i < n_known_rows (<= d) and 0 <= j < min(gso_valid_cols[i], i)
◆ n_known_cols
|
protected |
◆ n_known_rows
|
protected |
◆ n_source_rows
|
protected |
◆ r
|
protected |
Coefficients of the Gram-Schmidt orthogonalization (lower triangular matrix).
If enable_row_expo=false, r(i, j) = (b_i, b*_j). If enable_row_expo=true, r(i, j) = (b_i, b*_j) / 2 ^ (row_expo[i] + row_expo[j]).
r(i, j) is valid if 0 <= i < n_known_rows (<= d) and 0 <= j < gso_valid_cols[i] (<= i + 1).
◆ row_expo
| vector<long> MatGSOInterface< ZT, FT >::row_expo |
When enable_row_expo=true, row_expo[i] is the smallest non-negative integer such that b(i, j) <= 2^row_expo[i] for all j. Otherwise this array is empty.
◆ row_op_force_long
| const bool MatGSOInterface< ZT, FT >::row_op_force_long |
Changes the behaviour of row_addmul(_we). See the description of row_addmul.
◆ tmp_col_expo
|
protected |
◆ u
|
protected |
◆ u_inv_t
|
protected |
◆ ztmp1
|
protected |
◆ ztmp2
|
protected |
The documentation for this class was generated from the following files:
- fplll/gso_interface.h
- fplll/gso_interface.cpp
