# Polynomial multiplication using the DFT?

How to do polynomial multiplication using the discrete Fourier transform in SageMath?

Polynomial multiplication using the DFT?

How to do polynomial multiplication using the discrete Fourier transform in SageMath?

1

Here is the example from the article in SageMath:

```
sage: R.<x> = PolynomialRing(QQ)
sage: f = 1 + x
sage: g = 1 + x + x^2
sage: fg_deg = f.degree() + g.degree()
sage: I_f = IndexedSequence([f.monomial_coefficient(x^d) for d in range(fg_deg+1)], list(range(fg_deg+1)))
sage: I_g = IndexedSequence([g.monomial_coefficient(x^d) for d in range(fg_deg+1)], list(range(fg_deg+1)))
sage: I_fg = IndexedSequence(list(vector(I_f.dft().list()).pairwise_product(vector(I_g.dft().list()))), list(range(fg_deg+1))).idft()
sage: fg = sum(c*x^k for k,c in I_fg.dict().items())
sage: fg == f*g
True
```

Please start posting anonymously - your entry will be published after you log in or create a new account.

Asked: ** 2022-03-02 14:47:10 +0100 **

Seen: **410 times**

Last updated: **Mar 02 '22**

Univariate Polynomial Multiplication

Is it possible to get implicitly multiplied output?

Multivariate Polynomials over Rational Function Fields

How do I Pass a tuple as an argument for a multivariate polynomial?

Is there an example of how i could write a polynomial as a product of linear factors

multi-symmetric functions and multi-partitions

Related: DST and polynomial multiplication.