Polynomial multiplication using the DFT?
How to do polynomial multiplication using the discrete Fourier transform in SageMath?
How to do polynomial multiplication using the discrete Fourier transform in SageMath?
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.