# 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 +0200 **

Seen: **29 times**

Last updated: **Mar 02**

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

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.

Related: DST and polynomial multiplication.