polynomial_example.cc File Reference

Polynomial arithmetic in Aleph-w: construction, algebra, calculus, interpolation, and applications. More...

#include <iostream>
#include <iomanip>
#include <cmath>
#include <tpl_polynomial.H>

Include dependency graph for polynomial_example.cc:

Go to the source code of this file.

Typedefs
using	IntPolynomial = Gen_Polynomial< long long >

Functions
static void	section (const string &title)
static void	basic_arithmetic ()
	Demonstrates polynomial construction, printing, and the four basic arithmetic operations.
static void	calculus_example ()
	Symbolic differentiation and integration, verifying the Fundamental Theorem of Calculus: the derivative of the integral recovers the original polynomial.
static void	roots_and_interpolation ()
	Two ways to build polynomials from known data: (a) from_roots: given roots r1, r2, ..., builds (x - r1)(x - r2)... (b) interpolate: polynomial interpolation through given (x, y) points using Newton divided differences.
static void	transfer_function ()
	A simple low-pass filter transfer function H(s) = N(s) / D(s).
static void	sparse_polynomials ()
	Demonstrates efficiency of sparse representation by constructing polynomials with very high degree but few terms.
static void	root_analysis ()
	Demonstrates Sturm sequences, root counting, Cauchy bounds, Descartes' rule of signs, bisection, and Newton-Raphson.
static void	algebraic_transformations ()
	Demonstrates square-free factorization, extended GCD (Bezout identity), polynomial reversal, and Taylor shift.
int	main ()

Detailed Description

Polynomial arithmetic in Aleph-w: construction, algebra, calculus, interpolation, and applications.

Overview

The Gen_Polynomial<Coefficient> class in tpl_polynomial.H provides industrial-strength univariate polynomial arithmetic using a sparse representation backed by DynMapTree<size_t, Coefficient>. Only non-zero coefficients are stored, making it efficient on high-degree sparse polynomials such as x^1000 + 1.

This example walks through five illustrative scenarios:

1. Basic arithmetic — constructing polynomials and performing addition, subtraction, multiplication, and division.
2. Calculus — symbolic differentiation, integration, and the Fundamental Theorem verification.
3. Root finding and interpolation — building polynomials from known roots and from data points via interpolation using Newton divided differences (Polynomial::interpolate()).
4. Signal processing — representing a transfer function as a ratio of polynomials and evaluating frequency response.
5. Sparse polynomials — demonstrating efficiency on polynomials with very high degree but few non-zero terms.

Compilation

cmake -S . -B build -G Ninja -DBUILD_EXAMPLES=ON
cmake --build build --target polynomial_example
./build/Examples/polynomial_example

Author

Leandro Rabindranath León

Definition in file polynomial_example.cc.

Typedef Documentation

IntPolynomial

using IntPolynomial = Gen_Polynomial<long long>

Definition at line 80 of file polynomial_example.cc.

Function Documentation

algebraic_transformations()

static void algebraic_transformations ( )

static

Demonstrates square-free factorization, extended GCD (Bezout identity), polynomial reversal, and Taylor shift.

Definition at line 443 of file polynomial_example.cc.

References Aleph::Gen_Polynomial< Coefficient >::degree(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::factorize(), Aleph::Gen_Polynomial< Coefficient >::pow(), Aleph::Gen_Polynomial< Coefficient >::reverse(), section(), Aleph::Gen_Polynomial< Coefficient >::shift(), Aleph::Gen_Polynomial< Coefficient >::square_free(), and Aleph::Gen_Polynomial< Coefficient >::xgcd().

Referenced by main().

basic_arithmetic()

static void basic_arithmetic ( )

static

Demonstrates polynomial construction, printing, and the four basic arithmetic operations.

Definition at line 102 of file polynomial_example.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::divmod(), remainder(), and section().

Referenced by main().

calculus_example()

static void calculus_example ( )

static

Symbolic differentiation and integration, verifying the Fundamental Theorem of Calculus: the derivative of the integral recovers the original polynomial.

Definition at line 148 of file polynomial_example.cc.

References Aleph::Gen_Polynomial< Coefficient >::derivative(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::integral(), Aleph::Gen_Polynomial< Coefficient >::nth_derivative(), and section().

Referenced by main().

main()

int main

(

)

Definition at line 565 of file polynomial_example.cc.

References algebraic_transformations(), basic_arithmetic(), calculus_example(), root_analysis(), roots_and_interpolation(), sparse_polynomials(), and transfer_function().

root_analysis()

static void root_analysis ( )

static

Demonstrates Sturm sequences, root counting, Cauchy bounds, Descartes' rule of signs, bisection, and Newton-Raphson.

Definition at line 380 of file polynomial_example.cc.

References Aleph::Gen_Polynomial< Coefficient >::bisect_root(), Aleph::Gen_Polynomial< Coefficient >::cauchy_bound(), Aleph::Gen_Polynomial< Coefficient >::count_all_real_roots(), Aleph::Gen_Polynomial< Coefficient >::count_real_roots(), Aleph::Gen_Polynomial< Coefficient >::degree(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::from_roots(), Aleph::Gen_Polynomial< Coefficient >::negate_arg(), Aleph::Gen_Polynomial< Coefficient >::newton_root(), section(), and Aleph::Gen_Polynomial< Coefficient >::sign_variations().

Referenced by main().

roots_and_interpolation()

static void roots_and_interpolation ( )

static

Two ways to build polynomials from known data: (a) from_roots: given roots r1, r2, ..., builds (x - r1)(x - r2)... (b) interpolate: polynomial interpolation through given (x, y) points using Newton divided differences.

Definition at line 190 of file polynomial_example.cc.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), FunctionalMethods< Container, T >::for_each(), Aleph::Gen_Polynomial< Coefficient >::from_roots(), Aleph::Gen_Polynomial< Coefficient >::interpolate(), r, and section().

Referenced by main().

section()

static void section ( const string &  title )

static

Definition at line 86 of file polynomial_example.cc.

Referenced by algebraic_transformations(), basic_arithmetic(), calculus_example(), Aleph::FFT< Real >::filtfilt(), Aleph::FFT< Real >::filtfilt(), Aleph::FFT< Real >::freqz(), Aleph::FFT< Real >::gain_margin(), Aleph::FFT< Real >::group_delay(), Aleph::FFT< Real >::has_near_pole_zero_cancellation(), Aleph::FFT< Real >::is_stable(), main(), Aleph::FFT< Real >::minimum_pole_zero_distance(), Aleph::FFT< Real >::pair_poles_and_zeros(), Aleph::FFT< Real >::phase_delay(), Aleph::FFT< Real >::phase_margin(), Aleph::FFT< Real >::poles(), root_analysis(), roots_and_interpolation(), Aleph::FFT< Real >::section_from_coefficients(), sparse_polynomials(), Aleph::FFT< Real >::stability_margin(), TEST(), TEST(), transfer_function(), Aleph::FFT< Real >::validate_no_near_pole_zero_cancellation(), Aleph::FFT< Real >::validate_stable(), Aleph::FFT< Real >::validate_stable(), and Aleph::FFT< Real >::zeros().

sparse_polynomials()

static void sparse_polynomials ( )

static

Demonstrates efficiency of sparse representation by constructing polynomials with very high degree but few terms.

Definition at line 323 of file polynomial_example.cc.

References Aleph::DynList< T >::append(), Aleph::Gen_Polynomial< Coefficient >::compose(), Aleph::Gen_Polynomial< Coefficient >::degree(), Aleph::Gen_Polynomial< Coefficient >::derivative(), Aleph::diff(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::num_terms(), and section().

Referenced by main().

transfer_function()

static void transfer_function ( )

static

A simple low-pass filter transfer function H(s) = N(s) / D(s).

We evaluate the numerator and denominator polynomials separately at several frequency points to compute |H(jω)|.

Definition at line 245 of file polynomial_example.cc.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), exp(), Aleph::Gen_Polynomial< Coefficient >::for_each_term(), pow(), section(), and w.

Referenced by main().