5 Best Ways to Generate a Monic Polynomial with Given Roots in Python

Rate this post

πŸ’‘ Problem Formulation: When working with polynomials in mathematical computing or algebra, it is often necessary to construct a monic polynomial (a polynomial with the leading coefficient of 1) from a given set of roots. For example, if we have roots 1, 2, and 3, we seek to generate the monic polynomial x^3 - 6x^2 + 11x - 6. This article outlines how to efficiently accomplish this task using Python.

Method 1: Using NumPy’s poly Function

The numpy.poly function takes a sequence of roots and returns the coefficients of the corresponding monic polynomial. This method leverages the powerful numerical computing library, NumPy, making it efficient and reliable for generating polynomials in numerical analysis and scientific computing.

Here’s an example:

import numpy as np

roots = [1, 2, 3]
coeffs = np.poly(roots)

print(coeffs)

Output:

[  1.  -6.  11.  -6.]

This code snippet first imports NumPy and then defines a list of roots. By passing this list to the np.poly function, we get an array of coefficients that form the desired monic polynomial when multiplied out.

Method 2: Using sympy’s Poly Function

The sympy library, aimed at symbolic mathematics, provides a Poly function that can create polynomial expressions with the given roots. It is particularly useful for those requiring symbolic manipulation or exact arithmetic.

Here’s an example:

from sympy import symbols, Poly

x = symbols('x')
roots = [1, 2, 3]
poly = Poly.from_roots(roots, domain='QQ')

print(poly.as_expr())

Output:

x**3 - 6*x**2 + 11*x - 6

After importing the necessary functions from sympy and defining a symbolic variable ‘x’, we use Poly.from_roots to create a polynomial with the specified roots. The as_expr method then expresses the polynomial in its expanded form.

Method 3: Building Manually with Expansion

Without relying on external libraries, a monic polynomial can be generated using manual expansion. This involves creating a polynomial (f(x)) by multiplying together the binomials formed from each root (x – root).

Here’s an example:

roots = [1, 2, 3]

def expand_polynomial(roots):
    coeffs = [1]
    for root in roots:
        coeffs = [sum(x) for x in zip(coeffs + [0], [0] + [-root * c for c in coeffs])]
    return coeffs

coeffs = expand_polynomial(roots)
print(coeffs)

Output:

[1, -6, 11, -6]

This code defines a function that gradually expands the polynomial by convolution, mimicking the process of polynomial multiplication. The resulting coefficients are printed, giving us the polynomial in coefficient form.

Method 4: Using SciPy’s lagrange Function

SciPy’s lagrange function from the interpolate module can produce a polynomial that passes through given points. Although typically used for interpolation, by supplying the roots with corresponding zero values, we can obtain the polynomial we need.

Here’s an example:

from scipy.interpolate import lagrange
from numpy.polynomial.polynomial import Polynomial

roots = [1, 2, 3]
poly = lagrange(roots, [0, 0, 0])

print(Polynomial(poly).coef)

Output:

[  1.  -6.  11.  -6.]

Here, we use the lagrange function to generate a polynomial object, using our roots as the x-values and zeros as the y-values. The Polynomial object’s coef attribute is then used to print the coefficients of the resulting monic polynomial.

Bonus One-Liner Method 5: Polynomial Multiplication One-Liner

This succinct one-liner employs list comprehension alongside Python’s reduce function to multiply out the factors of the polynomial in a compact form.

Here’s an example:

from functools import reduce

roots = [1, 2, 3]
coeffs = reduce(lambda a, b: a + [-b*i for i in a[-1:]+[0]], roots, [1])

print(coeffs)

Output:

[1, -6, 11, -6]

In a functional programming style, this one-liner uses reduce to accumulate the polynomial’s coefficients. With each iteration, it multiplies the current list of coefficients by a binomial derived from a root, effectively expanding the polynomial.

Summary/Discussion

  • Method 1: NumPy’s poly Function. It is fast and reliable, best for numerical computations. However, it requires NumPy, which may not be optimal for minimal applications or environments without external library support.
  • Method 2: sympy’s Poly Function. Offers exact arithmetic and capable of symbolic manipulation. It is ideal for theoretical work but is slower than numerical methods and requires the heavy sympy library.
  • Method 3: Building Manually with Expansion. It does not depend on external libraries and is good for educational purposes. This method is computationally less efficient and can become cumbersome for large sets of roots.
  • Method 4: SciPy’s lagrange Function. Useful for polynomials derived from interpolation and relies on the SciPy library. It can be less intuitive when used explicitly for creating polynomials from roots.
  • Bonus One-Liner Method 5: Polynomial Multiplication One-Liner. Very concise and uses only built-in functions. This method can be less readable and harder to understand for those not familiar with functional programming.