Utils::Sturm< Real > Class Template Reference

Class for managing and computing the Sturm sequence associated with a polynomial. More...

#include <Utils_Poly.hh>

Public Types
using	Integer = int
using	Poly_t = Poly<Real>
using	dvec_t = Eigen::Matrix<Real,Eigen::Dynamic,1>
using	Interval

Public Member Functions
	Sturm ()
void	build (Poly_t const &p)
	Constructs the Sturm sequence for a given polynomial.
Integer	length () const
	Retrieves the length of the stored Sturm sequence.
Poly_t const &	get (Integer i) const
	Retrieves the i-th polynomial of the stored Sturm sequence.
Integer	sign_variations (Real x, bool &on_root) const
	Computes the sign variations of the stored Sturm sequence at a given point \( x \).
Integer	separate_roots (Real a, Real b)
	Computes subintervals containing single roots within a given interval \( [a,b] \).
Integer	separate_roots ()
	Compute an interval \( [a,b] \) that contains all real roots and separate them into subintervals.
Integer	n_roots () const
	Returns the number of roots found by the Sturm sequence.
Real	a () const
	Returns the left boundary \( a \) of the interval \( [a,b] \) containing all real roots.
Real	b () const
	Returns the right boundary \( b \) of the interval \( [a,b] \) containing all real roots.
Interval const &	get_interval (Integer i) const
	Returns the i-th interval containing a single root.
void	refine_roots ()
	Refine the roots of the polynomial after the intervals have been separated.
dvec_t const &	roots () const
	Returns a vector containing the computed roots after refinement.

Detailed Description

template<typename Real>
class Utils::Sturm< Real >

Class for managing and computing the Sturm sequence associated with a polynomial.

The Sturm class is dedicated to the construction and manipulation of the Sturm sequence for a given polynomial \( p(x) \). This sequence is instrumental in real algebraic geometry, as it provides crucial insights into the behavior of polynomial roots. Specifically, it enables users to ascertain the number of real roots within specific intervals and helps identify the locations of distinct real roots.

Template Parameters

Real	The data type used for the polynomial coefficients, typically a floating-point type.

Features

• Sturm Sequence Construction: Efficiently builds the Sturm sequence for a specified polynomial, facilitating root analysis.
• Sign Variation Counting: Provides methods to compute the number of sign variations of the Sturm sequence at given points, which is essential for determining the count of real roots in specified intervals.
• Root Isolation: Implements techniques to isolate intervals that contain single roots, aiding in numerical root-finding methods.
• Interval Analysis: Allows for the examination of polynomial behavior across intervals, enhancing the understanding of root distribution.

Member Typedef Documentation

dvec_t

template<typename Real>

using Utils::Sturm< Real >::dvec_t = Eigen::Matrix<Real,Eigen::Dynamic,1>

Integer

template<typename Real>

using Utils::Sturm< Real >::Integer = int

Interval

template<typename Real>

using Utils::Sturm< Real >::Interval

Initial value:

 struct Interval {
      Real    a;
      Real    b;
      Integer va;
      Integer vb;
      bool    a_on_root;
      bool    b_on_root;
    }

Poly_t

template<typename Real>

using Utils::Sturm< Real >::Poly_t = Poly<Real>

Constructor & Destructor Documentation

Sturm()

template<typename Real>

Utils::Sturm< Real >::Sturm ( )

inline

Member Function Documentation

a()

template<typename Real>

Real Utils::Sturm< Real >::a ( ) const

inline

Returns the left boundary \( a \) of the interval \( [a,b] \) containing all real roots.

This method returns the left endpoint of the interval that contains all real roots of the polynomial after using methods such as separate_roots().

Returns

The left boundary \( a \) of the interval.

b()

template<typename Real>

Real Utils::Sturm< Real >::b ( ) const

inline

Returns the right boundary \( b \) of the interval \( [a,b] \) containing all real roots.

This method returns the right endpoint of the interval that contains all real roots of the polynomial after using methods such as separate_roots().

Returns

The right boundary \( b \) of the interval.

build()

template<typename Real>

void Utils::Sturm< Real >::build

(

Poly_t const &

p

)

Constructs the Sturm sequence for a given polynomial.

This method takes a polynomial \( p(x) \) as input and builds its corresponding Sturm sequence.

Parameters

p	The polynomial \( p(x) \) for which to build the Sturm sequence. This should be a valid polynomial of type Poly_t.

Note

The Sturm sequence will be stored internally within the class, allowing subsequent methods to utilize it for root counting or determining the nature of the roots of the polynomial.

Warning

Ensure that the polynomial is non-constant and valid, as the Sturm sequence is not defined for constant polynomials.

get()

template<typename Real>

Poly_t const & Utils::Sturm< Real >::get ( Integer i ) const

inline

Retrieves the i-th polynomial of the stored Sturm sequence.

This method returns a constant reference to the polynomial at the specified index i in the Sturm sequence. The index is zero-based, meaning that get(0) will return the first polynomial in the sequence, get(1) will return the second, and so on.

Parameters

i	The index of the polynomial to retrieve from the Sturm sequence. It must be a valid index (0 <= i < length of Sturm sequence).

Returns

A constant reference to the i-th polynomial in the Sturm sequence.

Exceptions

std::out_of_range

if the index i is out of bounds.

Note

This method does not modify the Sturm sequence or its contents.

Example

Sturm<Poly_t> sturm;
Poly_t polynomial = ...; // Assume polynomial is initialized
sturm.build(polynomial); // Build the Sturm sequence from the polynomial
 
// Get the first polynomial in the Sturm sequence
Poly_t const & first_poly = sturm.get(0);
 
// Print or utilize the first polynomial
std::cout << "First polynomial: " << first_poly << '\n';

get_interval()

template<typename Real>

Interval const & Utils::Sturm< Real >::get_interval ( Integer i ) const

inline

Returns the i-th interval containing a single root.

After separating the roots of the polynomial, this method provides access to the specific interval that contains the i-th root. The interval is defined by a structure Interval, which holds the boundaries of the interval.

Parameters

i	The index of the interval (root).

Returns

The interval \( [a_i, b_i] \) containing the i-th root.

length()

template<typename Real>

Integer Utils::Sturm< Real >::length ( ) const

inline

Retrieves the length of the stored Sturm sequence.

This method returns the number of polynomials in the Sturm sequence that has been built for the corresponding polynomial.

Returns

The number of polynomials in the Sturm sequence as an integer value.

Note

This method does not modify the Sturm sequence or its contents. It only provides information about its size.

n_roots()

template<typename Real>

Integer Utils::Sturm< Real >::n_roots ( ) const

inline

Returns the number of roots found by the Sturm sequence.

After running root separation (e.g., using separate_roots()), this method returns the number of intervals found, each containing a single root.

Returns

The number of root-containing intervals.

Example

Sturm<Poly_t> sturm;
Poly_t polynomial = ...; // Initialize polynomial
sturm.build(polynomial);
sturm.separate_roots();
 
Integer num_roots = sturm.n_roots();
std::cout << "Number of real roots: " << num_roots << '\n';

refine_roots()

template<typename Real>

void Utils::Sturm< Real >::refine_roots

(

)

Refine the roots of the polynomial after the intervals have been separated.

This method computes the roots within the intervals determined by the separate_roots() method. After separating the intervals that contain the roots, this method applies a refinement procedure to accurately locate the roots within those intervals.

Example

Sturm<Poly_t> sturm;
Poly_t polynomial = ...; // Initialize polynomial
sturm.build(polynomial);
sturm.separate_roots();
sturm.refine_roots();
 
// Now the roots are refined and can be accessed
dvec_t const& refined_roots = sturm.roots();

roots()

template<typename Real>

dvec_t const & Utils::Sturm< Real >::roots ( ) const

inline

Returns a vector containing the computed roots after refinement.

This method returns the refined roots of the polynomial that were computed using the refine_roots() method. The roots are stored in a vector of type dvec_t.

Returns

A constant reference to the vector containing the refined roots.

Example

// After separating and refining roots
dvec_t const& roots = sturm.roots();
for (const auto& root : roots) {
    std::cout << "Root: " << root << '\n';
}

separate_roots() [1/2]

template<typename Real>

Integer Utils::Sturm< Real >::separate_roots

(

)

Compute an interval \( [a,b] \) that contains all real roots and separate them into subintervals.

This method uses Cauchy's bounds to compute an interval \( [-B, B] \), where \( B \) is an upper bound for the absolute values of the real roots of the polynomial. It then isolates each root by dividing this interval into subintervals, each containing exactly one root. It returns the number of subintervals (i.e., roots) found.

The method leverages Cauchy's bound \( B = 1 + \frac{\max |a_i|}{|a_n|} \), where \( a_n \) is the leading coefficient and \( a_i \) are the other coefficients, to determine an interval that contains all real roots.

Returns

The number of subintervals (roots) found.

Example

Sturm<Poly_t> sturm;
Poly_t polynomial = ...; // Assume polynomial is initialized
sturm.build(polynomial); // Build the Sturm sequence from the polynomial
 
Integer root_count = sturm.separate_roots(); // Automatically separate all real roots within computed bounds
std::cout << "Number of real roots found: " << root_count << '\n';

This method can be used to isolate all real roots of a polynomial in a simple, automated fashion.

separate_roots() [2/2]

template<typename Real>

Integer Utils::Sturm< Real >::separate_roots	(	Real	a,
		Real	b )

Computes subintervals containing single roots within a given interval \( [a,b] \).

This method identifies subintervals within the specified range \( [a,b] \) that each contain a single root of the polynomial. It performs root isolation and returns the number of such intervals found.

Parameters

a	The lower bound of the interval.
b	The upper bound of the interval.

Returns

The number of intervals (roots) found within the interval \( [a,b] \).

example

Sturm<Poly_t> sturm;
Poly_t polynomial = ...; // Assume polynomial is initialized
sturm.build(polynomial); // Build the Sturm sequence from the polynomial
 
Real a = -1.0; // Lower bound of the interval
Real b = 1.0;  // Upper bound of the interval
 
Integer root_count = sturm.separate_roots(a, b);
std::cout << "Number of roots found in the interval [" << a << ", " << b << "]: " << root_count << '\n';

sign_variations()

template<typename Real>

Integer Utils::Sturm< Real >::sign_variations	(	Real	x,
		bool &	on_root ) const

Computes the sign variations of the stored Sturm sequence at a given point \( x \).

This method evaluates the sign variations of the polynomials in the stored Sturm sequence at the specified point \( x \). The number of sign variations can help determine the number of real roots of the polynomial in the interval up to \( x \).

Parameters

x	The point at which to compute the sign variations of the Sturm sequence.
on_root	A reference to a boolean variable that will be set to true if \( x \) is a root of the first polynomial of the Sturm sequence; otherwise, it will be false.

Returns

The number of sign variations in the Sturm sequence at the point \( x \).

Example

Sturm<Poly_t> sturm;
Poly_t polynomial = ...; // Assume polynomial is initialized
sturm.build(polynomial); // Build the Sturm sequence from the polynomial
 
Real x = ...; // The point at which to evaluate the sign variations
bool is_on_root = false;
 
Integer variations = sturm.sign_variations(x, is_on_root);
 
std::cout << "Sign variations at x = " << x << ": " << variations << '\n';
if (is_on_root) {
  std::cout << "The point x is a root of polynomial.\n";
} else {
  std::cout << "The point x is not a root of polynomial.\n";
}

---

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

• /Users/enricobertolazzi/Ricerca/PINS/PINS-submodules/UtilsLite/src/Utils_Poly.hh