Representing polynomials

The package uses the Polynomial class to represent and manipulate Laurent polynomials.

P = Polynomial([0.4, 0.3, 0.5, 0.7])

\[ P(z) = 0.4 + 0.3z + 0.5z^2 + 0.7 z^3 \]

It is possible to shift the coefficients by specifying where the support should start with support_start

P = Polynomial([0.4, 0.3, 0.5, 0.7], support_start=-2)

\[ P(z) = 0.4z^{-2} + 0.3z^{-1} + 0.5 + 0.7 z \]

Accessing coefficients

After the polynomial is allocated, it is possible to get or set individual coefficients using the subscript operation:

from nlft_qsp import *

P = Polynomial([0.4, 0.3, 0.5, 0.7], support_start=-2)
print(P[-2])
P[4] = 5
print(P[3])
print(P[4])

(0.4+0j)
0j
(5+0j)

The subscript does not work only with the originally allocated indices. If an element outside the original support is accessed, then zero is returned, while if such an element is set then the coefficient list and support start will be reallocated accordingly.

Note

Setting the coefficients is the only way to modify a Polynomial object after it is created. All the other methods will always produce a new polynomial.

Support of the polynomial

The support() method returns a Python range containing the indices of all the coefficients appearing in the polynomial:

from nlft_qsp import *

P = Polynomial([0.4, 0.3, 0.5, 0.7], support_start=-2)
print(0 in P.support())
print(2 in P.support())

True
False

Warning

support() simply checks support_start and the length of the internal coefficient list, not the actual mathematical support of the polynomial.

from nlft_qsp import *

Q = Polynomial([1, 0, 0, 0])
print(3 in Q.support())

True

Evaluation

A polynomial can be evaluated by simply calling it with an input complex number.

from nlft_qsp import *

P = Polynomial([4j, 2])
print("P(z) =", P)
print("P(1 + 2j) =", P(1 + 2j))

P(z) = 4j z^0 + (2+0j) z^1
P(1 + 2j) = (2+8j)

Sometimes it might be useful to evaluate \(P(e^{2\pi i k/N})\) for the \(N\)-th roots of unity \(e^{2\pi i k/N}\). While it is possible to evaluate each term separately in \(\mathcal{O}(N^2)\) using the above code, it is possible to do it in \(\mathcal{O}(N \log N)\) using a Fast Fourier transform. This is done by the eval_at_roots_of_unity() method.

from nlft_qsp import *

P = Polynomial([4j, 2])
print(P.eval_at_roots_of_unity(16))

[ 2.        +4.j          1.84775907+4.76536686j  1.41421356+5.41421356j
  0.76536686+5.84775907j  0.        +6.j         -0.76536686+5.84775907j
 -1.41421356+5.41421356j -1.84775907+4.76536686j -2.        +4.j
 -1.84775907+3.23463314j -1.41421356+2.58578644j -0.76536686+2.15224093j
  0.        +2.j          0.76536686+2.15224093j  1.41421356+2.58578644j
  1.84775907+3.23463314j]

Note

Currently eval_at_roots_of_unity(N) method assumes \(N\) to be a power of two. If a non-power of two is passed then the next power of two is assumed.