Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Fast Fourier Transform: Polynomial Multiplication

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 (27)

Fast Fourier transform

A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in the frequency domain and vice versa. The DFT is obtained by decomposing a sequence of values into components of different frequencies. This operation is useful in many fields, but computing it directly from the definition is often too slow to be practical.

Fourier transform

In physics and mathematics, the Fourier transform (FT) is a transform that converts a function into a form that describes the frequencies present in the original function. The output of the transform is a complex-valued function of frequency. The term Fourier transform refers to both this complex-valued function and the mathematical operation. When a distinction needs to be made the Fourier transform is sometimes called the frequency domain representation of the original function.

Discrete Fourier transform

In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency. The interval at which the DTFT is sampled is the reciprocal of the duration of the input sequence. An inverse DFT (IDFT) is a Fourier series, using the DTFT samples as coefficients of complex sinusoids at the corresponding DTFT frequencies.

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.

Root of unity

In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power n. Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory of group characters, and the discrete Fourier transform. Roots of unity can be defined in any field. If the characteristic of the field is zero, the roots are complex numbers that are also algebraic integers.

Related lectures (38)

The fast Fourier transform

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

Numerical Methods: Boundary Value Problems

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

Fourier Series and Analysis

Covers Fourier series, analysis, the heat equation, Gibbs phenomenon, and Fourier transform properties.

Fourier Analysis: Fourier Series and Transform

Explores Fourier series, DFT, FFT, and their applications in signal processing and spectroscopy.

Neurophysiological Data Analysis