Specialisation of piranha::series_multiplier for piranha::polynomial. More...

#include <piranha/polynomial.hpp>

Inheritance diagram for piranha::series_multiplier< Series, detail::poly_multiplier_enabler< Series > >:

Collaboration diagram for piranha::series_multiplier< Series, detail::poly_multiplier_enabler< Series > >:

Public Types
using	v_ptr = std::vector< typename Series::term_type const * >
	Alias for a vector of const pointers to series terms.

using	size_type = typename v_ptr::size_type
	The size type of base_series_multiplier::v_ptr.

using	bucket_size_type = typename Series::size_type
	The size type of `Series`.

Public Member Functions
	series_multiplier (const Series &s1, const Series &s2)
	Constructor. More...

template<typename T = Series, call_enabler< T > = 0>
Series	operator() () const
	Perform multiplication. More...

Low-level interface
Low-level methods, on top of which the call operator is implemented.
Series	_untruncated_multiplication () const
	Untruncated multiplication. More...

template<typename T , typename... Args>
Series	_truncated_multiplication (const T &max_degree, const Args &... args) const
	Truncated multiplication. More...

template<typename T >
std::vector< typename base::size_type >	_get_skip_limits (const std::vector< T > &v_d1, const std::vector< T > &v_d2, const T &max_degree) const
	Establish skip limits for truncated multiplication. More...

Protected Member Functions
template<typename MultFunctor , typename LimitFunctor >
void	blocked_multiplication (const MultFunctor &mf, const size_type &start1, const size_type &end1, const LimitFunctor &lf) const
	Blocked multiplication. More...

template<typename MultFunctor >
void	blocked_multiplication (const MultFunctor &mf, const size_type &start1, const size_type &end1) const
	Blocked multiplication (convenience overload). More...

template<std::size_t MultArity, typename MultFunctor , typename LimitFunctor >
bucket_size_type	estimate_final_series_size (const LimitFunctor &lf) const
	Estimate size of series multiplication. More...

template<std::size_t MultArity, typename MultFunctor >
bucket_size_type	estimate_final_series_size () const
	Estimate size of series multiplication (convenience overload) More...

template<typename LimitFunctor >
Series	plain_multiplication (const LimitFunctor &lf) const
	A plain series multiplication routine. More...

Series	plain_multiplication () const
	A plain series multiplication routine (convenience overload). More...

void	finalise_series (Series &s) const
	Finalise series. More...

Static Protected Member Functions
static void	sanitise_series (Series &retval, unsigned n_threads)
	Sanitise series. More...

Protected Attributes
v_ptr	m_v1
	Vector of const pointers to the terms in the larger series.

v_ptr	m_v2
	Vector of const pointers to the terms in the smaller series.

const symbol_fset	m_ss
	The symbol set of the series used during construction.

unsigned	m_n_threads
	Number of threads. More...

Detailed Description

template<typename Series>
class piranha::series_multiplier< Series, detail::poly_multiplier_enabler< Series > >

Specialisation of piranha::series_multiplier for piranha::polynomial.

This specialisation of piranha::series_multiplier is enabled when Series is an instance of piranha::polynomial.

Type requirements

Series must be suitable for use in piranha::base_series_multiplier.

Exception safety guarantee

This class provides the same guarantee as piranha::base_series_multiplier.

Move semantics

Move semantics is equivalent to piranha::base_series_multiplier's move semantics.

Definition at line 978 of file polynomial.hpp.

Constructor & Destructor Documentation

◆ series_multiplier()

template<typename Series >

piranha::series_multiplier< Series, detail::poly_multiplier_enabler< Series > >::series_multiplier	(	const Series &	s1,
		const Series &	s2
	)

inlineexplicit

Constructor.

The constructor will call the base constructor and run these additional checks:

if the key is a piranha::kronecker_monomial, it will be checked that the result of the multiplication does not overflow the representation limits of piranha::kronecker_monomial;
if the key is a piranha::monomial of a C++ integral type, it will be checked that the result of the multiplication does not overflow the limits of the integral type.

If any check fails, a runtime error will be produced.

Parameters

s1	first series operand.
s2	second series operand.

Exceptions

std::overflow_error	if a bounds check, as described above, fails.
unspecified	any exception thrown by: the base constructor, standard threading primitives, memory errors in standard containers, thread_pool::enqueue(), future_list::push_back().

Definition at line 1278 of file polynomial.hpp.

Member Function Documentation

◆ _get_skip_limits()

template<typename Series >

template<typename T >

std::vector<typename base::size_type> piranha::series_multiplier< Series, detail::poly_multiplier_enabler< Series > >::_get_skip_limits	(	const std::vector< T > &	v_d1,
		const std::vector< T > &	v_d2,
		const T &	max_degree
	)		const

inline

Establish skip limits for truncated multiplication.

Note: This method can be called only if Series supports truncated multiplication (as explained in piranha::polynomial) and T is the same type as the degree type.

This method assumes that v_d1 and v_d2 are vectors containing the degrees of each term in the first and second series respectively, and that v_d2 is sorted in ascending order. It will return a vector v of indices in the second series such that, given an index i in the first series, the term of index v[i] in the second series is the first term such that the term-by-term multiplication with the i-th term in the first series produces a term of degree greater than max_degree. That is, terms of index equal to or greater than v[i] in the second series will produce terms with degree greater than max_degree when multiplied by the i-th term in the first series.

Parameters

v_d1	a vector containing the degrees of the terms in the first series.
v_d2	a sorted vector containing the degrees of the terms in the second series.
max_degree	the truncation degree.

Returns: the vector of skip limits, as explained above.

Exceptions

unspecified

any exception thrown by:

memory errors in standard containers,
piranha::safe_cast(),
operations on the degree type.

Definition at line 1464 of file polynomial.hpp.

◆ _truncated_multiplication()

template<typename Series >

template<typename T , typename... Args>

Series piranha::series_multiplier< Series, detail::poly_multiplier_enabler< Series > >::_truncated_multiplication	(	const T &	max_degree,
		const Args &...	args
	)		const

inline

Truncated multiplication.

Note

This method can be used only if the following conditions apply:

the conditions for truncated multiplication outlined in piranha::polynomial are satisfied,
the type T is the same as the degree type of the polynomial,
the number and types of Args is as specified below,
piranha::base_series_multiplier::plain_multiplication() and _get_skip_limits() can be called.

This method will perform the truncated multiplication of the series operands passed to the constructor. The truncation degree is set to max_degree, and it is either:

the total maximum degree, if the number of Args is zero, or
the partial degree, if the number of Args is two.

In the latter case, the two arguments must be:

an std::vector of std::string representing the names of the variables which will be taken into account when computing the partial degree,
a piranha::symbol_idx_fset referring to the positions of the variables of the first argument in the merged symbol set of the two operands.

Parameters

max_degree	the maximum degree of the result of the multiplication.
args	either an empty argument, or a pair of arguments as described above.

Returns: the result of the truncated multiplication of the operands used for construction.

Exceptions

unspecified

any exception thrown by:

memory errors in standard containers,
piranha::safe_cast(),
arithmetic and other operations on the degree type,
base_series_multiplier::plain_multiplication(),
_get_skip_limits().

Definition at line 1390 of file polynomial.hpp.

◆ _untruncated_multiplication()

template<typename Series >

Series piranha::series_multiplier< Series, detail::poly_multiplier_enabler< Series > >::_untruncated_multiplication ( ) const

inline

Untruncated multiplication.

Note: This method can be used only if operator()() can be called.

This method will return the result of multiplying the two polynomials used as input arguments in the class' constructor. The multiplication will be untruncated, regardless of the current global truncation settings.

Returns: the result of the untruncated multiplication of the two operands used in the construction of this.

Exceptions

unspecified

any exception thrown by:

piranha::base_series_multiplier::plain_multiplication(),
piranha::base_series_multiplier::estimate_final_series_size(),
piranha::base_series_multiplier::sanitise_series(),
piranha::base_series_multiplier::finalise_series(),
boost::numeric_cast(),
the public interface of piranha::hash_set,
piranha::safe_cast(),
memory errors in standard containers,
piranha::math::mul3(),
piranha::math::multiply_accumulate(),
thread_pool::enqueue(),
future_list::push_back().

Definition at line 1353 of file polynomial.hpp.

◆ blocked_multiplication() [1/2]

template<typename Series >

template<typename MultFunctor , typename LimitFunctor >

void piranha::base_series_multiplier< Series >::blocked_multiplication	(	const MultFunctor &	mf,
		const size_type &	start1,
		const size_type &	end1,
		const LimitFunctor &	lf
	)		const

inlineprotectedinherited

Blocked multiplication.

Note: If MultFunctor or LimitFunctor do not satisfy the requirements outlined below, a compile-time error will be produced.

This method is logically equivalent to the following double loop:

for (size_type i = start1; i < end1; ++i) {
     const size_type limit = std::min(lf(i),m_v2.size());
 for (size_type j = 0; j < limit; ++j) {
        mf(i,j);
 }
}

mf must be a function object with a call operator accepting two instances of base_series_multiplier::size_type and returning void. lf must be a function object with a call operator accepting and returning a base_series_multiplier::size_type.

Internally, the double loops is decomposed in blocks of size tuning::get_multiplication_block_size() in an attempt to optimise cache memory access patterns.

This method is meant to be used for series multiplication. mf is intended to be a function object that multiplies the i-th term of the first series by the j-th term of the second series. lf is intended to be a functor that establishes how many terms in the second series have to be multiplied by the i-th term of the first series.

Parameters

mf	the multiplication functor.
start1	start index in the first series.
end1	end index in the first series.
lf	the limit functor.

Exceptions

std::invalid_argument	if `start1` is greater than `end1` or greater than the size of base_series_multiplier::m_v1, or if `end1` is greater than the size of base_series_multiplier::m_v1.
unspecified	any exception thrown by the call operator of `mf` or `sf`, or piranha::safe_cast.

Definition at line 442 of file base_series_multiplier.hpp.

◆ blocked_multiplication() [2/2]

template<typename Series >

template<typename MultFunctor >

void piranha::base_series_multiplier< Series >::blocked_multiplication	(	const MultFunctor &	mf,
		const size_type &	start1,
		const size_type &	end1
	)		const

inlineprotectedinherited

Blocked multiplication (convenience overload).

This method is equivalent to the other overload with a limit functor that will unconditionally always return the size of the second series.

Parameters

mf	the multiplication functor.
start1	start index in the first series.
end1	end index in the first series.

Exceptions

unspecified any exception thrown by the other overload.

Definition at line 509 of file base_series_multiplier.hpp.

◆ estimate_final_series_size() [1/2]

template<typename Series >

template<std::size_t MultArity, typename MultFunctor , typename LimitFunctor >

bucket_size_type piranha::base_series_multiplier< Series >::estimate_final_series_size ( const LimitFunctor & lf ) const

inlineprotectedinherited

Estimate size of series multiplication.

Note: If MultArity, MultFunctor or LimitFunctor do not satisfy the requirements outlined below, a compile-time error will be produced.

This method expects a MultFunctor type exposing the same inteface as explained in blocked_multiplication(). Additionally, MultFunctor must be constructible from a const reference to piranha::base_series_multiplier and a mutable reference to Series. MultFunctor objects will be constructed internally by this method, passing this and a temporary local Series object as construction parameters. It will be assumed that a call mf(i,j) multiplies the i-th term of the first series by the j-th term of the second series, accumulating the result into the Series passed as second parameter for construction.

This method will apply a statistical approach to estimate the final size of the result of the multiplication of the first series by the second. It will perform random term-by-term multiplications and deduce the estimate from the number of term multiplications performed before finding the first duplicate term. The MultArity parameter represents the arity of term multiplications - that is, the number of terms generated by a single term-by-term multiplication. It must be strictly positive.

The lf parameter must be a function object exposing the same inteface as explained in blocked_multiplication(). This functor establishes how many terms in the second series must be multiplied by the i-th term of the first series.

The number returned by this function is always at least 1. Multiple threads might be used by this method: in such a case, different instances of MultFunctor are constructed in different threads, but lf is shared among all threads.

Parameters

lf	the limit functor.

Returns: the estimated size of the multiplication of the first series by the second, always at least 1.

Exceptions

std::overflow_error	in case of (unlikely) overflows in integral arithmetics.
unspecified	any exception thrown by: overflow errors in the conversion of piranha::integer to integral types, the call operator of `mf` or `lf`, and the constructor of `mf`, memory errors in standard containers, the conversion operator of piranha::integer, standard threading primitives, thread_pool::enqueue(), future_list::push_back().

Definition at line 556 of file base_series_multiplier.hpp.

◆ estimate_final_series_size() [2/2]

template<typename Series >

template<std::size_t MultArity, typename MultFunctor >

bucket_size_type piranha::base_series_multiplier< Series >::estimate_final_series_size ( ) const

inlineprotectedinherited

Estimate size of series multiplication (convenience overload)

Returns: the output of the other overload of estimate_final_series_size(), with a limit functor whose call operator will always return the size of the second series unconditionally.

Exceptions

unspecified any exception thrown by the other overload of estimate_final_series_size().

Definition at line 719 of file base_series_multiplier.hpp.

◆ finalise_series()

template<typename Series >

void piranha::base_series_multiplier< Series >::finalise_series ( Series & s ) const

inlineprotectedinherited

Finalise series.

This method will finalise the output s of a series multiplication undertaken via piranha::base_series_multiplier. Currently, this method will not do anything unless the coefficient type of Series is an instance of piranha::mp_rational. In this case, the coefficients of s will be normalised with respect to the least common multiplier computed in the constructor of piranha::base_series_multiplier.

Parameters

s	the `Series` to be finalised.

Exceptions

unspecified

any exception thrown by:

Definition at line 1120 of file base_series_multiplier.hpp.

◆ operator()()

template<typename Series >

template<typename T = Series, call_enabler< T > = 0>

Series piranha::series_multiplier< Series, detail::poly_multiplier_enabler< Series > >::operator() ( ) const

inline

Perform multiplication.

Note

This template operator is enabled only if:

the coefficient and key type of Series satisfy piranha::key_is_multipliable,
the coefficient type of Series supports piranha::math::mul3() and piranha::math::multiply_accumulate().

This method will perform the multiplication of the series operands passed to the constructor. Depending on the key type of Series, the implementation will use either base_series_multiplier::plain_multiplication() with base_series_multiplier::plain_multiplier or a different algorithm.

If a polynomial truncation threshold is defined and the degree type of the polynomial is a C++ integral type, the integral arithmetic operations involved in the truncation logic will be checked for overflow.

Returns: the result of the multiplication of the input series operands.

Exceptions

std::overflow_error in case of overflow errors.

unspecified

any exception thrown by:

piranha::base_series_multiplier::plain_multiplication(),
piranha::base_series_multiplier::estimate_final_series_size(),
piranha::base_series_multiplier::sanitise_series(),
piranha::base_series_multiplier::finalise_series(),
boost::numeric_cast(),
the public interface of piranha::hash_set,
piranha::safe_cast(),
memory errors in standard containers,
piranha::math::mul3(),
piranha::math::multiply_accumulate(),
thread_pool::enqueue(),
future_list::push_back(),
_truncated_multiplication(),
polynomial::get_auto_truncate_degree().

Definition at line 1320 of file polynomial.hpp.

◆ plain_multiplication() [1/2]

template<typename Series >

template<typename LimitFunctor >

Series piranha::base_series_multiplier< Series >::plain_multiplication ( const LimitFunctor & lf ) const

inlineprotectedinherited

A plain series multiplication routine.

Note: If the key and coefficient types of Series do not satisfy piranha::key_is_multipliable, or LimitFunctor does not satisfy the requirements outlined in base_series_multiplier::blocked_multiplication(), a compile-time error will be produced.

This method implements a generic series multiplication routine suitable for key types that satisfy piranha::key_is_multipliable. The implementation is either single-threaded or multi-threaded, depending on the sizes of the input series, and it will use either base_series_multiplier::plain_multiplier or a similar thread-safe multiplier for the term-by-term multiplications. The lf functor will be forwarded as limit functor to base_series_multiplier::blocked_multiplication() and base_series_multiplier::estimate_final_series_size().

Note that, in multithreaded mode, lf will be shared among (and called concurrently from) all the threads.

Parameters

lf	the limit functor (see base_series_multiplier::blocked_multiplication()).

Returns: the series resulting from the multiplication of the two series used to construct this.

Exceptions

unspecified

any exception thrown by:

piranha::safe_cast(),
base_series_multiplier::estimate_final_series_size(),
boost::numeric_cast(),
the public interface of piranha::hash_set,
base_series_multiplier::blocked_multiplication(),
base_series_multiplier::sanitise_series(),
the multiply() method of the key type of Series,
thread_pool::enqueue(),
future_list::push_back(),
the construction of terms,
in-place addition of coefficients.

Definition at line 978 of file base_series_multiplier.hpp.

◆ plain_multiplication() [2/2]

template<typename Series >

Series piranha::base_series_multiplier< Series >::plain_multiplication ( ) const

inlineprotectedinherited

A plain series multiplication routine (convenience overload).

Returns: the output of the other overload of plain_multiplication(), with a limit functor whose call operator will always return the size of the second series unconditionally.

Exceptions

unspecified any exception thrown by the other overload of plain_multiplication().

Definition at line 1100 of file base_series_multiplier.hpp.

◆ sanitise_series()

template<typename Series >

static void piranha::base_series_multiplier< Series >::sanitise_series	(	Series &	retval,
		unsigned	n_threads
	)

inlinestaticprotectedinherited

Sanitise series.

When using the low-level interface of piranha::hash_set for term insertion, invariants might be violated both in piranha::hash_set and piranha::series. In particular:

terms may not be checked for compatibility or for being zero upon insertion,
the count of elements in piranha::hash_set might not be updated.

This method can be used to fix these invariants: it will check whether each term of retval is incompatible and/or zero, and the total count of terms in the series will be set to the number of nonzero terms. Zero terms will be erased.

Note that in case of exceptions retval will likely be left in an inconsistent state which violates internal invariants. Calls to this function should always be wrapped in a try/catch block that makes sure that retval is cleared before re-throwing.

Parameters

retval	the series to be sanitised.
n_threads	the number of threads to be used.

Exceptions

std::invalid_argument	if `n_threads` is zero, or if one of the terms in `retval` is not compatible with the symbol set of `retval`.
std::overflow_error	if the number of terms in `retval` overflows the maximum value representable by base_series_multiplier::bucket_size_type.
unspecified	any exception thrown by: the cast operator of piranha::integer, standard threading primitives, thread_pool::enqueue(), future_list::push_back().

Definition at line 845 of file base_series_multiplier.hpp.

Member Data Documentation

◆ m_n_threads

template<typename Series >

unsigned piranha::base_series_multiplier< Series >::m_n_threads

protectedinherited

Number of threads.

This value will be set by the constructor, and it represents the number of threads that will be used by the multiplier. The value is always at least 1 and it is calculated via thread_pool::use_threads().

Definition at line 1138 of file base_series_multiplier.hpp.

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

polynomial.hpp

Public Types

Public Member Functions

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Detailed Description

template<typename Series> class piranha::series_multiplier< Series, detail::poly_multiplier_enabler< Series > >

Type requirements

Exception safety guarantee

Move semantics

Constructor & Destructor Documentation

◆ series_multiplier()

Member Function Documentation

◆ _get_skip_limits()

◆ _truncated_multiplication()

◆ _untruncated_multiplication()

◆ blocked_multiplication() [1/2]

◆ blocked_multiplication() [2/2]

◆ estimate_final_series_size() [1/2]

◆ estimate_final_series_size() [2/2]

◆ finalise_series()

◆ operator()()

◆ plain_multiplication() [1/2]

◆ plain_multiplication() [2/2]

◆ sanitise_series()

Member Data Documentation

◆ m_n_threads

template<typename Series>
class piranha::series_multiplier< Series, detail::poly_multiplier_enabler< Series > >