Multiplication of Polynomials using Discrete Fourier Transformation

Krzysztof Treyderowski; Christoph Schwarzweller

doi:10.2478/v10037-006-0015-y

.blurhash-client-img { display: none !important; }

Multiplication of Polynomials using Discrete Fourier Transformation

Formalized Mathematics

Volume 14 (2006): Issue 4 (December 2006)

By: Krzysztof Treyderowski and Christoph Schwarzweller

Open Access

|Jun 2008

Read online

Abstract

In this article we define the Discrete Fourier Transformation for univariate polynomials and show that multiplication of polynomials can be carried out by two Fourier Transformations with a vector multiplication in-between. Our proof follows the standard one found in the literature and uses Vandermonde matrices, see e.g. [27].

References

[1] Grzegorz Bancerek. The fundamental properties of natural numbers. Formalized Mathematics, 1(1):41-46, 1990.
Search in Google Scholar
[2] Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Formalized Mathematics, 1(1):107-114, 1990.
Search in Google Scholar
[3] Czesław Byliński. Binary operations. Formalized Mathematics, 1(1):175-180, 1990.
Search in Google Scholar
[4] Czesław Byliński. Finite sequences and tuples of elements of a non-empty sets. Formalized Mathematics, 1(3):529-536, 1990.
Search in Google Scholar
[5] Czesław Byliński. Functions and their basic properties. Formalized Mathematics, 1(1):55-65, 1990.
Search in Google Scholar
[6] Czesław Byliński. Functions from a set to a set. Formalized Mathematics, 1(1):153-164, 1990.
Search in Google Scholar
[7] Katarzyna Jankowska. Matrices. Abelian group of matrices. Formalized Mathematics, 2(4):475-480, 1991.
Search in Google Scholar
[8] Eugeniusz Kusak, Wojciech Leończuk, and Michał Muzalewski. Abelian groups, fields and vector spaces. Formalized Mathematics, 1(2):335-342, 1990.
Search in Google Scholar
[9] Robert Milewski. The evaluation of polynomials. Formalized Mathematics, 9(2):391-395, 2001.
Search in Google Scholar
[10] Robert Milewski. Fundamental theorem of algebra. Formalized Mathematics, 9(3):461-470, 2001.
Search in Google Scholar
[11] Robert Milewski. The ring of polynomials. Formalized Mathematics, 9(2):339-346, 2001.
Search in Google Scholar
[12] Michał Muzalewski. Construction of rings and left-, right-, and bi-modules over a ring. Formalized Mathematics, 2(1):3-11, 1991.
Search in Google Scholar
[13] Michał Muzalewski and Wojciech Skaba. From loops to abelian multiplicative groups with zero. Formalized Mathematics, 1(5):833-840, 1990.
Search in Google Scholar
[14] Michał Muzalewski and Lesław W. Szczerba. Construction of finite sequences over ring and left-, right-, and bi-modules over a ring. Formalized Mathematics, 2(1):97-104, 1991.
Search in Google Scholar
[15] Takaya Nishiyama and Yasuho Mizuhara. Binary arithmetics. Formalized Mathematics, 4(1):83-86, 1993.
Search in Google Scholar
[16] Jan Popiołek. Real normed space. Formalized Mathematics, 2(1):111-115, 1991.
Search in Google Scholar
[17] Konrad Raczkowski. Integer and rational exponents. Formalized Mathematics, 2(1):125-130, 1991.
Search in Google Scholar
[18] Christoph Schwarzweller. The binomial theorem for algebraic structures. Formalized Mathematics, 9(3):559-564, 2001.
Search in Google Scholar
[19] Andrzej Trybulec. Subsets of complex numbers. To appear in Formalized Mathematics.
Search in Google Scholar
[20] Andrzej Trybulec. Tarski Grothendieck set theory. Formalized Mathematics, 1(1):9-11, 1990.
Search in Google Scholar
[21] Andrzej Trybulec. Tuples, projections and Cartesian products. Formalized Mathematics, 1(1):97-105, 1990.
Search in Google Scholar
[22] Michał J. Trybulec. Integers. Formalized Mathematics, 1(3):501-505, 1990.
Search in Google Scholar
[23] Wojciech A. Trybulec. Groups. Formalized Mathematics, 1(5):821-827, 1990.
Search in Google Scholar
[24] Wojciech A. Trybulec. Pigeon hole principle. Formalized Mathematics, 1(3):575-579, 1990.
Search in Google Scholar
[25] Wojciech A. Trybulec. Vectors in real linear space. Formalized Mathematics, 1(2):291-296, 1990.
Search in Google Scholar
[26] Zinaida Trybulec. Properties of subsets. Formalized Mathematics, 1(1):67-71, 1990.
Search in Google Scholar
[27] J. von zur Gathen and J. Gerhard Modern Computer Algebra. Cambridge University Press, 1999.
Search in Google Scholar
[28] Edmund Woronowicz. Relations and their basic properties. Formalized Mathematics, 1(1):73-83, 1990.
Search in Google Scholar
[29] Katarzyna Zawadzka. The product and the determinant of matrices with entries in a field. Formalized Mathematics, 4(1):1-8, 1993.
Search in Google Scholar

Articles in this issue

DOI: https://doi.org/10.2478/v10037-006-0015-y | Journal eISSN: 1898-9934 | Journal ISSN: 1426-2630

Journal RSS Feed

Language: English

Page range: 121 - 128

Published online: Jun 13, 2008

Published in print: Jan 1, 2006

Published by: University of Białystok

In partnership with: Paradigm Publishing Services

Related subjects:

Computer sciences,

Artificial intelligence,

Computer sciences, other,

Mathematics,

Logic and set theory,

General mathematics

© 2008 Krzysztof Treyderowski, Christoph Schwarzweller, published by University of Białystok
This work is licensed under the Creative Commons License.

Volume 14 (2006): Issue 4 (December 2006)