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

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 on: Jun 13, 2008

Published by: University of Białystok

In partnership with: Paradigm Publishing Services

Publication frequency: 1 issue per year

Related subjects:

Mathematics,

Logic and set theory,

Computer sciences,

Artificial intelligence

© 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)