Sparse multivariate polynomial. More...

#include <tpl_multi_polynomial.H>

Collaboration diagram for Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >:

Classes
struct	FactorTerm
	Factorization term: a factor polynomial with its multiplicity. More...

struct	Pair_Candidate

struct	Pair_Candidate_Less

struct	Uni_Factor_Signature_Less
	Deterministic ordering of primitive univariate factors by normalized signature. More...

struct	Uni_Linear_Factor_Data
	Primitive linear factor data \(a x + b\)for a chosen main variable. More...

struct	Uni_Linear_Factor_Data_Less
	Deterministic ordering of primitive univariate linear factors. More...

Public Types
using	Coeff = Coefficient

using	Index = Array< size_t >

using	Order = MonomOrder

Public Member Functions
	Gen_MultiPolynomial ()=default
	Default constructor: the zero polynomial with 0 variables.

	Gen_MultiPolynomial (const size_t nvars, const Coefficient &c=Coefficient{})
	Constant polynomial.

	Gen_MultiPolynomial (const size_t nvars, const Array< size_t > &idx, const Coefficient &c)
	Single-term constructor.

	Gen_MultiPolynomial (const size_t nvars, const DynList< std::pair< Array< size_t >, Coefficient > > &ts)
	Construct from a list of (exponent-vector, coefficient) pairs.

	Gen_MultiPolynomial (const size_t nvars, std::initializer_list< std::pair< Array< size_t >, Coefficient > > ts)
	Construct from an initializer list of term pairs.

bool	is_zero () const noexcept
	True if this is the zero polynomial.

bool	is_constant () const noexcept
	True if constant or zero (total degree 0).

size_t	num_vars () const noexcept
	Number of variables.

size_t	num_terms () const noexcept
	Number of non-zero terms.

size_t	degree () const noexcept
	Total degree (maximum sum of exponents over all terms).

size_t	degree_in (size_t var) const noexcept
	Degree in a specific variable.

std::pair< Array< size_t >, Coefficient >	leading_term () const
	Leading term (largest monomial in the ordering).

Coefficient	leading_coeff () const
	Leading coefficient.

Array< size_t >	leading_monomial () const
	Leading monomial (exponent vector of the leading term).

Coefficient	coeff_at (const Array< size_t > &idx) const
	Read coefficient at a multi-index (0 if absent).

template<class Op >
void	for_each_term (Op &&op) const
	Visit every non-zero term in ascending monomial order.

template<class Op >
void	for_each_term_desc (Op &&op) const
	Visit every non-zero term in descending monomial order.

DynList< std::pair< Array< size_t >, Coefficient > >	terms () const
	All terms as a list (ascending order).

void	add_to_coeff (const Array< size_t > &idx, const Coefficient &delta)
	Add `delta` to the coefficient at `idx`.

void	remove_zeros ()
	Remove all terms whose coefficient is approximately zero.

void	scale_inplace (const Coefficient &s)
	Multiply every coefficient by `s` in place.

void	divide_scalar_inplace (const Coefficient &s)
	Divide every coefficient by `s` in place.

Gen_MultiPolynomial	operator+ (const Gen_MultiPolynomial &q) const
	Polynomial addition.

Gen_MultiPolynomial &	operator+= (const Gen_MultiPolynomial &q)
	In-place addition.

Gen_MultiPolynomial	operator+ (const Coefficient &s) const
	Add a scalar constant term.

Gen_MultiPolynomial &	operator+= (const Coefficient &s)
	In-place addition of a scalar constant term.

Gen_MultiPolynomial	operator- (const Gen_MultiPolynomial &q) const
	Polynomial subtraction.

Gen_MultiPolynomial &	operator-= (const Gen_MultiPolynomial &q)
	In-place subtraction.

Gen_MultiPolynomial	operator- (const Coefficient &s) const
	Subtract a scalar constant term.

Gen_MultiPolynomial &	operator-= (const Coefficient &s)
	In-place subtraction of a scalar constant term.

Gen_MultiPolynomial	operator- () const
	Unary negation.

Gen_MultiPolynomial	operator* (const Gen_MultiPolynomial &q) const
	Polynomial multiplication.

Gen_MultiPolynomial &	operator*= (const Gen_MultiPolynomial &q)
	In-place polynomial multiplication.

Gen_MultiPolynomial	operator* (const Coefficient &s) const
	Multiply by a scalar.

Gen_MultiPolynomial &	operator*= (const Coefficient &s)
	In-place scalar multiplication.

Gen_MultiPolynomial	operator/ (const Coefficient &s) const
	Divide by a scalar.

Gen_MultiPolynomial &	operator/= (const Coefficient &s)
	In-place scalar division.

Gen_MultiPolynomial	pow (size_t n) const
	Exponentiation \(p^n\)by repeated squaring.

Coefficient	eval (const Array< Coefficient > &pt) const
	Evaluate at a point.

Coefficient	operator() (const Array< Coefficient > &pt) const
	Evaluate at a point (function-call syntax).

bool	operator== (const Gen_MultiPolynomial &q) const
	Polynomial equality.

bool	operator!= (const Gen_MultiPolynomial &q) const
	Polynomial inequality.

std::string	to_str (const DynList< std::string > &names=DynList< std::string >()) const
	Human-readable string.

Gen_MultiPolynomial	promote (size_t new_nv) const
	Promote to a polynomial with more variables.

Gen_MultiPolynomial	partial (size_t var, size_t n=1) const
	Partial derivative with respect to a variable.

Array< Gen_MultiPolynomial >	gradient () const
	Gradient vector: array of all first-order partial derivatives.

Array< Array< Gen_MultiPolynomial > >	hessian () const
	Hessian matrix: all second-order partial derivatives.

Array< Coefficient >	eval_gradient (const Array< Coefficient > &pt) const
	Evaluate gradient at a point.

Array< Array< Coefficient > >	eval_hessian (const Array< Coefficient > &pt) const
	Evaluate Hessian at a point.

std::string	to_json () const
	Serialize polynomial to JSON string.

void	to_binary (std::ostream &out) const
	Serialize polynomial to binary stream.

Array< Coefficient >	eval_batch (const Array< Array< Coefficient > > &pts) const
	Evaluate polynomial at multiple points (with parallelism support).

std::pair< Array< Gen_MultiPolynomial >, Gen_MultiPolynomial >	divmod (const Array< Gen_MultiPolynomial > &divisors) const
	Multivariate division with remainder (Buchberger algorithm).

Gen_MultiPolynomial	reduce_modulo (const Array< Gen_MultiPolynomial > &divisors) const
	Polynomial reduction modulo an ideal (one-liner).

Coefficient	content () const
	Content of a multivariate polynomial: GCD of all coefficients.

Gen_MultiPolynomial	primitive_part () const
	Primitive part: polynomial divided by its content.

Gen_Polynomial< Coefficient >	homomorphic_eval (size_t keep_var, const Array< Coefficient > &eval_pts) const
	Homomorphic evaluation: reduce to univariate by substitution.

DynList< FactorTerm >	factorize () const
	Main multivariate factorization over the integers.

Static Public Member Functions
static constexpr Coefficient	epsilon () noexcept
	Machine epsilon for floating-point coefficients.

static bool	coeff_is_zero (const Coefficient &c) noexcept
	Test whether a coefficient is (approximately) zero.

static Gen_MultiPolynomial	variable (size_t nvars, const size_t var)
	The polynomial \(x_i\)(a single variable).

static Gen_MultiPolynomial	monomial (size_t nvars, const Array< size_t > &idx, const Coefficient &c=Coefficient(1))
	A single monomial \(c \, x^{\alpha}\).

static Gen_MultiPolynomial	fit (const Array< std::pair< Array< Coefficient >, Coefficient > > &data, const size_t nvars, const Array< Array< size_t > > &basis)
	Basic least-squares polynomial fitting.

static Gen_MultiPolynomial	fit_weighted (const Array< std::pair< Array< Coefficient >, Coefficient > > &data, size_t nvars, const Array< Array< size_t > > &basis, const Array< Coefficient > &weights)
	Weighted least-squares polynomial fitting.

static Gen_MultiPolynomial	fit_ridge (const Array< std::pair< Array< Coefficient >, Coefficient > > &data, size_t nvars, const Array< Array< size_t > > &basis, Coefficient lambda_used=nullptr, double gcv_score=nullptr)
	Regularized least-squares fitting with automatic GCV-based lambda selection.

static Gen_MultiPolynomial	interpolate (const Array< Array< Coefficient > > &grid, const Array< Coefficient > &values, size_t nvars)
	Multivariate interpolation via Newton divided differences (Chung-Yao).

static Gen_MultiPolynomial	from_json (const std::string &s)
	Deserialize from JSON.

static Gen_MultiPolynomial	from_binary (std::istream &in)
	Deserialize polynomial from binary stream.

static Gen_MultiPolynomial	fit_parallel (const Array< std::pair< Array< Coefficient >, Coefficient > > &data, size_t nvars, const Array< Array< size_t > > &basis)
	Parallel least-squares fitting.

static Gen_MultiPolynomial	s_poly (const Gen_MultiPolynomial &f, const Gen_MultiPolynomial &g)
	S-polynomial (Sylvester polynomial) of two polynomials.

static Array< Gen_MultiPolynomial >	groebner_basis (const Array< Gen_MultiPolynomial > &generators)
	Gröbner basis computation via Buchberger's algorithm.

static Array< Gen_MultiPolynomial >	reduced_groebner_basis (const Array< Gen_MultiPolynomial > &generators)
	Reduced Gröbner basis (minimized and normalized).

static bool	ideal_member (const Gen_MultiPolynomial &f, const Array< Gen_MultiPolynomial > &generators)
	Test membership in an ideal via Gröbner basis.

static Array< Gen_MultiPolynomial >	ideal_sum (const Array< Gen_MultiPolynomial > &a, const Array< Gen_MultiPolynomial > &b)
	Sum of two ideals: I + J = ⟨generators(I) ∪ generators(J)⟩.

static Array< Gen_MultiPolynomial >	ideal_product (const Array< Gen_MultiPolynomial > &a, const Array< Gen_MultiPolynomial > &b)
	Product of two ideals: I · J = ⟨a_i · b_j : a_i ∈ I, b_j ∈ J⟩.

static Array< Gen_MultiPolynomial >	ideal_power (const Array< Gen_MultiPolynomial > &gens, size_t n)
	Power of an ideal: I^n = I · I · ... · I (n times).

static bool	contains_ideal (const Array< Gen_MultiPolynomial > &I_gens, const Array< Gen_MultiPolynomial > &J_gens)
	Test whether ideal I contains ideal J: I ⊇ J.

static bool	ideals_equal (const Array< Gen_MultiPolynomial > &I_gens, const Array< Gen_MultiPolynomial > &J_gens)
	Test equality of two ideals: I = J.

static bool	radical_member (const Gen_MultiPolynomial &f, const Array< Gen_MultiPolynomial > &gens)
	Test membership in radical of ideal: f ∈ √I.

static Gen_MultiPolynomial	_embed_univariate (const Gen_Polynomial< Coefficient > &u, size_t nv, const size_t x_var)
	Embed a univariate polynomial into the multivariate ring.

static void	_append_unique (Array< Coefficient > &vals, const Coefficient &value)
	Append `value` to `vals` if it is not already present.

static Array< Uni_Linear_Factor_Data >	_collect_sorted_primitive_linear_factors (const Gen_Polynomial< Coefficient > &u)
	Collect primitive linear factors from a univariate factorization in stable order.

static Array< Coefficient >	_collect_unique_monic_linear_roots (const Gen_Polynomial< Coefficient > &u)
	Collect unique roots of monic linear factors from a univariate factorization.

static size_t	_eval_index_for_var (size_t main_var, size_t var) noexcept
	Return the evaluation-array position corresponding to variable `var`.

static size_t	_count_active_vars (const Gen_MultiPolynomial &p, size_t &last_active_var)
	Count active variables (positive degree) and remember the last one seen.

static Gen_MultiPolynomial	_build_affine_factor_from_linear_data (size_t nvars, size_t main_var, const Array< size_t > &other_vars, const Array< Coefficient > &base_eval_pts, const Coefficient &main_coeff, const Array< Coefficient > &other_coeffs, const Coefficient &base_constant_term)
	Build a primitive affine linear factor from specialized coefficients.

static bool	_try_lift_primitive_affine_linear_factor_for_main_var (const Gen_MultiPolynomial &p, size_t main_var, const Array< Coefficient > &base_eval_pts, Gen_MultiPolynomial &factor)
	Try to lift a primitive affine linear factor from specialized coefficients.

static Gen_MultiPolynomial	_build_affine_factor (size_t nvars, size_t main_var, const Array< size_t > &other_vars, const Array< Coefficient > &base_eval_pts, const Array< Coefficient > &slopes, const Coefficient &base_root)
	Build a monic affine linear factor from root data.

static bool	_search_affine_lift_options (const Gen_MultiPolynomial &p, size_t main_var, const Array< size_t > &other_vars, const Array< Array< Coefficient > > &root_options, const Array< Coefficient > &base_eval_pts, const Coefficient &base_root, size_t pos, Array< Coefficient > &slopes, Gen_MultiPolynomial &factor)
	Recursive search for an affine linear multivariate lift.

static bool	_try_lift_affine_linear_factor_for_main_var (const Gen_MultiPolynomial &p, size_t main_var, const Array< Coefficient > &base_eval_pts, Gen_MultiPolynomial &factor)
	Try to lift a monic affine linear factor for a fixed main variable.

static bool	_try_extract_affine_linear_factor (const Gen_MultiPolynomial &p, Gen_MultiPolynomial &factor)
	Try to extract a monic affine linear factor via multivariate lifting.

static bool	_build_interpolation_grid (const Gen_MultiPolynomial &p, const Array< size_t > &other_vars, Coefficient start, Coefficient step, Array< Array< Coefficient > > &grid, size_t &total_points)
	Build a regular interpolation grid for the active non-main variables.

static Array< Coefficient >	_decode_grid_point (const Array< Array< Coefficient > > &grid, size_t flat_index)
	Decode a flat tensor-grid index into coordinates (last dimension fastest).

static Array< Coefficient >	_build_eval_point (size_t nvars, size_t main_var, const Array< size_t > &other_vars, const Array< Coefficient > &coords)
	Build the full homomorphic-evaluation point from active-variable coordinates.

static Array< Gen_Polynomial< Coefficient > >	_expanded_univariate_factors (const Gen_Polynomial< Coefficient > &u)
	Expand a univariate factorization into individual factors.

static bool	_collect_sorted_primitive_factor_groups (const Gen_Polynomial< Coefficient > &u, size_t max_degree, Array< Array< Gen_Polynomial< Coefficient > > > &groups)
	Expand, primitive-normalize, and group factors by degree in a stable order.

static Gen_MultiPolynomial	_embed_coeff_poly_as_x_term (const Gen_MultiPolynomial &coeff_poly, size_t nvars, size_t main_var, const Array< size_t > &other_vars, size_t exp)
	Embed a coefficient polynomial in the ambient ring and multiply by x_main^exp.

static Array< Gen_MultiPolynomial >	_interpolated_factors_for_main_var (const Gen_MultiPolynomial &p, size_t main_var, Coefficient grid_start, Coefficient grid_step)
	Reconstruct primitive factors by interpolation across specialization grids.

static bool	_try_extract_interpolated_factor (const Gen_MultiPolynomial &p, Gen_MultiPolynomial &factor)
	Try to extract an exact non-linear factor via coefficient interpolation.

static DynList< FactorTerm >	_factorize_as_univariate_in_var (const Gen_MultiPolynomial &p, size_t active_var)
	Factor a polynomial that is effectively univariate in one variable.

static DynList< FactorTerm >	factor_recombination (Gen_MultiPolynomial f, const Array< Gen_MultiPolynomial > &candidates)
	Factor recombination: find true factors from lifted candidates.

Private Types
using	Pair_Key = std::pair< size_t, size_t >

using	Pair_Registry = DynMapTree< Pair_Key, bool >

using	Pair_Queue = DynBinHeap< Pair_Candidate, Pair_Candidate_Less >

Private Member Functions
Array< size_t >	norm (const Array< size_t > &idx) const
	Pad an index to nvars_ trailing zeros.

Static Private Member Functions
static void	make_monic_inplace (Gen_MultiPolynomial &p)

static bool	contains_equal_polynomial (const Array< Gen_MultiPolynomial > &basis, const Gen_MultiPolynomial &p)

static bool	leading_monomials_coprime (const Array< size_t > &a, const Array< size_t > &b, const size_t nvars) noexcept

static Pair_Key	canonical_pair (size_t i, size_t j) noexcept

static bool	lcm_pair_less (const Pair_Candidate &lhs, const Pair_Candidate &rhs)

static bool	pair_is_recorded (const Pair_Registry &pairs, size_t i, size_t j)

static bool	pair_is_zero_known (const Pair_Registry &zero_pairs, size_t i, size_t j)

static Pair_Candidate	make_pair_candidate (size_t i, size_t j, const Array< Array< size_t > > &leading_monomials, size_t nvars)

static bool	redundant_pair_by_chain_criterion (const Pair_Candidate &candidate, const Array< Array< size_t > > &leading_monomials, const Pair_Registry &zero_pairs, const size_t nvars)

static Pair_Candidate	pop_best_pair (Pair_Queue &queue, Pair_Registry &queued_pairs)

static void	enqueue_pair_if_needed (Pair_Queue &queue, Pair_Registry &queued_pairs, const Pair_Candidate &candidate, const Array< Array< size_t > > &leading_monomials, Pair_Registry &zero_pairs, const size_t nvars)

static Array< Gen_MultiPolynomial >	autoreduced_generators (const Array< Gen_MultiPolynomial > &generators)

static Array< Gen_MultiPolynomial >	minimize_groebner_basis (Array< Gen_MultiPolynomial > basis)

static Array< Gen_MultiPolynomial >	remove_zero_and_duplicates (const Array< Gen_MultiPolynomial > &basis)

static Array< Gen_MultiPolynomial >	autoreduce_groebner_basis (Array< Gen_MultiPolynomial > basis)

static void	rebuild_groebner_pair_state (const Array< Gen_MultiPolynomial > &basis, Array< Array< size_t > > &leading_monomials, Pair_Queue &queue, Pair_Registry &queued_pairs, Pair_Registry &zero_pairs)

static Coefficient	_eval_monomial (const Array< Coefficient > &pt, const Array< size_t > &alpha)
	Evaluate a monomial \(x^\alpha\)at a point.

static Gen_MultiPolynomial	_substitute_var (const Gen_MultiPolynomial &p, size_t var, const Coefficient &val)
	Substitute a single variable with a scalar value.

template<typename T >
static size_t	_list_size (const DynList< T > &lst)
	Count elements in a DynList.

static bool	_divides_exactly (const Gen_MultiPolynomial &f, const Gen_MultiPolynomial &divisor)
	Test whether `divisor` divides `f` exactly over Z[x1,...,xn].

static Gen_MultiPolynomial	_exact_quotient (const Gen_MultiPolynomial &f, const Gen_MultiPolynomial &divisor)
	Compute exact quotient f / divisor over Z[x1,...,xn].

Private Attributes
size_t	nvars_ = 0

DynMapTree< Array< size_t >, Coefficient, Avl_Tree, MonomOrder >	coeffs

Detailed Description

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>
class Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >

Sparse multivariate polynomial.

Represents a polynomial in \(n\)variables \(x_0, x_1, \ldots, x_{n-1}\)over a coefficient ring. Terms are stored in a balanced BST keyed by exponent vectors, ordered according to the monomial ordering MonomOrder.

Template Parameters

Coefficient	Coefficient type (default `double`).
MonomOrder	Strict-weak-order functor on `Array<size_t>` (default `Grevlex_Order`).

Definition at line 414 of file tpl_multi_polynomial.H.

Member Typedef Documentation

◆ Coeff

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

using Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Coeff = Coefficient

Definition at line 771 of file tpl_multi_polynomial.H.

◆ Index

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

using Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Index = Array<size_t>

Definition at line 772 of file tpl_multi_polynomial.H.

◆ Order

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

using Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Order = MonomOrder

Definition at line 773 of file tpl_multi_polynomial.H.

◆ Pair_Key

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

using Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Pair_Key = std::pair<size_t, size_t>

private

Definition at line 460 of file tpl_multi_polynomial.H.

◆ Pair_Queue

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

using Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Pair_Queue = DynBinHeap<Pair_Candidate, Pair_Candidate_Less>

private

Definition at line 498 of file tpl_multi_polynomial.H.

◆ Pair_Registry

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

using Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Pair_Registry = DynMapTree<Pair_Key, bool>

private

Definition at line 461 of file tpl_multi_polynomial.H.

Constructor & Destructor Documentation

◆ Gen_MultiPolynomial() [1/5]

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Gen_MultiPolynomial ( )

default

Default constructor: the zero polynomial with 0 variables.

◆ Gen_MultiPolynomial() [2/5]

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Gen_MultiPolynomial	(	const size_t	nvars,
		const Coefficient &	c = `Coefficient{}`
	)

inlineexplicit

Constant polynomial.

Parameters

[in]	nvars	Number of variables.
[in]	c	Constant value (default 0).

Definition at line 813 of file tpl_multi_polynomial.H.

◆ Gen_MultiPolynomial() [3/5]

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Gen_MultiPolynomial	(	const size_t	nvars,
		const Array< size_t > &	idx,
		const Coefficient &	c
	)

inline

Single-term constructor.

Parameters

[in]	nvars	Number of variables.
[in]	idx	Exponent vector.
[in]	c	Coefficient.

Definition at line 825 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeffs, and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::norm().

◆ Gen_MultiPolynomial() [4/5]

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Gen_MultiPolynomial	(	const size_t	nvars,
		const DynList< std::pair< Array< size_t >, Coefficient > > &	ts
	)

inline

Construct from a list of (exponent-vector, coefficient) pairs.

Parameters

[in]	nvars	Number of variables.
[in]	ts	Term list.

Definition at line 836 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::add_to_coeff(), and Aleph::blossom_maximum_cardinality_matching().

◆ Gen_MultiPolynomial() [5/5]

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Gen_MultiPolynomial	(	const size_t	nvars,
		std::initializer_list< std::pair< Array< size_t >, Coefficient > >	ts
	)

inline

Construct from an initializer list of term pairs.

Parameters

[in]	nvars	Number of variables.
[in]	ts	Initializer list of {exponent-vector, coefficient}.

Definition at line 849 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::add_to_coeff(), and Aleph::blossom_maximum_cardinality_matching().

Member Function Documentation

◆ _append_unique()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static void Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_append_unique	(	Array< Coefficient > &	vals,
		const Coefficient &	value
	)

inlinestatic

Append value to vals if it is not already present.

Definition at line 3371 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), and value.

◆ _build_affine_factor()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_build_affine_factor	(	size_t	nvars,
		size_t	main_var,
		const Array< size_t > &	other_vars,
		const Array< Coefficient > &	base_eval_pts,
		const Array< Coefficient > &	slopes,
		const Coefficient &	base_root
	)

inlinestatic

Build a monic affine linear factor from root data.

Given root values of the kept variable at a base point and slopes for the remaining variables, constructs: x_main - (sum_i slope_i * x_i + intercept).

Definition at line 3592 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::add_to_coeff(), Aleph::blossom_maximum_cardinality_matching(), and Aleph::intercept().

◆ _build_affine_factor_from_linear_data()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_build_affine_factor_from_linear_data	(	size_t	nvars,
		size_t	main_var,
		const Array< size_t > &	other_vars,
		const Array< Coefficient > &	base_eval_pts,
		const Coefficient &	main_coeff,
		const Array< Coefficient > &	other_coeffs,
		const Coefficient &	base_constant_term
	)

inlinestatic

Build a primitive affine linear factor from specialized coefficients.

Given factors of the form \(a x_{\text{main}} + b(\mathbf{u})\)at a base specialization point, reconstructs:

\[ a x_{\text{main}} + \sum_i c_i u_i + d \]

where each \(c_i\)is the change in the specialized constant term after incrementing the corresponding variable by one.

Definition at line 3472 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::add_to_coeff(), Aleph::blossom_maximum_cardinality_matching(), and Aleph::intercept().

◆ _build_eval_point()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Array< Coefficient > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_build_eval_point	(	size_t	nvars,
		size_t	main_var,
		const Array< size_t > &	other_vars,
		const Array< Coefficient > &	coords
	)

inlinestatic

Build the full homomorphic-evaluation point from active-variable coordinates.

Definition at line 3794 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ _build_interpolation_grid()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_build_interpolation_grid	(	const Gen_MultiPolynomial< Coefficient, MonomOrder > &	p,
		const Array< size_t > &	other_vars,
		Coefficient	start,
		Coefficient	step,
		Array< Array< Coefficient > > &	grid,
		size_t &	total_points
	)

inlinestatic

Build a regular interpolation grid for the active non-main variables.

Definition at line 3742 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Array< T >::reserve(), and value.

◆ _collect_sorted_primitive_factor_groups()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_collect_sorted_primitive_factor_groups	(	const Gen_Polynomial< Coefficient > &	u,
		size_t	max_degree,
		Array< Array< Gen_Polynomial< Coefficient > > > &	groups
	)

inlinestatic

Expand, primitive-normalize, and group factors by degree in a stable order.

Definition at line 3858 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), cmp(), Aleph::in_place_sort(), and Aleph::size().

◆ _collect_sorted_primitive_linear_factors()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Array< Uni_Linear_Factor_Data > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_collect_sorted_primitive_linear_factors ( const Gen_Polynomial< Coefficient > & u )

inlinestatic

Collect primitive linear factors from a univariate factorization in stable order.

Definition at line 3400 of file tpl_multi_polynomial.H.

References Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), and m.

◆ _collect_unique_monic_linear_roots()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Array< Coefficient > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_collect_unique_monic_linear_roots ( const Gen_Polynomial< Coefficient > & u )

inlinestatic

Collect unique roots of monic linear factors from a univariate factorization.

Definition at line 3426 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ _count_active_vars()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static size_t Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_count_active_vars	(	const Gen_MultiPolynomial< Coefficient, MonomOrder > &	p,
		size_t &	last_active_var
	)

inlinestatic

Count active variables (positive degree) and remember the last one seen.

Definition at line 3449 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::count(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::degree_in(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::num_vars().

◆ _decode_grid_point()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Array< Coefficient > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_decode_grid_point	(	const Array< Array< Coefficient > > &	grid,
		size_t	flat_index
	)

inlinestatic

Decode a flat tensor-grid index into coordinates (last dimension fastest).

Definition at line 3779 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Array< T >::size().

◆ _divides_exactly()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_divides_exactly	(	const Gen_MultiPolynomial< Coefficient, MonomOrder > &	f,
		const Gen_MultiPolynomial< Coefficient, MonomOrder > &	divisor
	)

inlinestaticprivate

Test whether divisor divides f exactly over Z[x1,...,xn].

Uses the multivariate division algorithm directly and accepts the divisor only when the remainder is exactly zero.

Definition at line 4427 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::degree(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::divmod(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_zero(), and r.

◆ _embed_coeff_poly_as_x_term()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_embed_coeff_poly_as_x_term	(	const Gen_MultiPolynomial< Coefficient, MonomOrder > &	coeff_poly,
		size_t	nvars,
		size_t	main_var,
		const Array< size_t > &	other_vars,
		size_t	exp
	)

inlinestatic

Embed a coefficient polynomial in the ambient ring and multiply by x_main^exp.

Definition at line 3886 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::add_to_coeff(), Aleph::blossom_maximum_cardinality_matching(), and exp().

◆ _embed_univariate()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_embed_univariate	(	const Gen_Polynomial< Coefficient > &	u,
		size_t	nv,
		const size_t	x_var
	)

inlinestatic

Embed a univariate polynomial into the multivariate ring.

Parameters

[in]	u	Univariate polynomial.
[in]	nv	Number of variables in the target ring.
[in]	x_var	Variable index for the univariate variable.

Returns: Multivariate polynomial equivalent to u in variable x_var.

Definition at line 3356 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::add_to_coeff(), Aleph::blossom_maximum_cardinality_matching(), exp(), and Aleph::Gen_Polynomial< Coefficient >::for_each_term().

◆ _eval_index_for_var()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static size_t Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_eval_index_for_var	(	size_t	main_var,
		size_t	var
	)

inlinestaticnoexcept

Return the evaluation-array position corresponding to variable var.

Definition at line 3443 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ _eval_monomial()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Coefficient Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_eval_monomial	(	const Array< Coefficient > &	pt,
		const Array< size_t > &	alpha
	)

inlinestaticprivate

Evaluate a monomial \(x^\alpha\)at a point.

Definition at line 4380 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::multi_poly_detail::int_power(), and Aleph::Array< T >::size().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::fit(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::fit_ridge(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::fit_weighted().

◆ _exact_quotient()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_exact_quotient	(	const Gen_MultiPolynomial< Coefficient, MonomOrder > &	f,
		const Gen_MultiPolynomial< Coefficient, MonomOrder > &	divisor
	)

inlinestaticprivate

Compute exact quotient f / divisor over Z[x1,...,xn].

Uses the public multivariate division algorithm and returns the quotient only when the remainder vanishes exactly.

Definition at line 4447 of file tpl_multi_polynomial.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::divmod(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::num_vars(), and r.

◆ _expanded_univariate_factors()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Array< Gen_Polynomial< Coefficient > > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_expanded_univariate_factors ( const Gen_Polynomial< Coefficient > & u )

inlinestatic

Expand a univariate factorization into individual factors.

Definition at line 3806 of file tpl_multi_polynomial.H.

References Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), and m.

◆ _factorize_as_univariate_in_var()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static DynList< FactorTerm > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_factorize_as_univariate_in_var	(	const Gen_MultiPolynomial< Coefficient, MonomOrder > &	p,
		size_t	active_var
	)

inlinestatic

Factor a polynomial that is effectively univariate in one variable.

Projects the polynomial onto the active variable, delegates to the univariate integer factorizer, and embeds the factors back into the ambient multivariate ring while preserving multiplicities.

Definition at line 4048 of file tpl_multi_polynomial.H.

References Aleph::DynList< T >::append(), Aleph::blossom_maximum_cardinality_matching(), exp(), Aleph::Gen_Polynomial< Coefficient >::for_each_term(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::FactorTerm::multiplicity.

◆ _interpolated_factors_for_main_var()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Array< Gen_MultiPolynomial > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_interpolated_factors_for_main_var	(	const Gen_MultiPolynomial< Coefficient, MonomOrder > &	p,
		size_t	main_var,
		Coefficient	grid_start,
		Coefficient	grid_step
	)

inlinestatic

Reconstruct primitive factors by interpolation across specialization grids.

Factors are grouped by degree in the main variable and ordered deterministically by their univariate coefficient signatures at each specialization point. When that slot ordering remains consistent across the grid, each primitive factor can be interpolated back into the ambient ring and then verified by exact division.

Definition at line 3913 of file tpl_multi_polynomial.H.

References Aleph::and, Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), exp(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::interpolate(), and Aleph::size().

◆ _list_size()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

template<typename T >

static size_t Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_list_size ( const DynList< T > & lst )

inlinestaticprivate

Count elements in a DynList.

Definition at line 4414 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ _search_affine_lift_options()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_search_affine_lift_options	(	const Gen_MultiPolynomial< Coefficient, MonomOrder > &	p,
		size_t	main_var,
		const Array< size_t > &	other_vars,
		const Array< Array< Coefficient > > &	root_options,
		const Array< Coefficient > &	base_eval_pts,
		const Coefficient &	base_root,
		size_t	pos,
		Array< Coefficient > &	slopes,
		Gen_MultiPolynomial< Coefficient, MonomOrder > &	factor
	)

inlinestatic

Recursive search for an affine linear multivariate lift.

Definition at line 3626 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ _substitute_var()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_substitute_var	(	const Gen_MultiPolynomial< Coefficient, MonomOrder > &	p,
		size_t	var,
		const Coefficient &	val
	)

inlinestaticprivate

Substitute a single variable with a scalar value.

Definition at line 4394 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::add_to_coeff(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::for_each_term(), Aleph::multi_poly_detail::int_power(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_.

◆ _try_extract_affine_linear_factor()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_try_extract_affine_linear_factor	(	const Gen_MultiPolynomial< Coefficient, MonomOrder > &	p,
		Gen_MultiPolynomial< Coefficient, MonomOrder > &	factor
	)

inlinestatic

Try to extract a monic affine linear factor via multivariate lifting.

Definition at line 3712 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ _try_extract_interpolated_factor()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_try_extract_interpolated_factor	(	const Gen_MultiPolynomial< Coefficient, MonomOrder > &	p,
		Gen_MultiPolynomial< Coefficient, MonomOrder > &	factor
	)

inlinestatic

Try to extract an exact non-linear factor via coefficient interpolation.

Definition at line 4015 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ _try_lift_affine_linear_factor_for_main_var()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_try_lift_affine_linear_factor_for_main_var	(	const Gen_MultiPolynomial< Coefficient, MonomOrder > &	p,
		size_t	main_var,
		const Array< Coefficient > &	base_eval_pts,
		Gen_MultiPolynomial< Coefficient, MonomOrder > &	factor
	)

inlinestatic

Try to lift a monic affine linear factor for a fixed main variable.

Definition at line 3666 of file tpl_multi_polynomial.H.

References Aleph::and, Aleph::Array< T >::append(), and Aleph::blossom_maximum_cardinality_matching().

◆ _try_lift_primitive_affine_linear_factor_for_main_var()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_try_lift_primitive_affine_linear_factor_for_main_var	(	const Gen_MultiPolynomial< Coefficient, MonomOrder > &	p,
		size_t	main_var,
		const Array< Coefficient > &	base_eval_pts,
		Gen_MultiPolynomial< Coefficient, MonomOrder > &	factor
	)

inlinestatic

Try to lift a primitive affine linear factor from specialized coefficients.

Definition at line 3509 of file tpl_multi_polynomial.H.

References Aleph::and, Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), and Aleph::size().

◆ add_to_coeff()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

void Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::add_to_coeff	(	const Array< size_t > &	idx,
		const Coefficient &	delta
	)

inline

Add delta to the coefficient at idx.

Inserts the term if absent; removes it if the result is zero.

Parameters

[in]	idx	Exponent vector.
[in]	delta	Value to add.

Definition at line 1053 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeffs, and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::norm().

◆ autoreduce_groebner_basis()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Array< Gen_MultiPolynomial > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::autoreduce_groebner_basis ( Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > basis )

inlinestaticprivate

Definition at line 666 of file tpl_multi_polynomial.H.

References Aleph::and, Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::contains_equal_polynomial(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::divmod(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_zero(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::make_monic_inplace(), r, and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::remove_zero_and_duplicates().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::groebner_basis().

◆ autoreduced_generators()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Array< Gen_MultiPolynomial > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::autoreduced_generators ( const Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > & generators )

inlinestaticprivate

Definition at line 578 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::contains_equal_polynomial(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::divmod(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::make_monic_inplace(), and r.

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::groebner_basis().

◆ canonical_pair()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Pair_Key Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::canonical_pair	(	size_t	i,
		size_t	j
	)

inlinestaticprivatenoexcept

Definition at line 463 of file tpl_multi_polynomial.H.

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::enqueue_pair_if_needed(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::groebner_basis(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::lcm_pair_less(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::make_pair_candidate(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::pair_is_recorded(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::pop_best_pair().

◆ coeff_at()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Coefficient Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_at ( const Array< size_t > & idx ) const

inline

Read coefficient at a multi-index (0 if absent).

Parameters

[in] idx Exponent vector.

Returns: Stored coefficient, or Coefficient{} if the term is absent.

Definition at line 988 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeffs, and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::norm().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator==(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ coeff_is_zero()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero ( const Coefficient & c )

inlinestaticnoexcept

Test whether a coefficient is (approximately) zero.

Parameters

[in] c Coefficient to test.

Returns: True if c is zero (within epsilon for floats).

Definition at line 794 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::epsilon().

◆ contains_equal_polynomial()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::contains_equal_polynomial	(	const Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > &	basis,
		const Gen_MultiPolynomial< Coefficient, MonomOrder > &	p
	)

inlinestaticprivate

Definition at line 437 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::autoreduce_groebner_basis(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::autoreduced_generators(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::groebner_basis(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::remove_zero_and_duplicates().

◆ contains_ideal()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::contains_ideal	(	const Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > &	I_gens,
		const Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > &	J_gens
	)

inlinestatic

Test whether ideal I contains ideal J: I ⊇ J.

An ideal I contains ideal J if and only if every generator of J belongs to I. Uses a precomputed Gröbner basis of I for efficiency.

Parameters

[in]	I_gens	Generators of ideal I (non-empty, no zeros).
[in]	J_gens	Generators of ideal J (non-empty, no zeros).

Returns: True if I ⊇ J; false otherwise.

Exceptions

std::domain_error	if either ideal is empty or contains zero
std::invalid_argument	if nvars mismatch

Note: Complexity: O(Gröbner(I) + |J| · Div(f, GB_I)). Precomputes Gröbner basis of I once; does not call ideal_member in a loop to avoid redundant computation.; Available only for non-integral coefficient types because it relies on groebner_basis.

Definition at line 3067 of file tpl_multi_polynomial.H.

References ah_domain_error_if, ah_invalid_argument_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::divmod(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::groebner_basis(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_zero(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, and remainder().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::ideals_equal(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ content()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Coefficient Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::content ( ) const

inline

Content of a multivariate polynomial: GCD of all coefficients.

For \(f = \sum_\alpha c_\alpha x^\alpha\), the content is \(\gcd(c_{\alpha_1}, c_{\alpha_2}, \ldots)\).

For the zero polynomial, returns zero. The sign follows the leading coefficient so that primitive_part() has a positive leading coefficient.

Returns: The GCD of all coefficients.

Note: Only available for integral coefficient types.; Complexity: \(O(k \log M)\)where k = num_terms, M = max coeff.

Definition at line 3236 of file tpl_multi_polynomial.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeffs, Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_zero(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::leading_coeff().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::primitive_part(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ degree()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

size_t Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::degree ( ) const

inlinenoexcept

Total degree (maximum sum of exponents over all terms).

Returns: 0 for the zero or constant polynomial.

Definition at line 922 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeffs, and Aleph::multi_poly_detail::total_degree().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_divides_exactly(), main(), TEST(), TEST(), and TEST().

◆ degree_in()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

size_t Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::degree_in ( size_t var ) const

inlinenoexcept

Degree in a specific variable.

Parameters

[in] var Variable index (0-based).

Returns: Maximum exponent of var over all terms.

Definition at line 935 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeffs, and Aleph::Array< T >::size().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_count_active_vars(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::factorize(), and main().

◆ divide_scalar_inplace()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

void Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::divide_scalar_inplace ( const Coefficient & s )

inline

Divide every coefficient by s in place.

Parameters

[in] s Scalar divisor (must not be zero).

Exceptions

std::domain_error if s is zero.

Definition at line 1113 of file tpl_multi_polynomial.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeffs, and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::remove_zeros().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator/=().

◆ divmod()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

std::pair< Array< Gen_MultiPolynomial >, Gen_MultiPolynomial > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::divmod ( const Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > & divisors ) const

inline

Multivariate division with remainder (Buchberger algorithm).

Divides this polynomial by the array of divisors and returns quotients and remainder. Each divisor must be non-zero and have the same number of variables as this polynomial.

Parameters

[in] divisors Array of non-zero divisor polynomials.

Returns

Pair (quotients, remainder):

quotients[i]: quotient by divisors[i]
remainder: the polynomial remainder

Exceptions

std::domain_error	if divisors is empty or contains a zero polynomial
std::invalid_argument	if a non-zero divisor has mismatched nvars

Note: Complexity: O(terms(p) * s * terms(fi)) per outer iteration, where s = divisors.size() and terms(fi) = number of terms in divisors[i]. Requires Coefficient type to support division (/).; For integral coefficient types, a divisor only reduces a leading term when its leading coefficient divides exactly; otherwise that term is emitted to the remainder so the algorithm still makes progress.

Definition at line 2625 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Gen_MultiPolynomial(), ah_domain_error_if, ah_invalid_argument_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero(), Aleph::multi_poly_detail::divides_index(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_zero(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::leading_term(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::monomial(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, r, and Aleph::multi_poly_detail::sub_indices().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_divides_exactly(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_exact_quotient(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::autoreduce_groebner_basis(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::autoreduced_generators(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::contains_ideal(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::groebner_basis(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::reduce_modulo(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ enqueue_pair_if_needed()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static void Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::enqueue_pair_if_needed	(	Pair_Queue &	queue,
		Pair_Registry &	queued_pairs,
		const Pair_Candidate &	candidate,
		const Array< Array< size_t > > &	leading_monomials,
		Pair_Registry &	zero_pairs,
		const size_t	nvars
	)

inlinestaticprivate

Definition at line 552 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::canonical_pair(), Aleph::DynBinHeap< T, Compare >::insert(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::leading_monomials_coprime(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::pair_is_recorded(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::redundant_pair_by_chain_criterion().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::rebuild_groebner_pair_state().

◆ epsilon()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static constexpr Coefficient Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::epsilon ( )

inlinestaticconstexprnoexcept

Machine epsilon for floating-point coefficients.

Returns: 128 * numeric_limits::epsilon for floats, 0 for exact types.

Definition at line 782 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero().

◆ eval()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Coefficient Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::eval ( const Array< Coefficient > & pt ) const

inline

Evaluate at a point.

Parameters

[in] pt Array of values, one per variable.

Returns: \(p(v_0, \ldots, v_{n-1})\).

Exceptions

std::domain_error if pt has fewer elements than num_vars().

Definition at line 1395 of file tpl_multi_polynomial.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::for_each_term(), Aleph::multi_poly_detail::int_power(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, and Aleph::Array< T >::size().

Referenced by Aleph::analyze_fit(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::eval_batch(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::eval_hessian(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator()(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ eval_batch()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Array< Coefficient > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::eval_batch ( const Array< Array< Coefficient > > & pts ) const

inline

Evaluate polynomial at multiple points (with parallelism support).

Parameters

[in] pts Array of evaluation points.

Returns: Array of results, pts[i] → eval(pts[i]).

Note: Complexity: \(O(k \cdot n \cdot m)\) where k = num_terms, n = num_vars, m = pts.size().; Parallelism: Evaluation of points is parallelizable; uses thread pool if enabled.

Definition at line 2466 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::eval().

Referenced by TEST().

◆ eval_gradient()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Array< Coefficient > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::eval_gradient ( const Array< Coefficient > & pt ) const

inline

Evaluate gradient at a point.

Parameters

[in] pt Evaluation point (array of size >= num_vars).

Returns: Array of size num_vars containing gradient values.

Exceptions

std::domain_error if pt.size() < num_vars().

Note: Complexity: \(O(k \log k \cdot n + k \cdot n)\)(gradient computation + evaluation).

Definition at line 2129 of file tpl_multi_polynomial.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::gradient(), k, Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, and Aleph::Array< T >::size().

Referenced by TEST(), TEST(), and TEST().

◆ eval_hessian()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Array< Array< Coefficient > > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::eval_hessian ( const Array< Coefficient > & pt ) const

inline

Evaluate Hessian at a point.

Parameters

[in] pt Evaluation point (array of size >= num_vars).

Returns: \(n \times n\)matrix of Hessian values at pt.

Exceptions

std::domain_error if pt.size() < num_vars().

Note: Complexity: \(O(k \log k \cdot n^2 + k \cdot n^2)\)(Hessian computation + evaluation).

Definition at line 2150 of file tpl_multi_polynomial.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::eval(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::hessian(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, and Aleph::Array< T >::size().

Referenced by TEST(), and TEST().

◆ factor_recombination()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static DynList< FactorTerm > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::factor_recombination	(	Gen_MultiPolynomial< Coefficient, MonomOrder >	f,
		const Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > &	candidates
	)

inlinestatic

Factor recombination: find true factors from lifted candidates.

Given candidate factors from specialization-based lifting, tests exact divisibility against the current remainder and extracts any verified factors it finds.

Parameters

[in]	f	Polynomial to factor (primitive).
[in]	candidates	Array of candidate factors from Hensel lifting.

Returns: List of verified irreducible factors.

Note: This is intentionally conservative: it only accepts factors that divide exactly in the ambient polynomial ring.; Complexity: dominated by exact-divisibility checks against the candidate list.

Definition at line 4087 of file tpl_multi_polynomial.H.

References Aleph::and, Aleph::DynList< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_constant(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_zero(), k, Aleph::product(), and Aleph::HTList::size().

Referenced by TEST(), and TEST().

◆ factorize()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

DynList< FactorTerm > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::factorize ( ) const

inline

Main multivariate factorization over the integers.

Combines content extraction, exact affine/non-linear factor lifting from specializations, homomorphic evaluation (reduction to univariate), univariate factorization (Layer 5), and factor recombination to factor a multivariate polynomial over \(\mathbb{Z}\).

Algorithm outline:

Extract the scalar content and the primitive part.
Repeatedly extract exact factors from several specializations: affine linear factors directly, and some monic non-linear factors by interpolating their specialized coefficients on a tensor grid.
Choose a main variable and evaluation points for the rest.
Evaluate to obtain a univariate polynomial; factor it (Layer 5).
Recombine candidate factors by exact trial division.

Returns: A list of FactorTerm whose product reproduces the original polynomial exactly. If the scalar content is not one, it is emitted as a constant factor of multiplicity one.

Note: Only available for integral coefficient types.; Complexity: depends on the number of factors and degrees; specialization/interpolation lifting is heuristic, and recombination may still be exponential in the worst case.; For univariate polynomials (num_vars == 1), delegates to the univariate factorize() from Layer 5.; Every factor emitted is verified by exact division, but an unresolved residual factor should not be interpreted as a proof of irreducibility in the full multivariate integer ring.

Definition at line 4217 of file tpl_multi_polynomial.H.

References ah_domain_error_if, Aleph::and, Aleph::DynList< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::degree_in(), LocateFunctions< Container, Type >::get_it(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::homomorphic_eval(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_constant(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_zero(), and m.

Referenced by main(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ fit()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::fit	(	const Array< std::pair< Array< Coefficient >, Coefficient > > &	data,
		const size_t	nvars,
		const Array< Array< size_t > > &	basis
	)

inlinestatic

Basic least-squares polynomial fitting.

Minimizes: \(\sum_i (y_i - p(x_i))^2\)

Parameters

[in]	data	Array of (point, value) pairs.
[in]	nvars	Number of variables.
[in]	basis	Array of monomial exponent vectors (basis monomials).

Returns: Best-fit polynomial in least-squares sense.

Exceptions

std::domain_error if data or basis is empty, or normal equations singular.

Note: Complexity: \(O(m \cdot b^2 + b^3)\)where m=data points, b=basis size. For production: Use fit_weighted() for importance weighting support.

Definition at line 1608 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_eval_monomial(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::add_to_coeff(), ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero(), col, k, m, row, OhashCommon< HashTbl, Key >::size(), and y.

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ fit_parallel()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::fit_parallel	(	const Array< std::pair< Array< Coefficient >, Coefficient > > &	data,
		size_t	nvars,
		const Array< Array< size_t > > &	basis
	)

inlinestatic

Parallel least-squares fitting.

Builds design matrix rows in parallel; solves normal equations sequentially.

Parameters

[in]	data	Array of (point, value) pairs.
[in]	nvars	Number of variables.
[in]	basis	Array of monomial exponent vectors.

Returns: Best-fit polynomial.

Exceptions

std::domain_error if data/basis empty or normal equations singular.

Note: Complexity: \(O(m \cdot b / p + b^3)\)where m=data points, b=basis size, p=threads.; Parallelism applies to row construction; normal equations solved sequentially.

Definition at line 2492 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::add_to_coeff(), ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero(), col, Aleph::multi_poly_detail::eval_monomial(), k, m, Aleph::pmaps(), row, rows, OhashCommon< HashTbl, Key >::size(), and y.

Referenced by TEST().

◆ fit_ridge()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::fit_ridge	(	const Array< std::pair< Array< Coefficient >, Coefficient > > &	data,
		size_t	nvars,
		const Array< Array< size_t > > &	basis,
		Coefficient *	lambda_used = `nullptr`,
		double *	gcv_score = `nullptr`
	)

inlinestatic

Regularized least-squares fitting with automatic GCV-based lambda selection.

Solves Tikhonov ridge regression: \(\min_c ||Ac - y||^2 + \lambda ||c||^2\) Automatically selects \(\lambda\)via Generalized Cross-Validation (GCV).

Parameters

[in]	data	Array of (point, value) pairs.
[in]	nvars	Number of variables.
[in]	basis	Array of monomial exponent vectors (basis monomials).
[out]	lambda_used	If non-null, receives the selected regularization parameter.
[out]	gcv_score	If non-null, receives the GCV score at selected lambda.

Returns: Best-fit polynomial with ridge regularization.

Exceptions

std::domain_error if data/basis empty or normal equations singular.

Note: Use case: Ill-conditioned or noisy data. Automatic lambda selection via GCV. Complexity: \(O(m \cdot b^2 + b^3 + \text{trials})\)where m=data points, b=basis size. Reference: Golub & Kahan (1965), Wahba (1990).

Warning: The GCV implementation uses b (basis size) as an upper bound approximation for the effective degrees of freedom trace(A(A^T A + lambda I)^{-1}A^T). This can overestimate the trace for ill-conditioned systems or when b≈m. For higher accuracy, consider implementing exact trace computation or stochastic trace estimation (e.g., Hutchinson estimator).

Definition at line 1841 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_eval_monomial(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::add_to_coeff(), ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero(), col, k, m, pred, row, OhashCommon< HashTbl, Key >::size(), and y.

Referenced by TEST(), TEST(), TEST(), and TEST().

◆ fit_weighted()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::fit_weighted	(	const Array< std::pair< Array< Coefficient >, Coefficient > > &	data,
		size_t	nvars,
		const Array< Array< size_t > > &	basis,
		const Array< Coefficient > &	weights
	)

inlinestatic

Weighted least-squares polynomial fitting.

Production-grade fitting with per-point weights for importance-weighted regression. Minimizes: \(\sum_i w_i (y_i - p(x_i))^2\)

Parameters

[in]	data	Array of (point, value) pairs.
[in]	nvars	Number of variables.
[in]	basis	Array of monomial exponent vectors (basis monomials).
[in]	weights	Per-point weights (size must equal data.size()).

Returns: Best-fit polynomial in weighted least-squares sense.

Exceptions

std::domain_error if data/basis empty or weights size mismatch.

Note: Use case: Heteroscedastic data (varying measurement noise), importance-weighted samples, or robust fitting with outlier downweighting. Complexity: \(O(m \cdot b^2 + b^3)\)where m=data points, b=basis size.

Definition at line 1720 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_eval_monomial(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::add_to_coeff(), ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero(), col, k, m, row, OhashCommon< HashTbl, Key >::size(), and Aleph::Array< T >::size().

Referenced by TEST().

◆ for_each_term()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

template<class Op >

void Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::for_each_term ( Op && op ) const

inline

Visit every non-zero term in ascending monomial order.

Parameters

[in] op Callable void(const Array<size_t>&, const Coefficient&).

Definition at line 1002 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeffs.

◆ for_each_term_desc()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

template<class Op >

void Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::for_each_term_desc ( Op && op ) const

inline

Visit every non-zero term in descending monomial order.

Parameters

[in] op Callable void(const Array<size_t>&, const Coefficient&).

Definition at line 1015 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeffs, and Aleph::DynList< T >::insert().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::to_str().

◆ from_binary()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::from_binary ( std::istream & in )

inlinestatic

Deserialize polynomial from binary stream.

Reads format created by to_binary().

Parameters

[in] in Input stream.

Returns: Reconstructed polynomial.

Exceptions

std::ios_base::failure if read fails or format is invalid.

Definition at line 2423 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::add_to_coeff(), Aleph::blossom_maximum_cardinality_matching(), and exp().

Referenced by TEST(), and TEST().

◆ from_json()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::from_json ( const std::string & s )

inlinestatic

Deserialize from JSON.

Parses format created by to_json().

Parameters

[in] s JSON string.

Returns: Reconstructed polynomial.

Exceptions

std::domain_error	if JSON format is invalid.
std::invalid_argument	if coefficient conversion fails (from std::stod).
std::out_of_range	if coefficient value is out of range (from std::stod).

Note: This parser only supports the exact format produced by to_json().

Definition at line 2330 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::add_to_coeff(), ah_domain_error_if, Aleph::and, Aleph::blossom_maximum_cardinality_matching(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_.

Referenced by TEST(), and TEST().

◆ gradient()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Array< Gen_MultiPolynomial > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::gradient ( ) const

inline

Gradient vector: array of all first-order partial derivatives.

Returns: Array of size num_vars(), where element i is \(\frac{\partial p}{\partial x_i}\).

Note: Complexity: \(O(k \log k \cdot n)\)where k = num_terms, n = num_vars.

Definition at line 2087 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Gen_MultiPolynomial(), k, Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::partial().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::eval_gradient(), TEST(), TEST(), and TEST().

◆ groebner_basis()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Array< Gen_MultiPolynomial > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::groebner_basis ( const Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > & generators )

inlinestatic

Gröbner basis computation via Buchberger's algorithm.

Computes a Gröbner basis of the ideal generated by the input polynomials using a Buchberger-style algorithm with criterion B1 (coprime LMs), Buchberger's chain criterion for known-zero pairs, prioritized pair selection by lcm leading monomial, and incremental basis autoreduction whenever a new non-zero remainder is added. Generators are first made monic and autoreduced to remove exact duplicates and obvious ideal members before pair processing.

Parameters

[in] generators Array of generator polynomials (may contain zero).

Returns: A new array forming a Gröbner basis of the generated ideal.

Exceptions

std::domain_error	if generators is empty or contains zero polynomials
std::domain_error	if iteration limit (10000) is exceeded

Note: Complexity depends on ideal structure and may be exponential in degree. Pair processing uses a priority heap keyed by the lcm of leading monomials plus explicit zero-pair tracking, and the working basis is interreduced incrementally to curb redundant intermediate growth.; Available only for non-integral coefficient types because the implementation makes basis elements monic via coefficient division.; This is still a Buchberger-family implementation, not F4/F5. It is intended for exact field-like coefficient domains or numerically well-scaled floating workloads, not for truncated integral division semantics.

Definition at line 2751 of file tpl_multi_polynomial.H.

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::contains_ideal(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::ideal_member(), main(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::reduced_groebner_basis(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ hessian()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Array< Array< Gen_MultiPolynomial > > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::hessian ( ) const

inline

Hessian matrix: all second-order partial derivatives.

Returns: \(n \times n\)matrix (symmetric), where H[i][j] = \(\frac{\partial^2 p}{\partial x_i \partial x_j}\).

Note: Symmetry: H[i][j] == H[j][i] (Schwarz's theorem).; Complexity: \(O(k \log k \cdot n^2)\)where k = num_terms, n = num_vars.

Definition at line 2103 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Gen_MultiPolynomial(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::partial().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::eval_hessian(), TEST(), TEST(), TEST(), and TEST().

◆ homomorphic_eval()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_Polynomial< Coefficient > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::homomorphic_eval	(	size_t	keep_var,
		const Array< Coefficient > &	eval_pts
	)		const

inline

Homomorphic evaluation: reduce to univariate by substitution.

Substitutes all variables except keep_var with values from eval_pts, producing a univariate polynomial in \(x_{\text{keep\_var}}\).

Parameters

[in]	keep_var	Index of the variable to keep (0-based).
[in]	eval_pts	Array of size `num_vars()-1` with substitution values, ordered by variable index (skipping `keep_var`).

Returns: Univariate polynomial \(g(t) = f(a_0, \ldots, t, \ldots, a_{n-1})\).

Exceptions

std::domain_error	if `keep_var` >= num_vars().
std::domain_error	if `eval_pts.size()` != num_vars()-1.

Note: Complexity: \(O(k \cdot n)\)where k = num_terms, n = num_vars.

Definition at line 3319 of file tpl_multi_polynomial.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::for_each_term(), Aleph::Gen_Polynomial< Coefficient >::get_coeff(), Aleph::multi_poly_detail::int_power(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, and Aleph::Gen_Polynomial< Coefficient >::set_coeff().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::factorize(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ ideal_member()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::ideal_member	(	const Gen_MultiPolynomial< Coefficient, MonomOrder > &	f,
		const Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > &	generators
	)

inlinestatic

Test membership in an ideal via Gröbner basis.

A polynomial belongs to the ideal generated by the given generators if and only if its remainder modulo a Gröbner basis of the ideal is zero.

Parameters

[in]	f	Polynomial to test.
[in]	generators	Array of generator polynomials.

Returns: True if f is in the ideal; false otherwise.

Exceptions

std::domain_error	if generators is empty or contains zero polynomials
std::domain_error	if iteration limit is exceeded

Note: Complexity includes Gröbner basis computation, which is expensive. For repeated membership tests, precompute the Gröbner basis.; Available only for non-integral coefficient types because it relies on groebner_basis.

Definition at line 2909 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::groebner_basis().

Referenced by main(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::radical_member(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ ideal_power()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Array< Gen_MultiPolynomial > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::ideal_power	(	const Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > &	gens,
		size_t	n
	)

inlinestatic

Power of an ideal: I^n = I · I · ... · I (n times).

Computes the nth power of an ideal by repeated ideal multiplication. Special cases: I^0 = ⟨1⟩ (the unit ideal), I^1 = I.

Parameters

[in]	gens	Generator polynomials (non-empty, no zeros).
[in]	n	Exponent (non-negative integer).

Returns: Array of generators for I^n.

Exceptions

std::domain_error if gens is empty or contains zero

Note: Complexity: O(n · |gens|^k · T_mult) accumulated. Result size grows as |gens|^n. Use only for small n and |gens| to avoid exponential explosion.

Warning: Result array size can be exponential in n.

Definition at line 3021 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Gen_MultiPolynomial(), ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::ideal_product(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_zero().

Referenced by TEST(), TEST(), TEST(), TEST(), and TEST().

◆ ideal_product()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Array< Gen_MultiPolynomial > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::ideal_product	(	const Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > &	a,
		const Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > &	b
	)

inlinestatic

Product of two ideals: I · J = ⟨a_i · b_j : a_i ∈ I, b_j ∈ J⟩.

Computes all pairwise products of generators from two ideals. The result is a set of |a| × |b| polynomials (may contain duplicates).

Parameters

[in]	a	First ideal generators (non-empty, no zeros).
[in]	b	Second ideal generators (non-empty, no zeros).

Returns: Array of size(a) × size(b) containing products a_i · b_j.

Exceptions

std::domain_error	if `a` or `b` is empty
std::domain_error	if any generator is zero
std::invalid_argument	if nvars mismatch

Note: Complexity: O(|a| · |b| · T_mult). Result may grow large for large inputs.

Definition at line 2978 of file tpl_multi_polynomial.H.

References ah_domain_error_if, ah_invalid_argument_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_zero(), k, Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, and Aleph::Array< T >::size().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::ideal_power(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ ideal_sum()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Array< Gen_MultiPolynomial > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::ideal_sum	(	const Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > &	a,
		const Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > &	b
	)

inlinestatic

Sum of two ideals: I + J = ⟨generators(I) ∪ generators(J)⟩.

Concatenates the generators of two ideals to form their sum. No Gröbner computation is performed; the result is the union of generators.

Parameters

[in]	a	First ideal generators (non-empty, no zeros).
[in]	b	Second ideal generators (non-empty, no zeros).

Returns: Array of size(a) + size(b) containing all generators.

Exceptions

std::domain_error	if `a` or `b` is empty
std::domain_error	if any generator in `a` or `b` is zero
std::invalid_argument	if nvars mismatch between `a` and `b`

Note: Complexity: O(n + m). No reduction applied.

Definition at line 2935 of file tpl_multi_polynomial.H.

References ah_domain_error_if, ah_invalid_argument_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_zero(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, and Aleph::Array< T >::size().

Referenced by TEST(), TEST(), TEST(), TEST(), and TEST().

◆ ideals_equal()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::ideals_equal	(	const Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > &	I_gens,
		const Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > &	J_gens
	)

inlinestatic

Test equality of two ideals: I = J.

Two ideals are equal if and only if each contains the other. Equivalent to: contains_ideal(I, J) && contains_ideal(J, I).

Parameters

[in]	I_gens	Generators of ideal I (non-empty, no zeros).
[in]	J_gens	Generators of ideal J (non-empty, no zeros).

Returns: True if I = J; false otherwise.

Exceptions

std::domain_error	if either ideal is empty or contains zero
std::invalid_argument	if nvars mismatch

Note: Complexity: O(2 × contains_ideal). May be expensive for large ideals.; Available only for non-integral coefficient types because it relies on Gröbner-basis ideal containment.

Definition at line 3119 of file tpl_multi_polynomial.H.

References ah_domain_error_if, ah_invalid_argument_if, Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::contains_ideal(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_zero(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_.

Referenced by TEST(), TEST(), TEST(), TEST(), and TEST().

◆ interpolate()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::interpolate	(	const Array< Array< Coefficient > > &	grid,
		const Array< Coefficient > &	values,
		size_t	nvars
	)

inlinestatic

Multivariate interpolation via Newton divided differences (Chung-Yao).

Constructs a polynomial that passes through all points in a tensor-product grid. Uses dimension-by-dimension Newton divided-differences table.

Parameters

[in]	grid	Array of size num_vars; grid[d] is array of nodes in dimension d (must be distinct).
[in]	values	Array of function values on the grid (must have size = product of grid sizes).
[in]	nvars	Number of variables.

Returns: Interpolating polynomial of total degree \(\prod_d (\text{size}_d - 1)\).

Exceptions

std::domain_error if grid sizes don't match data size, or duplicate nodes found.

Note: Algorithm: Chung-Yao (1977) — Newton divided-differences applied per dimension.; Complexity: \(O\left( n \cdot \prod_d m_d^2 \right)\)where n=nvars, m_d=grid[d].size().; Grid order: values are in row-major (rightmost dimension varies fastest).

Definition at line 2184 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Gen_MultiPolynomial(), ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero(), dim(), m, nodes, Aleph::Array< T >::size(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::variable().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_interpolated_factors_for_main_var(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ is_constant()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_constant ( ) const

inlinenoexcept

True if constant or zero (total degree 0).

Definition at line 898 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeffs, and Aleph::multi_poly_detail::is_zero_index().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::factor_recombination(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::factorize(), main(), TEST(), TEST(), and TEST().

◆ is_zero()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_zero ( ) const

inlinenoexcept

True if this is the zero polynomial.

Definition at line 892 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeffs.

◆ lcm_pair_less()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::lcm_pair_less	(	const Pair_Candidate &	lhs,
		const Pair_Candidate &	rhs
	)

inlinestaticprivate

Definition at line 476 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::canonical_pair(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Pair_Candidate::i, Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Pair_Candidate::j, Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Pair_Candidate::lcm, and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Pair_Candidate::lcm_degree.

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Pair_Candidate_Less::operator()().

◆ leading_coeff()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Coefficient Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::leading_coeff ( ) const

inline

Leading coefficient.

Returns: Coefficient of the leading term.

Exceptions

std::domain_error if the polynomial is zero.

Definition at line 966 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::leading_term().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::content(), and main().

◆ leading_monomial()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Array< size_t > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::leading_monomial ( ) const

inline

Leading monomial (exponent vector of the leading term).

Returns: Multi-index of the leading term.

Exceptions

std::domain_error if the polynomial is zero.

Definition at line 975 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::leading_term().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::minimize_groebner_basis().

◆ leading_monomials_coprime()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::leading_monomials_coprime	(	const Array< size_t > &	a,
		const Array< size_t > &	b,
		const size_t	nvars
	)

inlinestaticprivatenoexcept

Definition at line 446 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::enqueue_pair_if_needed(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::groebner_basis().

◆ leading_term()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

std::pair< Array< size_t >, Coefficient > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::leading_term ( ) const

inline

Leading term (largest monomial in the ordering).

Returns: Pair (exponent vector, coefficient).

Exceptions

std::domain_error if the polynomial is zero.

Definition at line 955 of file tpl_multi_polynomial.H.

References ah_domain_error_if, Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeffs, Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_zero(), and m.

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::divmod(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::leading_coeff(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::leading_monomial(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ make_monic_inplace()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static void Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::make_monic_inplace ( Gen_MultiPolynomial< Coefficient, MonomOrder > & p )

inlinestaticprivate

Definition at line 426 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::autoreduce_groebner_basis(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::autoreduced_generators(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::groebner_basis(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::reduced_groebner_basis().

◆ make_pair_candidate()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Pair_Candidate Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::make_pair_candidate	(	size_t	i,
		size_t	j,
		const Array< Array< size_t > > &	leading_monomials,
		size_t	nvars
	)

inlinestaticprivate

Definition at line 510 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::canonical_pair(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Pair_Candidate::i, Aleph::multi_poly_detail::lcm_indices(), and Aleph::multi_poly_detail::total_degree().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::rebuild_groebner_pair_state().

◆ minimize_groebner_basis()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Array< Gen_MultiPolynomial > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::minimize_groebner_basis ( Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > basis )

inlinestaticprivate

Definition at line 607 of file tpl_multi_polynomial.H.

References Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::multi_poly_detail::divides_index(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::leading_monomial(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_.

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::reduced_groebner_basis().

◆ monomial()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::monomial	(	size_t	nvars,
		const Array< size_t > &	idx,
		const Coefficient &	c = `Coefficient(1)`
	)

inlinestatic

A single monomial \(c \, x^{\alpha}\).

Parameters

[in]	nvars	Number of variables.
[in]	idx	Exponent vector \(\alpha\).
[in]	c	Coefficient (default 1).

Returns: The monomial \(c \, x_0^{\alpha_0} \cdots x_{n-1}^{\alpha_{n-1}}\).

Definition at line 880 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Gen_MultiPolynomial(), and Aleph::blossom_maximum_cardinality_matching().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::divmod(), main(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::radical_member(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::s_poly(), and TEST().

◆ norm()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Array< size_t > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::norm ( const Array< size_t > & idx ) const

inlineprivate

Pad an index to nvars_ trailing zeros.

Definition at line 421 of file tpl_multi_polynomial.H.

References Aleph::multi_poly_detail::extend_index(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_.

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Gen_MultiPolynomial(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::add_to_coeff(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_at().

◆ num_terms()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

size_t Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::num_terms ( ) const

inlinenoexcept

Number of non-zero terms.

Definition at line 914 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeffs.

Referenced by main(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator*(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator==(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::to_binary().

◆ num_vars()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

size_t Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::num_vars ( ) const

inlinenoexcept

Number of variables.

Definition at line 908 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_.

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_count_active_vars(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_exact_quotient(), main(), Aleph::operator-(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ operator!=()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator!= ( const Gen_MultiPolynomial< Coefficient, MonomOrder > & q ) const

inline

Polynomial inequality.

Definition at line 1453 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ operator()()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Coefficient Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator() ( const Array< Coefficient > & pt ) const

inline

Evaluate at a point (function-call syntax).

Parameters

[in] pt Array of values.

Returns: \(p(\text{pt})\).

Exceptions

std::domain_error if pt has fewer elements than num_vars().

Definition at line 1423 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::eval().

◆ operator*() [1/2]

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator* ( const Coefficient & s ) const

inline

Multiply by a scalar.

Parameters

[in] s Scalar.

Returns: Scaled polynomial.

Definition at line 1308 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Gen_MultiPolynomial(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::for_each_term(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, and r.

◆ operator*() [2/2]

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator* ( const Gen_MultiPolynomial< Coefficient, MonomOrder > & q ) const

inline

Polynomial multiplication.

Parameters

[in] q Multiplicand.

Returns: Product \(\text{this} \cdot q\).

Note: Complexity: \(O(k_1 k_2 \log(k_1 k_2))\) where \(k_i\)is the number of terms.

Definition at line 1259 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Gen_MultiPolynomial(), Aleph::multi_poly_detail::add_indices(), Aleph::blossom_maximum_cardinality_matching(), Aleph::multi_poly_detail::extend_index(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::for_each_term(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_zero(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::num_terms(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, and r.

◆ operator*=() [1/2]

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_MultiPolynomial & Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator*= ( const Coefficient & s )

inline

In-place scalar multiplication.

Parameters

[in] s Scalar.

Returns: Reference to *this.

Definition at line 1327 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::scale_inplace().

◆ operator*=() [2/2]

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_MultiPolynomial & Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator*= ( const Gen_MultiPolynomial< Coefficient, MonomOrder > & q )

inline

In-place polynomial multiplication.

Parameters

[in] q Multiplicand.

Returns: Reference to *this.

Definition at line 1294 of file tpl_multi_polynomial.H.

◆ operator+() [1/2]

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator+ ( const Coefficient & s ) const

inline

Add a scalar constant term.

Parameters

[in] s Scalar addend.

Returns: Polynomial plus the constant s.

Definition at line 1165 of file tpl_multi_polynomial.H.

References r.

◆ operator+() [2/2]

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator+ ( const Gen_MultiPolynomial< Coefficient, MonomOrder > & q ) const

inline

Polynomial addition.

Parameters

[in] q Addend.

Returns: Sum \(\text{this} + q\).

Definition at line 1134 of file tpl_multi_polynomial.H.

References r.

◆ operator+=() [1/2]

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_MultiPolynomial & Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator+= ( const Coefficient & s )

inline

In-place addition of a scalar constant term.

Parameters

[in] s Scalar addend.

Returns: Reference to *this.

Definition at line 1176 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::add_to_coeff(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_.

◆ operator+=() [2/2]

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_MultiPolynomial & Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator+= ( const Gen_MultiPolynomial< Coefficient, MonomOrder > & q )

inline

In-place addition.

Parameters

[in] q Addend.

Returns: Reference to *this.

Definition at line 1145 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::add_to_coeff(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::for_each_term(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::scale_inplace().

◆ operator-() [1/3]

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator- ( ) const

inline

Unary negation.

Returns: \(-p\).

Definition at line 1237 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::for_each_term(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, and r.

◆ operator-() [2/3]

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator- ( const Coefficient & s ) const

inline

Subtract a scalar constant term.

Parameters

[in] s Scalar subtrahend.

Returns: Polynomial minus the constant s.

Definition at line 1217 of file tpl_multi_polynomial.H.

References r.

◆ operator-() [3/3]

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator- ( const Gen_MultiPolynomial< Coefficient, MonomOrder > & q ) const

inline

Polynomial subtraction.

Parameters

[in] q Subtrahend.

Returns: Difference \(\text{this} - q\).

Definition at line 1186 of file tpl_multi_polynomial.H.

References r.

◆ operator-=() [1/2]

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_MultiPolynomial & Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator-= ( const Coefficient & s )

inline

In-place subtraction of a scalar constant term.

Parameters

[in] s Scalar subtrahend.

Returns: Reference to *this.

Definition at line 1228 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::add_to_coeff(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_.

◆ operator-=() [2/2]

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_MultiPolynomial & Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator-= ( const Gen_MultiPolynomial< Coefficient, MonomOrder > & q )

inline

In-place subtraction.

Parameters

[in] q Subtrahend.

Returns: Reference to *this.

Definition at line 1197 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::add_to_coeff(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeffs, Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::for_each_term(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_.

◆ operator/()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator/ ( const Coefficient & s ) const

inline

Divide by a scalar.

Parameters

[in] s Scalar divisor (must not be zero).

Returns: Quotient polynomial.

Exceptions

std::domain_error if s is zero.

Definition at line 1338 of file tpl_multi_polynomial.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::for_each_term(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, and r.

◆ operator/=()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_MultiPolynomial & Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator/= ( const Coefficient & s )

inline

In-place scalar division.

Parameters

[in] s Scalar divisor (must not be zero).

Returns: Reference to *this.

Exceptions

std::domain_error if s is zero.

Definition at line 1358 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::divide_scalar_inplace().

◆ operator==()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator== ( const Gen_MultiPolynomial< Coefficient, MonomOrder > & q ) const

inline

Polynomial equality.

Parameters

[in] q Other polynomial.

Returns: True iff all non-zero terms coincide (within epsilon for floats).

Definition at line 1436 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_at(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero(), Aleph::eq(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::for_each_term(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::num_terms().

◆ pair_is_recorded()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::pair_is_recorded	(	const Pair_Registry &	pairs,
		size_t	i,
		size_t	j
	)

inlinestaticprivate

Definition at line 500 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::canonical_pair(), and Aleph::DynMapTree< Key, Data, Tree, Compare >::contains().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::enqueue_pair_if_needed(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::pair_is_zero_known().

◆ pair_is_zero_known()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::pair_is_zero_known	(	const Pair_Registry &	zero_pairs,
		size_t	i,
		size_t	j
	)

inlinestaticprivate

Definition at line 505 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::pair_is_recorded().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::redundant_pair_by_chain_criterion().

◆ partial()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::partial	(	size_t	var,
		size_t	n = `1`
	)		const

inline

Partial derivative with respect to a variable.

Computes \(\frac{\partial^n p}{\partial x_{\text{var}}^n}\) using the falling factorial rule.

Parameters

[in]	var	Variable index (0-based).
[in]	n	Order of derivative (default 1).

Returns: Partial derivative polynomial.

Exceptions

std::domain_error if var >= num_vars().

Algorithm:: For each term \(c \cdot x^\alpha\), replace with
\[ c \cdot \alpha_{\text{var}}^{\underline{n}} \cdot x^{\alpha - n \cdot e_{\text{var}}} \]
where \(\alpha^{\underline{n}}\) is the falling factorial.

Complexity:: \(O(k \log k)\) where k = num_terms.

Definition at line 2056 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::add_to_coeff(), ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero(), Aleph::multi_poly_detail::decrement_index_at(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::for_each_term(), k, and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_.

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::gradient(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::hessian(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ pop_best_pair()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Pair_Candidate Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::pop_best_pair	(	Pair_Queue &	queue,
		Pair_Registry &	queued_pairs
	)

inlinestaticprivate

Definition at line 543 of file tpl_multi_polynomial.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::canonical_pair(), Aleph::DynBinHeap< T, Compare >::getMin(), and Aleph::GenBinHeap< NodeType, Key, Compare >::is_empty().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::groebner_basis().

◆ pow()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::pow ( size_t n ) const

inline

Exponentiation \(p^n\)by repeated squaring.

Parameters

[in] n Exponent.

Returns: \(p^n\). Returns the constant 1 (with same num_vars) if n == 0.

Definition at line 1372 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_.

Referenced by main(), TEST(), TEST(), TEST(), and TEST().

◆ primitive_part()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::primitive_part ( ) const

inline

Primitive part: polynomial divided by its content.

Returns \(f / \text{content}(f)\). The result has \(\gcd\)of coefficients equal to 1 and positive leading coefficient.

Returns: Primitive polynomial, or the zero polynomial if is_zero().

Note: Only available for integral coefficient types.; Complexity: \(O(k \log M)\)for content + \(O(k)\)division.

Definition at line 3272 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Gen_MultiPolynomial(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeffs, Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::content(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::for_each_term(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_zero(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, and r.

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ promote()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::promote ( size_t new_nv ) const

inline

Promote to a polynomial with more variables.

All existing terms are padded with trailing-zero exponents.

Parameters

[in] new_nv New number of variables (>= current num_vars).

Returns: Promoted polynomial.

Exceptions

std::domain_error if new_nv < num_vars().

Definition at line 1573 of file tpl_multi_polynomial.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::multi_poly_detail::extend_index(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::for_each_term(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, and r.

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::radical_member(), and TEST().

◆ radical_member()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::radical_member	(	const Gen_MultiPolynomial< Coefficient, MonomOrder > &	f,
		const Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > &	gens
	)

inlinestatic

Test membership in radical of ideal: f ∈ √I.

Uses the Rabinowitsch trick: f ∈ √I (radical of I in k[x₀,...,x_{n−1}]) if and only if 1 ∈ I + ⟨1 − y·f⟩ in k[x₀,...,x_{n−1}, y]. Returns true if the augmented ideal contains 1.

Parameters

[in]	f	Polynomial to test (nvars must match generators if non-zero).
[in]	gens	Generators of ideal I (non-empty, no zeros).

Returns: True if f ∈ √I; false otherwise.

Exceptions

std::domain_error	if `gens` is empty or contains zero
std::invalid_argument	if f is non-zero with mismatched nvars

Note: Complexity: O(Gröbner(I + ⟨1−y·f⟩)) in augmented ring with nv+1 variables. The zero polynomial always belongs to any radical.

Warning: Rabinowitsch computation can be expensive due to the augmented ideal.

Note: Available only for non-integral coefficient types because it reduces ideal membership to Gröbner-basis computations.

Definition at line 3163 of file tpl_multi_polynomial.H.

References ah_domain_error_if, ah_invalid_argument_if, Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::ideal_member(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_zero(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::monomial(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::promote().

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ rebuild_groebner_pair_state()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static void Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::rebuild_groebner_pair_state	(	const Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > &	basis,
		Array< Array< size_t > > &	leading_monomials,
		Pair_Queue &	queue,
		Pair_Registry &	queued_pairs,
		Pair_Registry &	zero_pairs
	)

inlinestaticprivate

Definition at line 738 of file tpl_multi_polynomial.H.

References Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::enqueue_pair_if_needed(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::make_pair_candidate(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_.

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::groebner_basis().

◆ reduce_modulo()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::reduce_modulo ( const Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > & divisors ) const

inline

Polynomial reduction modulo an ideal (one-liner).

Reduces this polynomial modulo a set of divisor polynomials by computing the division remainder.

Parameters

[in] divisors Array of divisor polynomials.

Returns: The remainder after division by divisors.

Exceptions

std::domain_error if divisors is empty

Note: Equivalent to divmod(divisors).second.

Definition at line 2889 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::divmod().

Referenced by main(), TEST(), TEST(), TEST(), and TEST().

◆ reduced_groebner_basis()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Array< Gen_MultiPolynomial > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::reduced_groebner_basis ( const Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > & generators )

inlinestatic

Reduced Gröbner basis (minimized and normalized).

Computes a Gröbner basis and then reduces it by:

Removing redundant generators (whose LM is divisible by another's LM)
Making each generator monic (leading coefficient = 1)
Interreducing each generator w.r.t. the others

Parameters

[in] generators Array of generator polynomials.

Returns: A reduced Gröbner basis: minimal, monic, and pairwise interreduced.

Exceptions

std::domain_error	if generators is empty or contains zero polynomials
std::domain_error	if iteration limit is exceeded

Note: The basis elements are pairwise coprime in leading monomials.; Available only for non-integral coefficient types because it depends on groebner_basis.

Definition at line 2840 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::groebner_basis(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::make_monic_inplace(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::minimize_groebner_basis(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, r, and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::remove_zero_and_duplicates().

Referenced by main(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ redundant_pair_by_chain_criterion()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static bool Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::redundant_pair_by_chain_criterion	(	const Pair_Candidate &	candidate,
		const Array< Array< size_t > > &	leading_monomials,
		const Pair_Registry &	zero_pairs,
		const size_t	nvars
	)

inlinestaticprivate

Definition at line 522 of file tpl_multi_polynomial.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::multi_poly_detail::divides_index(), k, and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::pair_is_zero_known().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::enqueue_pair_if_needed(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::groebner_basis().

◆ remove_zero_and_duplicates()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Array< Gen_MultiPolynomial > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::remove_zero_and_duplicates ( const Array< Gen_MultiPolynomial< Coefficient, MonomOrder > > & basis )

inlinestaticprivate

Definition at line 651 of file tpl_multi_polynomial.H.

References Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::contains_equal_polynomial(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_zero().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::autoreduce_groebner_basis(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::reduced_groebner_basis().

◆ remove_zeros()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

void Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::remove_zeros ( )

inline

Remove all terms whose coefficient is approximately zero.

Definition at line 1071 of file tpl_multi_polynomial.H.

References Aleph::DynList< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeffs, and k.

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::divide_scalar_inplace(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::scale_inplace().

◆ s_poly()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::s_poly	(	const Gen_MultiPolynomial< Coefficient, MonomOrder > &	f,
		const Gen_MultiPolynomial< Coefficient, MonomOrder > &	g
	)

inlinestatic

S-polynomial (Sylvester polynomial) of two polynomials.

Computes the S-polynomial used in Buchberger's algorithm: S(f, g) = (lcm(lm(f), lm(g)) / lm(f)) * f - (lcm(lm(f), lm(g)) / lm(g)) * g

Parameters

[in]	f	First polynomial (non-zero).
[in]	g	Second polynomial (non-zero).

Returns: The S-polynomial S(f, g).

Exceptions

std::domain_error	if `f` or `g` is zero
std::invalid_argument	if f and g have different number of variables

Note: The result may be zero if f and g have coprime leading monomials.; Available only for non-integral coefficient types because the implementation scales by inverse leading coefficients.

Definition at line 2700 of file tpl_multi_polynomial.H.

References ah_domain_error_if, ah_invalid_argument_if, Aleph::blossom_maximum_cardinality_matching(), gamma(), Aleph::multi_poly_detail::lcm_indices(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::monomial(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, and Aleph::multi_poly_detail::sub_indices().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::groebner_basis(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ scale_inplace()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

void Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::scale_inplace ( const Coefficient & s )

inline

Multiply every coefficient by s in place.

Parameters

[in] s Scalar.

Definition at line 1089 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeffs, and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::remove_zeros().

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator*=(), and Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::operator+=().

◆ terms()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

DynList< std::pair< Array< size_t >, Coefficient > > Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::terms ( ) const

inline

All terms as a list (ascending order).

Returns: DynList of (exponent-vector, coefficient) pairs.

Definition at line 1032 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::for_each_term(), and r.

Referenced by TEST().

◆ to_binary()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

void Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::to_binary ( std::ostream & out ) const

inline

Serialize polynomial to binary stream.

Format: nvars (uint64) | n_terms (uint64) | ( exponents (uint64×nvars) | coeff (double) )×n_terms

Parameters

[out] out Output stream.

Exceptions

std::ios_base::failure if write fails.

Definition at line 2394 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), exp(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::for_each_term(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::num_terms(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, and out.

Referenced by TEST(), and TEST().

◆ to_json()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

std::string Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::to_json ( ) const

inline

Serialize polynomial to JSON string.

Format: {"nvars":n,"terms":[{"e":[...exponents...],"c":coeff},...]}.

Returns: JSON string representation.

Note: Precision: Coefficients saved with 17 significant digits (IEEE 754 double).

Definition at line 2294 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::for_each_term(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, and Aleph::Array< T >::size().

Referenced by TEST(), and TEST().

◆ to_str()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

std::string Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::to_str ( const DynList< std::string > & names = DynList<std::string>() ) const

inline

Human-readable string.

Uses variable names x, y, z for up to 3 variables, or x0, x1, ... for more. Custom names can be supplied via names.

Parameters

[in] names Optional variable-name list.

Returns: String such as "3*x^2*y - 2".

Definition at line 1470 of file tpl_multi_polynomial.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeff_is_zero(), FunctionalMethods< Container, T >::for_each(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::for_each_term_desc(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::is_zero(), Aleph::multi_poly_detail::is_zero_index(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_, and Aleph::Array< T >::size().

Referenced by main(), Aleph::operator<<(), print_result(), TEST(), and TEST().

◆ variable()

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

static Gen_MultiPolynomial Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::variable	(	size_t	nvars,
		const size_t	var
	)

inlinestatic

The polynomial \(x_i\)(a single variable).

Parameters

[in]	nvars	Number of variables.
[in]	var	Variable index (0-based).

Returns: Polynomial whose only term is \(x_{\text{var}}\).

Definition at line 866 of file tpl_multi_polynomial.H.

References Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::Gen_MultiPolynomial(), ah_domain_error_if, and Aleph::blossom_maximum_cardinality_matching().

Member Data Documentation

◆ coeffs

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

DynMapTree<Array<size_t>, Coefficient, Avl_Tree, MonomOrder> Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::coeffs

private

Definition at line 418 of file tpl_multi_polynomial.H.

◆ nvars_

template<typename Coefficient = double, class MonomOrder = Grevlex_Order>

size_t Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::nvars_ = 0

private

Definition at line 416 of file tpl_multi_polynomial.H.

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

tpl_multi_polynomial.H

Classes

Public Types

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Coeff

◆ Index

◆ Order

◆ Pair_Key

◆ Pair_Queue

◆ Pair_Registry

Constructor & Destructor Documentation

◆ Gen_MultiPolynomial() [1/5]

◆ Gen_MultiPolynomial() [2/5]

◆ Gen_MultiPolynomial() [3/5]

◆ Gen_MultiPolynomial() [4/5]

◆ Gen_MultiPolynomial() [5/5]

Member Function Documentation

◆ _append_unique()

◆ _build_affine_factor()

◆ _build_affine_factor_from_linear_data()

◆ _build_eval_point()

◆ _build_interpolation_grid()

◆ _collect_sorted_primitive_factor_groups()

◆ _collect_sorted_primitive_linear_factors()

◆ _collect_unique_monic_linear_roots()

◆ _count_active_vars()

◆ _decode_grid_point()

◆ _divides_exactly()

◆ _embed_coeff_poly_as_x_term()

◆ _embed_univariate()

◆ _eval_index_for_var()

◆ _eval_monomial()

◆ _exact_quotient()

◆ _expanded_univariate_factors()

◆ _factorize_as_univariate_in_var()

◆ _interpolated_factors_for_main_var()

◆ _list_size()

◆ _search_affine_lift_options()

◆ _substitute_var()

◆ _try_extract_affine_linear_factor()

◆ _try_extract_interpolated_factor()

◆ _try_lift_affine_linear_factor_for_main_var()

◆ _try_lift_primitive_affine_linear_factor_for_main_var()

◆ add_to_coeff()

◆ autoreduce_groebner_basis()

◆ autoreduced_generators()

◆ canonical_pair()

◆ coeff_at()

◆ coeff_is_zero()

◆ contains_equal_polynomial()

◆ contains_ideal()

◆ content()

◆ degree()

◆ degree_in()

◆ divide_scalar_inplace()

◆ divmod()

◆ enqueue_pair_if_needed()

◆ epsilon()

◆ eval()

◆ eval_batch()

◆ eval_gradient()

◆ eval_hessian()

◆ factor_recombination()

◆ factorize()

◆ fit()

◆ fit_parallel()

◆ fit_ridge()

◆ fit_weighted()

◆ for_each_term()

◆ for_each_term_desc()

◆ from_binary()

◆ from_json()

◆ gradient()

◆ groebner_basis()