FNFT
Files | Functions
PRIVATE: Polynomials

Files

file  fnft__poly_chirpz.h
 Fast evaluation of polynomials using the Chirp Z-transform.
 
file  fnft__poly_eval.h
 Evaluation of polynomials and their derivatives using Horner's method.
 
file  fnft__poly_fmult.h
 Fast multiplication of n polynomials.
 
file  fnft__poly_roots_fasteigen.h
 Fast root finding of polynomials.
 
file  fnft__poly_roots_fftgridsearch.h
 Approximation of polynomial roots on the unit circle using gridding.
 
file  fnft__poly_specfact.h
 Spectral factorization of polynomials.
 

Functions

FNFT_INT fnft__poly_chirpz (const FNFT_UINT deg, FNFT_COMPLEX const *const p, const FNFT_COMPLEX A, const FNFT_COMPLEX W, const FNFT_UINT M, FNFT_COMPLEX *const result)
 Fast evaluation of a polynomial on a spiral in the complex plane. More...
 
FNFT_INT fnft__poly_eval (const FNFT_UINT deg, FNFT_COMPLEX const *const p, const FNFT_UINT nz, FNFT_COMPLEX *const z)
 Evaluation of polynomials. More...
 
FNFT_INT fnft__poly_evalderiv (const FNFT_UINT deg, FNFT_COMPLEX const *const p, const FNFT_UINT nz, FNFT_COMPLEX *const z, FNFT_COMPLEX *const deriv)
 Evaluation of polynomials and their derivatives. More...
 
FNFT_INT fnft__poly_fmult_two_polys_len (const FNFT_UINT deg)
 Length of the FFTs used by fnft__poly_fmult_two_polys. More...
 
FNFT_INT fnft__poly_fmult_two_polys (const FNFT_UINT deg, FNFT_COMPLEX const *const p1, FNFT_COMPLEX const *const p2, FNFT_COMPLEX *const result, fnft__fft_wrapper_plan_t plan_fwd, fnft__fft_wrapper_plan_t plan_inv, FNFT_COMPLEX *const buf0, FNFT_COMPLEX *const buf1, FNFT_COMPLEX *const buf2, const FNFT_INT add_flag)
 Multiplies two polynomials. More...
 
FNFT_INT fnft__poly_fmult_two_polys2x2 (const FNFT_UINT deg, FNFT_COMPLEX const *const p1_11, const FNFT_UINT p1_stride, FNFT_COMPLEX const *const p2_11, const FNFT_UINT p2_stride, FNFT_COMPLEX *const result_11, const FNFT_UINT result_stride, fnft__fft_wrapper_plan_t plan_fwd, fnft__fft_wrapper_plan_t plan_inv, FNFT_COMPLEX *const buf0, FNFT_COMPLEX *const buf1, FNFT_COMPLEX *const buf2)
 Multiplies two 2x2 matrices of polynomials. More...
 
FNFT_UINT fnft__poly_fmult_numel (const FNFT_UINT deg, const FNFT_UINT n)
 Number of elements that the input p to fnft__poly_fmult should have. More...
 
FNFT_INT fnft__poly_fmult (FNFT_UINT *const d, FNFT_UINT n, FNFT_COMPLEX *const p, FNFT_INT *const W_ptr)
 Fast multiplication of multiple polynomials of same degree. More...
 
FNFT_UINT fnft__poly_fmult2x2_numel (const FNFT_UINT deg, const FNFT_UINT n)
 Number of elements that the inputs p and result to fnft__poly_fmult2x2 should have. More...
 
FNFT_INT fnft__poly_fmult2x2 (FNFT_UINT *d, FNFT_UINT n, FNFT_COMPLEX *const p, FNFT_COMPLEX *const result, FNFT_INT *const W_ptr)
 Fast multiplication of multiple 2x2 matrix-valued polynomials of the same degree. More...
 
FNFT_INT fnft__poly_roots_fasteigen (const FNFT_UINT deg, FNFT_COMPLEX const *const p, FNFT_COMPLEX *const roots)
 Fast computation of polynomial roots. More...
 
FNFT_INT fnft__poly_roots_fftgridsearch (const FNFT_UINT deg, FNFT_COMPLEX const *const p, FNFT_UINT *const M_ptr, FNFT_REAL const *const PHI, FNFT_COMPLEX *const roots)
 Unit circle roots of a polynomial via grid search. More...
 
FNFT_INT fnft__poly_roots_fftgridsearch_paraherm (const FNFT_UINT deg, FNFT_COMPLEX const *const p, FNFT_UINT *const M_ptr, FNFT_REAL const *const PHI, FNFT_COMPLEX *const roots)
 Unit circle roots of a parahermitian Laurent polynomial via grid search. More...
 
FNFT_INT fnft__poly_specfact (const FNFT_UINT deg, FNFT_COMPLEX const *const poly, FNFT_COMPLEX *const result, const FNFT_UINT oversampling_factor, const FNFT_INT kappa)
 Spectral factorization of polynomial. More...
 

Detailed Description

Function Documentation

◆ fnft__poly_chirpz()

FNFT_INT fnft__poly_chirpz ( const FNFT_UINT  deg,
FNFT_COMPLEX const *const  p,
const FNFT_COMPLEX  A,
const FNFT_COMPLEX  W,
const FNFT_UINT  M,
FNFT_COMPLEX *const  result 
)

Fast evaluation of a polynomial on a spiral in the complex plane.

This routine implements the Chirp Z-transform. Given a polynomial

\[ p(z)=p_0+p_1 z^1+p_2 z^2+...+p_{deg} z^{deg} \]

and complex numbers A and W, this routine evaluates the polynomial \( p(z) \) at the M points \( z=1/w_k \), where

\[ w_k=AW^{-m}, \quad m=0,1,\dots,M-1, \]

using only \( O\{(N+M)\log(N+M)\} \) floating point operations.

See also
https://doi.org/10.1109/TAU.1969.1162034
Parameters
[in]degDegree of the polynomial
[in]pArray containing the deg+1 coefficients of the polynomial in descending order (i.e., \( p_{deg}, p_{deg-1}, \dots, p_1, p_0 \)).
[in]AFirst constant defining the spiral at which the polynomial will be evaluated.
[in]WSecond constant defining the spiral at which the polynomial will be evaluated
[in]MNumber of points at which the polynomial will be evaluated.
[out]resultArray of M points. Will be filled with \( p(1/w_1),...,p(1/w_M) \).
Returns
FNFT_SUCCESS or one of the FNFT_EC_... error codes defined in fnft_errwarn.h.

◆ fnft__poly_eval()

FNFT_INT fnft__poly_eval ( const FNFT_UINT  deg,
FNFT_COMPLEX const *const  p,
const FNFT_UINT  nz,
FNFT_COMPLEX *const  z 
)

Evaluation of polynomials.

Evaluates a polynomial

\[ p(z)=p_0+p_1 z^1+p_2 z^2+...+p_{deg} z^{deg} \]

at nz points

\[ z=z_1,...,z_{nz} \]

in the complex plane using Horner's method.

See also
http://cnx.org/contents/hnzXCQRy@7/Horners-Method-for-Evaluating-
Parameters
[in]degDegree of the polynomial
[in]pArray containing the deg+1 coefficients of the polynomial in descending order (i.e., \( p_{deg}, p_{deg-1}, \dots, p_1, p_0 \)).
[in]nzNumber of points z at which the polynomial should be evaluated
[in,out]zArray of nz points \(z_1,\dots,z_{nz}\) at which the polynomial should be evaluated. These values will be overwritten with the corresponding values \(p(z_1),\dots,p(z_{nz})\) of the polynomial.
Returns
FNFT_SUCCESS or one of the FNFT_EC_... error codes defined in fnft_errwarn.h.

◆ fnft__poly_evalderiv()

FNFT_INT fnft__poly_evalderiv ( const FNFT_UINT  deg,
FNFT_COMPLEX const *const  p,
const FNFT_UINT  nz,
FNFT_COMPLEX *const  z,
FNFT_COMPLEX *const  deriv 
)

Evaluation of polynomials and their derivatives.

Evaluates a polynomial

\[ p(z)=p_0+p_1 z^1+p_2 z^2+...+p_{deg} z^{deg} \]

and its derivative

\[ p'(z)=\frac{dp}{dz}(z)=p_1+2p_2 z^1+...+deg~p_{deg} z^{deg-1} \]

at nz points

\[ z=z_1,...,z_{nz} \]

in the complex plane using Horner's method.

See also
http://cnx.org/contents/hnzXCQRy@7/Horners-Method-for-Evaluating-
Parameters
[in]degDegree of the polynomial
[in]pArray containing the deg+1 coefficients of the polynomial in descending order (i.e., \( p_{deg}, p_{deg-1}, \dots, p_1, p_0 \)).
[in]nzNumber of points z at which the polynomial should be evaluated
[in,out]zArray of nz points \(z_1,\dots,z_{nz}\) at which the polynomial and its derivative should be evaluated. These values will be overwritten with the corresponding values \(p(z_1),\dots,p(z_{nz})\) of the polynomial.
[out]derivArray of length nz. It will be filled with the values \(p'(z_1),\dots,p'(z_{nz})\) of the derivative.
Returns
FNFT_SUCCESS or one of the FNFT_EC_... error codes defined in fnft_errwarn.h.

◆ fnft__poly_fmult()

FNFT_INT fnft__poly_fmult ( FNFT_UINT *const  d,
FNFT_UINT  n,
FNFT_COMPLEX *const  p,
FNFT_INT *const  W_ptr 
)

Fast multiplication of multiple polynomials of same degree.

Fast multiplication of n polynomials of degree d. Their coefficients are stored in the array p and will be overwritten. If W_ptr != NULL, the result has been normalized by a factor 2^W. Upon exit, W has been stored in *W_ptr.

Parameters
[in,out]dUpon entry, degree of the input polynomials. Upon exit, degree of their product.
[in]nNumber of polynomials.
[in,out]pComplex valued array with m entries, where m is determined using fnft__poly_fmult_numel. Upon entry, the first (*d+1)*n elements of this array contain the coefficients of the polynomials. Upon exit, the first *d+1 elements contain the result.
[in]W_ptrPointer to normalization flag.
Returns
FNFT_SUCCESS or one of the FNFT_EC_... error codes defined in fnft_errwarn.h.

◆ fnft__poly_fmult2x2()

FNFT_INT fnft__poly_fmult2x2 ( FNFT_UINT d,
FNFT_UINT  n,
FNFT_COMPLEX *const  p,
FNFT_COMPLEX *const  result,
FNFT_INT *const  W_ptr 
)

Fast multiplication of multiple 2x2 matrix-valued polynomials of the same degree.

Fast multiplication of n 2x2 matrix-valued polynomials of degree d. Their coefficients are stored in the array p and will be overwritten. If W_ptr != NULL, the result has been normalized by a factor 2^W. Upon exit, W has been stored in *W_ptr.

Parameters
[in]dPointer to a FNFT_UINT containing the degree of the polynomials.
[in]nNumber of 2x2 matrix-valued polynomials.
[in,out]pComplex valued array which holds the coefficients of the polynomials being multiplied. Should be of length m*(*d+1), where m is obtained using fnft__poly_fmult2x2_numel. WARNING: p is overwritten.
[out]resultComplex valued array that holds the result of the multiplication. Should be of the same size as p.
[in]W_ptrPointer to normalization flag.
Returns
FNFT_SUCCESS or one of the FNFT_EC_... error codes defined in fnft_errwarn.h.

◆ fnft__poly_fmult2x2_numel()

FNFT_UINT fnft__poly_fmult2x2_numel ( const FNFT_UINT  deg,
const FNFT_UINT  n 
)

Number of elements that the inputs p and result to fnft__poly_fmult2x2 should have.

Specifies how much memory (in number of elements) the user needs to allocate for the inputs p and result of the routine fnft__poly_fmult2x2.

Parameters
[in]degDegree of the polynomials
[in]nNumber of polynomials
Returns
A number m. The inputs p and result to fnft__poly_fmult2x2 should be a array with m entries.

◆ fnft__poly_fmult_numel()

FNFT_UINT fnft__poly_fmult_numel ( const FNFT_UINT  deg,
const FNFT_UINT  n 
)

Number of elements that the input p to fnft__poly_fmult should have.

Specifies how much memory (in number of elements) the user needs to allocate for the input p of the routine fnft__poly_fmult.

Parameters
[in]degDegree of the polynomials
[in]nNumber of polynomials
Returns
A number m. The input p to fnft__poly_fmult should be a array with m entries.

◆ fnft__poly_fmult_two_polys()

FNFT_INT fnft__poly_fmult_two_polys ( const FNFT_UINT  deg,
FNFT_COMPLEX const *const  p1,
FNFT_COMPLEX const *const  p2,
FNFT_COMPLEX *const  result,
fnft__fft_wrapper_plan_t  plan_fwd,
fnft__fft_wrapper_plan_t  plan_inv,
FNFT_COMPLEX *const  buf0,
FNFT_COMPLEX *const  buf1,
FNFT_COMPLEX *const  buf2,
const FNFT_INT  add_flag 
)

Multiplies two polynomials.

Fast multiplication of two polynomials using the FFT.

Parameters
degDegree of the polynomials.
[in]p1Array of coefficients for the first polynomial.
[in]p2Array of coefficients for the second polynomial.
[out]resultArray in which the coefficients of the result are stored.
plan_fwdPlan generated by fnft__fft_wrapper_create_plan for a forward FFT of the length returned by fnft__poly_fmult_two_polys_len.
plan_invPlan generated by fnft__fft_wrapper_create_plan for an inverse FFT of the length returned by fnft__poly_fmult_two_polys_len.
[in,out]buf0Buffer of the same length as the FFTs. Must be allocated allocated and free by the user using fnft__fft_wrapper_malloc and fnft__fft_wrapper_free, respectively.
[in,out]buf1See buf0.
[in,out]buf2See buf0.
[in]add_flagFlag either 0 or 1. If add_flag = 1 is passed then the result of polynomial multiplication is added to the values already present in result. If add_flag = 0 then the values in result are overwritten.
Returns
FNFT_SUCCESS or one of the FNFT_EC_... error codes defined in fnft_errwarn.h.

◆ fnft__poly_fmult_two_polys2x2()

FNFT_INT fnft__poly_fmult_two_polys2x2 ( const FNFT_UINT  deg,
FNFT_COMPLEX const *const  p1_11,
const FNFT_UINT  p1_stride,
FNFT_COMPLEX const *const  p2_11,
const FNFT_UINT  p2_stride,
FNFT_COMPLEX *const  result_11,
const FNFT_UINT  result_stride,
fnft__fft_wrapper_plan_t  plan_fwd,
fnft__fft_wrapper_plan_t  plan_inv,
FNFT_COMPLEX *const  buf0,
FNFT_COMPLEX *const  buf1,
FNFT_COMPLEX *const  buf2 
)

Multiplies two 2x2 matrices of polynomials.

Fast multiplication of two 2x2 matrices of polynomials using the FFT.

Parameters
degDegree of the polynomials.
[in]p1_11Array of deg+1 coefficients for the upper left polynomial p1_11(z) of the first matrix p1(z).
[in]p1_strideThe deg+1 coefficients of the other polynomials p1_12(z), p1_21(z) and p1_22(z) in the first matrix are expected to be stored at p1_11+p1_stride, p1_11+2*p1_stride and p1+3*p1_stride, respectively.
[in]p2_11Array of deg+1 coefficients for the upper left polynomial p2_11(z) of the second matrix p2(z).
[in]p2_strideThe deg+1 coefficients of the other polynomials p2_12(z), p2_21(z) and p2_22(z) in the first matrix are expected to be stored at p2_11+p2_stride, p2_11+2*p2_stride and p2+3*p2_stride, respectively.
[out]result_11Array in which the 2*deg+1 coefficients of the upper left polynomial result_11(z) of the product result(z)=p1(z)*p2(z) will be stored.
[in]result_strideThe 2*deg+1 coefficients of the other polynomials result_12(z), result_21(z) and result_22(z) in the resulting matrix are will be stored at result_11+result_stride, result_11+2*result_stride and result+3*result_stride, respectively.
plan_fwdPlan generated by fnft__fft_wrapper_create_plan for a forward FFT of the length returned by fnft__poly_fmult_two_polys_len.
plan_invPlan generated by fnft__fft_wrapper_create_plan for an inverse FFT of the length returned by fnft__poly_fmult_two_polys_len.
[in,out]buf0Buffer of the same length as the FFTs. Must be allocated allocated and free by the user using fnft__fft_wrapper_malloc and fnft__fft_wrapper_free, respectively.
[in,out]buf1See buf0.
[in,out]buf2See buf0.
Returns
FNFT_SUCCESS or one of the FNFT_EC_... error codes defined in fnft_errwarn.h.

◆ fnft__poly_fmult_two_polys_len()

FNFT_INT fnft__poly_fmult_two_polys_len ( const FNFT_UINT  deg)

Length of the FFTs used by fnft__poly_fmult_two_polys.

Parameters
degThe degree of the polynomials to be multiplied.
Returns
The length of the (inverse) FFT (in number of complex elements) required by fnft__poly_fmult_two_polys.

◆ fnft__poly_roots_fasteigen()

FNFT_INT fnft__poly_roots_fasteigen ( const FNFT_UINT  deg,
FNFT_COMPLEX const *const  p,
FNFT_COMPLEX *const  roots 
)

Fast computation of polynomial roots.

This routine compute the roots of a polynomial

\[ p(z)=p_0+p_1 z^1+p_2 z^2+...+p_{deg} z^{deg} \]

using only \( O\{ deg^2 \}\) floating point operations.

See also
https://arxiv.org/abs/1611.02435v2
Parameters
[in]degDegree of the polynomial
[in]pArray containing the deg+1 coefficients of the polynomial in descending order (i.e., \( p_{deg}, p_{deg-1}, \dots, p_1, p_0 \)).
[out]rootsArray of deg+1 points. Will be filled with the roots of \( p(z) \).
Returns
FNFT_SUCCESS or one of the FNFT_EC_... error codes defined in fnft_errwarn.h.

◆ fnft__poly_roots_fftgridsearch()

FNFT_INT fnft__poly_roots_fftgridsearch ( const FNFT_UINT  deg,
FNFT_COMPLEX const *const  p,
FNFT_UINT *const  M_ptr,
FNFT_REAL const *const  PHI,
FNFT_COMPLEX *const  roots 
)

Unit circle roots of a polynomial via grid search.

This routine approximates the unit circle roots of a polynomial

\[ p(z)=p_0 + p_{1}z^1 + \dots p_{deg} + p_N z^{deg}, \]

where the star denote the complex conjugate. (That is, it looks for the solutions of \( p(z)=0 \) that satisfy \( |z|=1 \).) The polynomial \( p(z) \) is evaluated on the grid \( z=r_k e^{j\theta_m} \), where

\[ \theta_m=\Phi_0 + m \epsilon, \ \ \ \ m=0,1,\dots,M-1, \ \epsilon=\frac{\Phi_1 - \Phi_0}{M-1}\]

and

\[ r_k = 1 - k\epsilon, \ \ \ \ k=-1,0,1. \]

The evaluations are carried out using the Chirp transform. The grid points on the unit circle where the absolute value of the polynomial is lower than or equal to the absolute value at the eight neighboring grid points are candidates for a root. (This is the first stage of the Lindsey-Fox algorithm.) The polynomial is then approximated locally around the center grid poFNFT_INT and the root of this linerization is computed. The root of the linearization is kept if it is not too far from the grid point.

See also
https://doi.org/10.1109/MSP.2003.1253552
poly_roots_fftgridsearch_paraherm
poly_chirpz
Parameters
[in]degThe degree of the polynomial.
[in]pArray containing the deg+1 coefficients of the Laurent polynomial in descending order (i.e., \( p_{deg}, p_{deg-1}, \dots, p_{1}, p_{0} \)).
[in,out]M_ptrUpon entry, *M_ptr contains the desired value for the number of points M. Upon return, *M_ptr has been overwritten with the number of detected roots.
[in]PHIArray with two entries, \( \Phi_0 \) and \( \Phi_1 \). The first value should be lower than the second one.
[out]rootsArray of M points. Will be filled with the detected roots. (The number of detected roots is stored in *M_ptr.)
Returns
FNFT_SUCCESS or one of the FNFT_EC_... error codes defined in fnft_errwarn.h.

◆ fnft__poly_roots_fftgridsearch_paraherm()

FNFT_INT fnft__poly_roots_fftgridsearch_paraherm ( const FNFT_UINT  deg,
FNFT_COMPLEX const *const  p,
FNFT_UINT *const  M_ptr,
FNFT_REAL const *const  PHI,
FNFT_COMPLEX *const  roots 
)

Unit circle roots of a parahermitian Laurent polynomial via grid search.

This routine approximates the unit circle roots of a para-hermitian Laurent polynomial

\[ p(z)=p_{-N} + p_{-N+1} + \dots p_{N-1} + p_N, \ \ \ \ p(z)=p^*(1/z^*), \]

where the star denote the complex conjugate. (That is, it looks for the solutions of \( p(z)=0 \) that satisfy \( |z|=1 \).) The Laurent polynomial \( p(z) \) is evaluated on the grid \( z=e^{j\theta_m} \), where

\[ \theta_m=\Phi_0 + m \epsilon, \ \ \ \ m=0,1,\dots,M-1, \ \epsilon=\frac{\Phi_1 - \Phi_0}{M-1}.\]

The evaluations are carried out using the Chirp transform. Since the Laurent polynomial is para-hermitian, it will be real on the unit circle. If the sign of the Laurent polynomial changes between two consequtive points on the grid, a root is detected. The position of the roots is determined using linear interpolation.

See also
poly_roots_fftgridsearch
poly_chirpz
Parameters
[in]degThis should be the value of \( 2N+1 \).
[in]pArray containing the deg+1 coefficients of the Laurent polynomial in descending order (i.e., \( p_{N}, p_{N-1}, \dots, p_{-N+1}, p_{-N} \)).
[in,out]M_ptrUpon entry, *M_ptr contains the desired value for the number of points M. Upon return, *M_ptr has been overwritten with the number of detected roots.
[in]PHIArray with two entries, \( \Phi_0 \) and \( \Phi_1 \). The first value should be lower than the second one.
[out]rootsArray of M points. Will be filled with the detected roots. (The number of detected roots is stored in *M_ptr.)
Returns
FNFT_SUCCESS or one of the FNFT_EC_... error codes defined in fnft_errwarn.h.

◆ fnft__poly_specfact()

FNFT_INT fnft__poly_specfact ( const FNFT_UINT  deg,
FNFT_COMPLEX const *const  poly,
FNFT_COMPLEX *const  result,
const FNFT_UINT  oversampling_factor,
const FNFT_INT  kappa 
)

Spectral factorization of polynomial.

Computes the spectral factor of given polynomial with no zeros inside the unit circle.

Parameters
[in]degDegree of the polynomial.
[in]polyArray of coefficients for the polynomial.
[out]resultArray in which the coefficients of the result are stored.
[in]oversampling_factorOversampling factor is used to improve conditioning of the spectral factorization problem.
[in]kappakappa =+1 for the focusing nonlinear Schroedinger equation, =-1 for the defocusing one.
Returns
FNFT_SUCCESS or one of the FNFT_EC_... error codes defined in fnft_errwarn.h.