Pruner class, to compute and optimize cost and success probability of pruned enumeration. More...

#include <pruner.h>

Data Structures
class	TestPruner

Public Member Functions
	Pruner (const int n)
	(limited) Constructor for Pruner. Only for svp_probability. More...

	Pruner (const FT enumeration_radius, const FT preproc_cost, const vector< double > &gso_r, const FT target=0.9, const PrunerMetric metric=PRUNER_METRIC_PROBABILITY_OF_SHORTEST, int flags=PRUNER_GRADIENT)
	Constructor for Pruner. More...

	Pruner (const FT enumeration_radius, const FT preproc_cost, const vector< vector< double > > &gso_rs, const FT target=0.9, const PrunerMetric metric=PRUNER_METRIC_PROBABILITY_OF_SHORTEST, int flags=PRUNER_GRADIENT)
	Constructor for Pruner with multiple basis (averaging the cost function over all of them) More...

void	optimize_coefficients (vector< double > &pr)
	Main interface for optimizing pruning coefficients. More...

void	optimize_coefficients_cost_vary_prob (vector< double > &pr)
	Main interface for optimizing the pruning coefficients with respect to the overall enumeration time. More...

void	optimize_coefficients_cost_fixed_prob (vector< double > &pr)
	Main interface to optimize the pruning coefficients with respect to the single enumeration. More...

void	optimize_coefficients_evec (vector< double > &pr)
	Run the optimization process using 'even' coefficients. More...

void	optimize_coefficients_full (vector< double > &pr)
	Run the optimization process using all the coefficients. More...

double	single_enum_cost (const vector< double > &pr, vector< double > *detailed_cost=nullptr)
	Compute the cost of a single enumeration. More...

double	repeated_enum_cost (const vector< double > &pr)
	cost of repeating enumeration and preprocessing More...

double	measure_metric (const vector< double > &pr)
	Return either SVP probability or expected number of solution depending on metric. More...

FT	gaussian_heuristic ()
	gaussian heuristic for the shortest vector length of the loaded basis. More...

Friends
class	TestPruner

Detailed Description

template<class FT>
class Pruner< FT >

Pruner class, to compute and optimize cost and success probability of pruned enumeration.

The class is templated by a Floating Point Type, which are used for internal computations.

This class provides an implementation of the numerically optimized pruning strategy of [Gama Nguyen Regev 2010].

Many details for implementation follows from the thesis [Chen 2013] Some simplifications have been made, for example we restrict ourselves to `‘even vector bounds’' i.e., the bound at indices 2i and 2i+1 are kept equal, as to allow volume estimation by symbolic integration (see [GNR10,Chen13])

naming conventions:

b is for bound (squared)
ipv is for inverse partial volumes (NOT squared)
r is for gram schmidt length (squared). Automatically renormalized to avoid overflowing partial volumes
p is for polynomial

inside this code, b,pv,and r are in reversed order as to conform with the algorithm description of [Chen13] reversing the order is handled by the load and save methods.

n is for the dimension of the basis to prune
d is for degrees of polynomials. md is for max_degree
d is floor(n/2 at most). Odd n are dealt with by ignoring the first component

Constructor & Destructor Documentation

◆ Pruner() [1/3]

template<class FT >

Pruner< FT >::Pruner ( const int n )

inlineexplicit

(limited) Constructor for Pruner. Only for svp_probability.

Parameters

n	dimension of the pruned block

◆ Pruner() [2/3]

template<class FT >

Pruner< FT >::Pruner	(	const FT	enumeration_radius,
		const FT	preproc_cost,
		const vector< double > &	gso_r,
		const FT	target = `0.9`,
		const PrunerMetric	metric = `PRUNER_METRIC_PROBABILITY_OF_SHORTEST`,
		int	flags = `PRUNER_GRADIENT`
	)

inline

Constructor for Pruner.

Algorithmic details are given for the wrapping function prune().

Parameters

enumeration_radius	radius of the desired enumeration
preproc_cost	cost of preprocessing (i.e. additive cost for a retrying an enumeration)
gso_r	vector Gram-Schmidt length (squared) of the enumerated block over several bases
target	desired target success probability/expected solutions after all retrial.
metric	metric is to be optimized : PRUNER_METRIC_PROBABILITY_OF_SHORTEST or PRUNER_METRIC_EXPECTED_SOLUTIONS
flags	complementary parameters : PRUNER_CVP PRUNER_START_FROM_INPUT PRUNER_GRADIENT PRUNER_NELDER_MEAD PRUNER_VERBOSE

◆ Pruner() [3/3]

template<class FT >

Pruner< FT >::Pruner	(	const FT	enumeration_radius,
		const FT	preproc_cost,
		const vector< vector< double > > &	gso_rs,
		const FT	target = `0.9`,
		const PrunerMetric	metric = `PRUNER_METRIC_PROBABILITY_OF_SHORTEST`,
		int	flags = `PRUNER_GRADIENT`
	)

inline

Constructor for Pruner with multiple basis (averaging the cost function over all of them)

Algorithmic details are given for the wrapping function prune().

Parameters

enumeration_radius	radius of the desired enumeration
preproc_cost	cost of preprocessing (i.e. additive cost for a retrying an enumeration)
gso_rs	vector of vector Gram-Schmidt length (squared) of the enumerated block over several bases
target	desired target success probability/expected solutions after all retrial.
metric	metric is to be optimized : PRUNER_METRIC_PROBABILITY_OF_SHORTEST or PRUNER_METRIC_EXPECTED_SOLUTIONS
flags	complementary parameters : PRUNER_CVP PRUNER_START_FROM_INPUT PRUNER_GRADIENT PRUNER_NELDER_MEAD PRUNER_VERBOSE

Member Function Documentation

◆ gaussian_heuristic()

template<class FT >

FT Pruner< FT >::gaussian_heuristic

gaussian heuristic for the shortest vector length of the loaded basis.

Note: If multiple loaded then it is the gaussian heuristic of the first one.

◆ measure_metric()

template<class FT >

double Pruner< FT >::measure_metric ( const vector< double > & pr )

inline

Return either SVP probability or expected number of solution depending on metric.

◆ optimize_coefficients()

template<class FT >

void Pruner< FT >::optimize_coefficients ( vector< double > & pr )

Main interface for optimizing pruning coefficients.

It will invoke either of the two functions:

depending on the input flags.

If the flag PRUNER_SINGLE is disabled (default), it calls function (1) so that goal is to optimize the cost computed assingle_enum_cost(pr) * trials + preproc_cost * (trials - 1.0)

If the flag PRUNER_SINGLE is enabled in flags, it calls function (2) such that the goal is to optimize the single_enum_cost(pr) while fixing the metric (number of solutions or success probability) to the target.

optimize either overall cost or cost by fixing probability

◆ optimize_coefficients_cost_fixed_prob()

template<class FT >

void Pruner< FT >::optimize_coefficients_cost_fixed_prob ( vector< double > & pr )

Main interface to optimize the pruning coefficients with respect to the single enumeration.

Main interface to optimize the single enumeration time with the constraint such that the succ. prob (or expected solutions) is fixed (and given) from input to the Pruner constructor.

Hierarchy of calls if PRUNER_HALF is not set (default):

This function first invokes optimize_coefficients_evec_core() and then optimize_coefficients_full_core() to optimize the overall enumeration cost.
Then it tries to adjust the pruning parameters to achieve the target succ. probability (or expected number of solutions) by calling either optimize_coefficients_incr_prob() or optimize_coefficients_decr_prob().
Finally, it does some local optimization by calling optimize_coefficients_local_adjust_smooth() which aims to smooth the discountinuities in the curve and then optimize_coefficients_local_adjust_prob() which aims to fine-adjust the succ. probability to be close enough to the target.

◆ optimize_coefficients_cost_vary_prob()

template<class FT >

void Pruner< FT >::optimize_coefficients_cost_vary_prob ( vector< double > & pr )

Main interface for optimizing the pruning coefficients with respect to the overall enumeration time.

Main interface to optimize the overall enumeration time where the target function is: single_enum_cost(pr) * trials + preproc_cost * (trials - 1.0);

Hierarchy of calls if PRUNER_HALF is not set (default):

This function first invokes optimize_coefficients_evec_core() which optimizes using only even-position vectors for speed.
Then it calls several local tuning functions optimize_coefficients_local_adjust_*() to adjust the parameters in small scales.
Finally it does an optimization using full vectors using optimize_coefficients_full_core(). This procedure is repeated for several rounds until no further improvements can be achieved.

If PRUNER_HALF is set, this function simply calls optimize_coefficients_evec. Note that if PRUNER_HALF is set, one can not use PRUNER_SINGLE.

◆ optimize_coefficients_evec()

template<class FT >

void Pruner< FT >::optimize_coefficients_evec ( vector< double > & pr )

Run the optimization process using 'even' coefficients.

Run the optimization process, successively using the algorithm activated using using half coefficients: the input pr has length n; but only the even indices in the vector will be used in the optimization. In the end, we have pr_i = pr_{i+1}.

Note that this function calls optimize_coefficients_evec_core(). The difference is that this function optimize_coefficients_evec() do not assume pr contains some valid coefficient in prior. If the input pr is empty, it starts with the greedy() method and does some preparation work before it invokes optimize_coefficients_evec_core().

Note that this function (and optimize_coefficients_evec_core()) only optimizes the overall enumeration time where the target function is:

      `single_enum_cost(pr) * trials + preproc_cost * (trials - 1.0)`

preparation and call optimization with constrains that b_i = b_{i+1} for even i.

◆ optimize_coefficients_full()

template<class FT >

void Pruner< FT >::optimize_coefficients_full ( vector< double > & pr )

Run the optimization process using all the coefficients.

Run the optimization process, successively using the algorithm activated using using full coefficients. That is, we do not have the constraint pr_i = pr_{i+1} in this function.

Note that this function calls optimize_coefficients_full_core(). The difference is that this function optimize_coefficients_full() do not assume pr contains some valid coefficient in prior. If the input pr is empty, it starts with the greedy() method and does some preparation work before it invokes optimize_coefficients_full_core().

Note that this function (and optimize_coefficients_full_core()) only optimizes the overall enumeration time where the target function is:

       `single_enum_cost(pr) * trials + preproc_cost * (trials - 1.0)`

Optimize without constrains b_i = b_{i+1} for even i. Note that this function assumes the pr already contains some valid pruning coefficients.

◆ repeated_enum_cost()

template<class FT >

double Pruner< FT >::repeated_enum_cost ( const vector< double > & pr )

inline

cost of repeating enumeration and preprocessing

Compute the cost of r enumeration and (r-1) preprocessing, where r is the required number of retrials to reach target/target_solution

Parameters

b	pruning bounds

Returns: cost

◆ single_enum_cost()

template<class FT >

double Pruner< FT >::single_enum_cost	(	const vector< double > &	pr,
		vector< double > *	detailed_cost = `nullptr`
	)

inline

Compute the cost of a single enumeration.

Friends And Related Function Documentation

◆ TestPruner

template<class FT >

friend class TestPruner

friend

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

fplll/pruner/pruner.h
fplll/pruner/pruner.cpp
fplll/pruner/pruner_cost.cpp
fplll/pruner/pruner_optimize.cpp
fplll/pruner/pruner_optimize_tc.cpp
fplll/pruner/pruner_optimize_tp.cpp
fplll/pruner/pruner_prob.cpp
fplll/pruner/pruner_simplex.h
fplll/pruner/pruner_util.cpp

Data Structures

Public Member Functions

Friends

Detailed Description

Constructor & Destructor Documentation

◆ Pruner() [1/3]

◆ Pruner() [2/3]

◆ Pruner() [3/3]

Member Function Documentation

◆ gaussian_heuristic()

◆ measure_metric()

◆ optimize_coefficients()

◆ optimize_coefficients_cost_fixed_prob()

◆ optimize_coefficients_cost_vary_prob()

◆ optimize_coefficients_evec()

◆ optimize_coefficients_full()

◆ repeated_enum_cost()

◆ single_enum_cost()

Friends And Related Function Documentation

◆ TestPruner