Lecture

Fast Fourier Transform: Polynomial Multiplication

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

MATH-489: Number theory II.d - Cryptography

. ...

Description

This lecture covers the Fast Fourier Transform (FFT) algorithm for polynomial multiplication, explaining how it transforms polynomials into vectors, performs element-wise multiplication, and reverts back to the original space. The instructor demonstrates the recursive nature of FFT, splitting polynomials into even and odd parts, and reconstructing coefficients using roots of unity. The complexity analysis of FFT is discussed, highlighting its efficiency in reducing the number of multiplications required for polynomial operations.

Instructor

Dimitar Petkov Jetchev

Official source

Related concepts (31)

Non-uniform discrete Fourier transform

In applied mathematics, the nonuniform discrete Fourier transform (NUDFT or NDFT) of a signal is a type of Fourier transform, related to a discrete Fourier transform or discrete-time Fourier transform, but in which the input signal is not sampled at equally spaced points or frequencies (or both). It is a generalization of the shifted DFT. It has important applications in signal processing, magnetic resonance imaging, and the numerical solution of partial differential equations.

Fourier analysis

In mathematics, Fourier analysis (ˈfʊrieɪ,_-iər) is the study of the way general functions may be represented or approximated by sums of simpler trigonometric functions. Fourier analysis grew from the study of Fourier series, and is named after Joseph Fourier, who showed that representing a function as a sum of trigonometric functions greatly simplifies the study of heat transfer. The subject of Fourier analysis encompasses a vast spectrum of mathematics.

Discrete Fourier transform over a ring

In mathematics, the discrete Fourier transform over a ring generalizes the discrete Fourier transform (DFT), of a function whose values are commonly complex numbers, over an arbitrary ring. Let R be any ring, let be an integer, and let be a principal nth root of unity, defined by: The discrete Fourier transform maps an n-tuple of elements of R to another n-tuple of elements of R according to the following formula: By convention, the tuple is said to be in the time domain and the index j is called time.

Multiplication algorithm

A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Efficient multiplication algorithms have existed since the advent of the decimal system. If a positional numeral system is used, a natural way of multiplying numbers is taught in schools as long multiplication, sometimes called grade-school multiplication, sometimes called the Standard Algorithm: multiply the multiplicand by each digit of the multiplier and then add up all the properly shifted results.

Polynomial ring

In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variables) with coefficients in another ring, often a field. Often, the term "polynomial ring" refers implicitly to the special case of a polynomial ring in one indeterminate over a field. The importance of such polynomial rings relies on the high number of properties that they have in common with the ring of the integers.

Related lectures (64)

The fast Fourier transform

Explores the history and efficiency of the fast Fourier transform algorithm, demonstrating its practical applications and computational advantages.

Fast Fourier Transform: Basics and Applications

Explores the Fast Fourier Transform algorithm for efficient signal processing applications, including dividing signals and analyzing complexity.

Numerical Methods: Boundary Value Problems

Covers numerical methods for solving boundary value problems using Crank-Nicolson and FFT.

Fast Fourier Transform

Explains the Fast Fourier Transform, a fast algorithm for calculating the Discrete Fourier Transform.

Fourier Series and Transforms: Introduction and Properties