PolynomialRoots Namespace Reference

Classes
class	CubicT
class	QuadraticT
class	QuarticT
class	real_complex
	Lightweight complex number type used by the standard-precision solvers. More...

Typedefs
using	real_type = double
	Scalar type used by the standard-precision API.
using	integer = int
	Integer type used for degrees, counts and indices.
using	ostream_type = std::basic_ostream<char>
	Output stream type used by diagnostic methods.
using	istream_type = std::basic_istream<char>
	Input stream type reserved for formatted input helpers.
using	Quadratic = QuadraticT<real_type, real_complex>
using	Cubic = CubicT<real_type, real_complex>
using	Quartic = QuarticT<real_type, real_complex>

Functions
template<typename T_real>
T_real	thirdT ()
template<typename T_real>
T_real	one27thT ()
template<typename T_real>
T_real	two27thT ()
real_complex	operator+ (real_complex const &a, real_complex const &b)
	Return the sum of two standard-precision complex values.
real_complex	operator+ (real_complex const &a, real_type b)
	Return the sum of a standard-precision complex value and a real scalar.
real_complex	operator+ (real_type a, real_complex const &b)
	Return the sum of a real scalar and a standard-precision complex value.
real_complex	operator- (real_complex const &a, real_complex const &b)
	Return the difference of two standard-precision complex values.
real_complex	operator- (real_complex const &a, real_type b)
	Return the difference between a standard-precision complex value and a real scalar.
real_complex	operator- (real_type a, real_complex const &b)
	Return the difference between a real scalar and a standard-precision complex value.
real_complex	operator- (real_complex const &a)
	Return the additive inverse of a standard-precision complex value.
real_complex	operator* (real_complex const &a, real_complex const &b)
	Return the product of two standard-precision complex values.
real_complex	operator* (real_complex const &a, real_type b)
	Return the product of a standard-precision complex value and a real scalar.
real_complex	operator* (real_type a, real_complex const &b)
	Return the product of a real scalar and a standard-precision complex value.
real_complex	operator/ (real_complex const &a, real_complex const &b)
	Return the quotient of two standard-precision complex values.
real_complex	operator/ (real_complex const &a, real_type b)
	Return the quotient of a standard-precision complex value and a real scalar.
real_complex	operator/ (real_type a, real_complex const &b)
	Return the quotient of a real scalar and a standard-precision complex value.
real_type	abs (real_complex const &value)
real_type	abs2 (real_complex const &value)
int	roots (real_type const *op, integer const Degree, real_type *zeror, real_type *zeroi)
template<>
real_type	machepsiT ()
template<>
real_type	toleranceT ()
template<typename T_real>
T_real	eval_poly (T_real const op[], integer const Degree, T_real const &x)
template double	eval_poly (double const op[], integer const Degree, double const &x)
template<typename T_real>
bool	Newton_step (T_real const op[], integer const Degree, T_real &x)
template bool	Newton_step (double const op[], integer const Degree, double &x)
template<typename T_real>
void	eval_poly_Dpoly (T_real const op[], integer const Degree, T_real const &x, T_real &p, T_real &dp)
template void	eval_poly_Dpoly (double const op[], integer const Degree, double const &x, double &p, double &dp)
template<typename T_real, typename T_complex>
T_complex	eval_poly_complex (T_real const op[], integer const Degree, T_complex const &x)
template real_complex	eval_poly_complex (real_type const op[], integer const Degree, real_complex const &x)
template<typename... Args>
void	root_assert (bool cond, std::format_string< Args... > fmt, Args &&... args)
template<typename T_real>
T_real	machepsiT ()
	Return the machine epsilon associated with the scalar type.
template<typename T_real>
T_real	toleranceT ()
	Return the default residual tolerance associated with the scalar type.
template<typename T_real>
T_real	evalMonicCubic (T_real const &x, T_real const &a, T_real const &b, T_real const &c)
template<typename T_real>
void	evalMonicCubic (T_real const &x, T_real const &a, T_real const &b, T_real const &c, T_real &p, T_real &dp)
	Evaluate a monic cubic polynomial and its first derivative.
template<typename T_real>
void	evalMonicCubic (T_real const &x, T_real const &a, T_real const &b, T_real const &c, T_real &p, T_real &dp, T_real &ddp)
	Evaluate a monic cubic polynomial and its first two derivatives.
template<typename T_real>
T_real	evalMonicQuartic (T_real const &x, T_real const &a, T_real const &b, T_real const &c, T_real const &d)
	Evaluate a monic quartic polynomial.
template<typename T_real>
void	evalMonicQuartic (T_real const &x, T_real const &a, T_real const &b, T_real const &c, T_real const &d, T_real &p, T_real &dp)
	Evaluate a monic quartic polynomial and its first derivative.
template<typename T_real>
void	evalMonicQuartic (T_real const &x, T_real const &a, T_real const &b, T_real const &c, T_real const &d, T_real &p, T_real &dp, T_real &ddp)
	Evaluate a monic quartic polynomial and its first two derivatives.

Variables
constexpr integer	MAXDEGREE = 100
	Maximum degree accepted by the Jenkins-Traub entry point.

Detailed Description

Implementation of Flocke algorithm for roots of 3rd and 4th degree polynomials.

There are 3 classed for 2nd, 3rd and 4th degree polynomial. An experimental translation to C++ of a C implementation of Jenkins–Traub algorithm is available.

References

• N.Flocke Algorithm 954: An Accurate and Efficient Cubic and Quartic Equation Solver for Physical Applications ACM TOMS, vol 41, n.4, 2015
• M.A. Jenkins and J.F.Traub A Three-Stage Algorithm for Real Polynomials Using Quadratic Iteration SIAM Journal on Numerical Analysis Vol. 7, No.4 (Dec., 1970), pp.545-566

Typedef Documentation

Cubic

using PolynomialRoots::Cubic = CubicT<real_type, real_complex>

integer

using PolynomialRoots::integer = int

Integer type used for degrees, counts and indices.

istream_type

using PolynomialRoots::istream_type = std::basic_istream<char>

Input stream type reserved for formatted input helpers.

ostream_type

using PolynomialRoots::ostream_type = std::basic_ostream<char>

Output stream type used by diagnostic methods.

Quadratic

using PolynomialRoots::Quadratic = QuadraticT<real_type, real_complex>

Quartic

using PolynomialRoots::Quartic = QuarticT<real_type, real_complex>

real_type

using PolynomialRoots::real_type = double

Scalar type used by the standard-precision API.

Function Documentation

abs()

real_type PolynomialRoots::abs ( real_complex const & value )

inline

abs2()

real_type PolynomialRoots::abs2 ( real_complex const & value )

inline

eval_poly() [1/2]

template double PolynomialRoots::eval_poly	(	double const	op[],
		integer const	Degree,
		double const &	x )

eval_poly() [2/2]

template<typename T_real>

T_real PolynomialRoots::eval_poly	(	T_real const	op[],
		integer	Degree,
		T_real const &	x )

Evaluate a real polynomial at a real point with a numerically stable scheme.

Parameters

[in]	op	polynomial coefficients in descending powers
[in]	Degree	polynomial degree
[in]	x	evaluation point

Returns

value of the polynomial at x

eval_poly_complex() [1/2]

template real_complex PolynomialRoots::eval_poly_complex	(	real_type const	op[],
		integer const	Degree,
		real_complex const &	x )

eval_poly_complex() [2/2]

template<typename T_real, typename T_complex>

T_complex PolynomialRoots::eval_poly_complex	(	T_real const	op[],
		integer	Degree,
		T_complex const &	x )

Evaluate a real polynomial at a complex point.

Parameters

[in]	op	polynomial coefficients in descending powers
[in]	Degree	polynomial degree
[in]	x	complex evaluation point

Returns

value of the polynomial at x

eval_poly_Dpoly() [1/2]

template void PolynomialRoots::eval_poly_Dpoly	(	double const	op[],
		integer const	Degree,
		double const &	x,
		double &	p,
		double &	dp )

eval_poly_Dpoly() [2/2]

template<typename T_real>

void PolynomialRoots::eval_poly_Dpoly	(	T_real const	op[],
		integer	Degree,
		T_real const &	x,
		T_real &	p,
		T_real &	dp )

Evaluate a real polynomial and its first derivative at a real point.

Parameters

[in]	op	polynomial coefficients in descending powers
[in]	Degree	polynomial degree
[in]	x	evaluation point
[out]	p	polynomial value at x
[out]	dp	derivative value at x

evalMonicCubic() [1/3]

template<typename T_real>

T_real PolynomialRoots::evalMonicCubic ( T_real const & x, T_real const & a, T_real const & b, T_real const & c )

inline

Evaluate a monic cubic polynomial.

Parameters

[in]	x	evaluation point
[in]	a	coefficient of \( x^2 \)
[in]	b	coefficient of \( x \)
[in]	c	constant coefficient

Returns

value of \( x^3 + a x^2 + b x + c \)

evalMonicCubic() [2/3]

template<typename T_real>

void PolynomialRoots::evalMonicCubic ( T_real const & x, T_real const & a, T_real const & b, T_real const & c, T_real & p, T_real & dp )

inline

Evaluate a monic cubic polynomial and its first derivative.

evalMonicCubic() [3/3]

template<typename T_real>

void PolynomialRoots::evalMonicCubic ( T_real const & x, T_real const & a, T_real const & b, T_real const & c, T_real & p, T_real & dp, T_real & ddp )

inline

Evaluate a monic cubic polynomial and its first two derivatives.

evalMonicQuartic() [1/3]

template<typename T_real>

T_real PolynomialRoots::evalMonicQuartic ( T_real const & x, T_real const & a, T_real const & b, T_real const & c, T_real const & d )

inline

Evaluate a monic quartic polynomial.

evalMonicQuartic() [2/3]

template<typename T_real>

void PolynomialRoots::evalMonicQuartic ( T_real const & x, T_real const & a, T_real const & b, T_real const & c, T_real const & d, T_real & p, T_real & dp )

inline

Evaluate a monic quartic polynomial and its first derivative.

evalMonicQuartic() [3/3]

template<typename T_real>

void PolynomialRoots::evalMonicQuartic ( T_real const & x, T_real const & a, T_real const & b, T_real const & c, T_real const & d, T_real & p, T_real & dp, T_real & ddp )

inline

Evaluate a monic quartic polynomial and its first two derivatives.

machepsiT() [1/2]

template<>

real_type PolynomialRoots::machepsiT

(

)

machepsiT() [2/2]

template<typename T_real>

T_real PolynomialRoots::machepsiT

(

)

Return the machine epsilon associated with the scalar type.

Newton_step() [1/2]

template bool PolynomialRoots::Newton_step	(	double const	op[],
		integer const	Degree,
		double &	x )

Newton_step() [2/2]

template<typename T_real>

bool PolynomialRoots::Newton_step	(	T_real const	op[],
		integer	Degree,
		T_real &	x )

Apply one Newton update to a real polynomial root estimate.

Parameters

[in]	op	polynomial coefficients in descending powers
[in]	Degree	polynomial degree
[in,out]	x	current estimate, overwritten with the updated value

Returns

true after performing the update

one27thT()

template<typename T_real>

T_real PolynomialRoots::one27thT ( )

inline

operator*() [1/3]

real_complex PolynomialRoots::operator* ( real_complex const & a, real_complex const & b )

inline

Return the product of two standard-precision complex values.

operator*() [2/3]

real_complex PolynomialRoots::operator* ( real_complex const & a, real_type b )

inline

Return the product of a standard-precision complex value and a real scalar.

operator*() [3/3]

real_complex PolynomialRoots::operator* ( real_type a, real_complex const & b )

inline

Return the product of a real scalar and a standard-precision complex value.

operator+() [1/3]

real_complex PolynomialRoots::operator+ ( real_complex const & a, real_complex const & b )

inline

Return the sum of two standard-precision complex values.

operator+() [2/3]

real_complex PolynomialRoots::operator+ ( real_complex const & a, real_type b )

inline

Return the sum of a standard-precision complex value and a real scalar.

operator+() [3/3]

real_complex PolynomialRoots::operator+ ( real_type a, real_complex const & b )

inline

Return the sum of a real scalar and a standard-precision complex value.

operator-() [1/4]

real_complex PolynomialRoots::operator- ( real_complex const & a )

inline

Return the additive inverse of a standard-precision complex value.

operator-() [2/4]

real_complex PolynomialRoots::operator- ( real_complex const & a, real_complex const & b )

inline

Return the difference of two standard-precision complex values.

operator-() [3/4]

real_complex PolynomialRoots::operator- ( real_complex const & a, real_type b )

inline

Return the difference between a standard-precision complex value and a real scalar.

operator-() [4/4]

real_complex PolynomialRoots::operator- ( real_type a, real_complex const & b )

inline

Return the difference between a real scalar and a standard-precision complex value.

operator/() [1/3]

real_complex PolynomialRoots::operator/ ( real_complex const & a, real_complex const & b )

inline

Return the quotient of two standard-precision complex values.

operator/() [2/3]

real_complex PolynomialRoots::operator/ ( real_complex const & a, real_type b )

inline

Return the quotient of a standard-precision complex value and a real scalar.

operator/() [3/3]

real_complex PolynomialRoots::operator/ ( real_type a, real_complex const & b )

inline

Return the quotient of a real scalar and a standard-precision complex value.

root_assert()

template<typename... Args>

void PolynomialRoots::root_assert ( bool cond, std::format_string< Args... > fmt, Args &&... args )

inline

Lightweight assertion helper used by the solvers to validate inputs.

Parameters

[in]	cond	condition that must hold
[in]	fmt	format string used to build the diagnostic message
[in]	args	arguments interpolated in fmt

roots()

int PolynomialRoots::roots ( real_type const * op, integer Degree, real_type * zeror, real_type * zeroi )

nodiscard

Find roots of a generic polynomial using Jenkins-Traub method

Parameters

[in]	op	the coefficients of the polynomial
[in]	Degree	degree of the polynomial
[out]	zeror	real part of the roots
[out]	zeroi	imaginary part of the roots

Returns

error code, 0 OK

thirdT()

template<typename T_real>

T_real PolynomialRoots::thirdT ( )

inline

toleranceT() [1/2]

template<>

real_type PolynomialRoots::toleranceT

(

)

toleranceT() [2/2]

template<typename T_real>

T_real PolynomialRoots::toleranceT

(

)

Return the default residual tolerance associated with the scalar type.

two27thT()

template<typename T_real>

T_real PolynomialRoots::two27thT ( )

inline

Variable Documentation

MAXDEGREE

integer PolynomialRoots::MAXDEGREE = 100

inlineconstexpr

Maximum degree accepted by the Jenkins-Traub entry point.