# fourier transform

Published articles for fourier transform.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## Negacyclic Polynomial Multiplication

DevFeed: [Negacyclic Polynomial Multiplication](<https://devfeed.tech/articles/negacyclic-polynomial-multiplication-40460.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2022/12/09/negacyclic-polynomial-multiplication/>)

Published: 2022-12-09T13:35:45Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [polynomials](<https://devfeed.tech/topics/polynomials.md>), [Cryptography](<https://devfeed.tech/topics/cryptography.md>), [homomorphic encryption](<https://devfeed.tech/topics/homomorphic-encryption.md>), [Encryption](<https://devfeed.tech/topics/encryption.md>), [Python](<https://devfeed.tech/topics/python.md>), [GitHub](<https://devfeed.tech/topics/github.md>)

Tags: [article](<https://devfeed.tech/tags/article.md>), [complex-twist](<https://devfeed.tech/tags/complex-twist.md>), [cryptography](<https://devfeed.tech/tags/cryptography.md>), [encryption](<https://devfeed.tech/tags/encryption.md>), [fourier-transform](<https://devfeed.tech/tags/fourier-transform.md>), [github](<https://devfeed.tech/tags/github.md>), [homomorphic-encryption](<https://devfeed.tech/tags/homomorphic-encryption.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [negacyclic](<https://devfeed.tech/tags/negacyclic.md>), [polynomial-ring](<https://devfeed.tech/tags/polynomial-ring.md>), [polynomials](<https://devfeed.tech/tags/polynomials.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>)

### AI overview

This tutorial explains three techniques for computing negacyclic polynomial products, including the simpler cyclic product as a precursor. It places these operations in the context of lattice cryptography and fully homomorphic encryption and provides Python code on GitHub.

### Source excerpt

In this article I'll cover three techniques to compute special types of polynomial products that show up in lattice cryptography and fully homomorphic encryption. Namely, the negacyclic polynomial product, which is the product of two polynomials in the quotient ring $\mathbb{Z}[x] / (x^N + 1)$. As a precursor to the negacyclic product, we'll cover the simpler cyclic product. All of the Python code written for this article is on GitHub.

## Polynomial Multiplication Using the FFT

DevFeed: [Polynomial Multiplication Using the FFT](<https://devfeed.tech/articles/polynomial-multiplication-using-the-fft-40459.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2022/11/16/polynomial-multiplication-using-the-fft/>)

Published: 2022-11-16T08:00:00Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [polynomials](<https://devfeed.tech/topics/polynomials.md>), [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [NumPy](<https://devfeed.tech/topics/numpy.md>), [Mathematics](<https://devfeed.tech/topics/mathematics.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [arrays](<https://devfeed.tech/tags/arrays.md>), [efficiently](<https://devfeed.tech/tags/efficiently.md>), [fft](<https://devfeed.tech/tags/fft.md>), [fourier-transform](<https://devfeed.tech/tags/fourier-transform.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [polynomial-interpolation](<https://devfeed.tech/tags/polynomial-interpolation.md>), [polynomials](<https://devfeed.tech/tags/polynomials.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>)

### AI overview

This tutorial explains how to multiply two polynomials efficiently using the Fast Fourier Transform. It contrasts the naive O(n^2) approach with polynomial interpolation, pointwise multiplication, and carefully chosen roots of unity that enable reusable computations.

### Source excerpt

Problem: Compute the product of two polynomials efficiently. Solution: import numpy from numpy.fft import fft, ifft def poly_mul(p1, p2): """Multiply two polynomials. p1 and p2 are arrays of coefficients in degree-increasing order. """ deg1 = p1.shape[0] - 1 deg2 = p1.shape[0] - 1 # Would be 2*(deg1 + deg2) + 1, but the next-power-of-2 handles the +1 total_num_pts = 2 * (deg1 + deg2) next_power_of_2 = 1 << (total_num_pts - 1).

## The Two-Dimensional Fourier Transform and Digital Watermarking

DevFeed: [The Two-Dimensional Fourier Transform and Digital Watermarking](<https://devfeed.tech/articles/the-two-dimensional-fourier-transform-and-digital-watermarking-40336.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2013/12/30/the-two-dimensional-fourier-transform-and-digital-watermarking/>)

Published: 2013-12-30T19:24:05Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [fourier transform](<https://devfeed.tech/topics/fourier-transform.md>), [watermarking](<https://devfeed.tech/topics/watermarking.md>), [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [Code](<https://devfeed.tech/topics/code.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [animations](<https://devfeed.tech/tags/animations.md>), [big-o-notation](<https://devfeed.tech/tags/big-o-notation.md>), [calculus](<https://devfeed.tech/tags/calculus.md>), [dimension](<https://devfeed.tech/tags/dimension.md>), [fft](<https://devfeed.tech/tags/fft.md>), [fourier-analysis](<https://devfeed.tech/tags/fourier-analysis.md>), [fourier-transform](<https://devfeed.tech/tags/fourier-transform.md>), [github](<https://devfeed.tech/tags/github.md>), [graphics](<https://devfeed.tech/tags/graphics.md>), [image-manipulation](<https://devfeed.tech/tags/image-manipulation.md>), [images](<https://devfeed.tech/tags/images.md>), [james-hance](<https://devfeed.tech/tags/james-hance.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [matrices](<https://devfeed.tech/tags/matrices.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>), [star-wars](<https://devfeed.tech/tags/star-wars.md>), [up](<https://devfeed.tech/tags/up.md>), [watermarking](<https://devfeed.tech/tags/watermarking.md>)

### AI overview

This tutorial introduces the multidimensional Fourier transform, explains its relationship to the one-dimensional transform, describes an FFT-style algorithm for computing it, and applies it to digitally watermarking images.

### Source excerpt

We've studied the Fourier transform quite a bit on this blog: with four primers and the Fast Fourier Transform algorithm under our belt, it's about time we opened up our eyes to higher dimensions. Indeed, in the decades since Cooley & Tukey's landmark paper, the most interesting applications of the discrete Fourier transform have occurred in dimensions greater than 1. But for all our work we haven't yet discussed what it means to take an "n-dimensional" Fourier transform.

## The Fast Fourier Transform

DevFeed: [The Fast Fourier Transform](<https://devfeed.tech/articles/the-fast-fourier-transform-40280.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2012/07/18/the-fast-fourier-transform/>)

Published: 2012-07-18T08:00:54Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [processing](<https://devfeed.tech/topics/processing.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [analysis](<https://devfeed.tech/tags/analysis.md>), [audio](<https://devfeed.tech/tags/audio.md>), [divide-and-conquer](<https://devfeed.tech/tags/divide-and-conquer.md>), [fourier-analysis](<https://devfeed.tech/tags/fourier-analysis.md>), [fourier-transform](<https://devfeed.tech/tags/fourier-transform.md>), [graphics](<https://devfeed.tech/tags/graphics.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [processing](<https://devfeed.tech/tags/processing.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>), [signal-processing](<https://devfeed.tech/tags/signal-processing.md>), [sound](<https://devfeed.tech/tags/sound.md>)

### AI overview

A tutorial on the Fast Fourier Transform explains its historical development, the improvement from O(n^2) to O(n log n) computation for the discrete Fourier transform, and a derivation and implementation approach. It also explores audio denoising by filtering a noisy signal's frequency spectrum.

### Source excerpt

It's often said that the Age of Information began on August 17, 1964 with the publication of Cooley and Tukey's paper, "An Algorithm for the Machine Calculation of Complex Fourier Series." They published a landmark algorithm which has since been called the Fast Fourier Transform algorithm, and has spawned countless variations. Specifically, it improved the best known computational bound on the discrete Fourier transform from $ O(n^2)$ to $ O(n \log n)$, which is the difference between uselessness and panacea.

## The Discrete Fourier Transform -- A Primer

DevFeed: [The Discrete Fourier Transform -- A Primer](<https://devfeed.tech/articles/the-discrete-fourier-transform-a-primer-40278.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2012/06/23/the-discrete-fourier-transform/>)

Published: 2012-06-23T14:13:53Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Programming](<https://devfeed.tech/topics/programming.md>)

Tags: [analysis](<https://devfeed.tech/tags/analysis.md>), [course](<https://devfeed.tech/tags/course.md>), [fourier-analysis](<https://devfeed.tech/tags/fourier-analysis.md>), [fourier-transform](<https://devfeed.tech/tags/fourier-transform.md>), [function](<https://devfeed.tech/tags/function.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [primer](<https://devfeed.tech/tags/primer.md>), [vector-spaces](<https://devfeed.tech/tags/vector-spaces.md>)

### AI overview

This primer explains the intuitive connections between continuous and discrete Fourier transforms. It covers discrete approximations of functions and transforms, the transition between discrete representations, and the role of sampling as motivation.

### Source excerpt

So here we are. We have finally made it to a place where we can transition with confidence from the classical continuous Fourier transform to the discrete version, which is the foundation for applications of Fourier analysis to programming. Indeed, we are quite close to unfurling the might of the Fast Fourier Transform algorithm, which efficiently computes the discrete Fourier transform. But because of its focus on algorithmic techniques, we will save it for a main content post and instead focus here on the intuitive connections between the discrete and continuous realms.

## Generalized Functions -- A Primer

DevFeed: [Generalized Functions -- A Primer](<https://devfeed.tech/articles/generalized-functions-a-primer-40275.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2012/06/06/generalized-functions/>)

Published: 2012-06-06T20:57:05Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Mathematics](<https://devfeed.tech/topics/mathematics.md>), [Math and Logic](<https://devfeed.tech/topics/math-and-logic.md>), [abstraction](<https://devfeed.tech/topics/abstraction.md>), [Programming](<https://devfeed.tech/topics/programming.md>)

Tags: [abstraction](<https://devfeed.tech/tags/abstraction.md>), [fourier-analysis](<https://devfeed.tech/tags/fourier-analysis.md>), [fourier-transform](<https://devfeed.tech/tags/fourier-transform.md>), [functional-analysis](<https://devfeed.tech/tags/functional-analysis.md>), [generalized-functions](<https://devfeed.tech/tags/generalized-functions.md>), [linear-algebra](<https://devfeed.tech/tags/linear-algebra.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [primer](<https://devfeed.tech/tags/primer.md>), [programming](<https://devfeed.tech/tags/programming.md>), [theory](<https://devfeed.tech/tags/theory.md>)

### AI overview

This primer develops a more rigorous mathematical framework for Fourier transforms. It motivates the search for a class of functions that remains well behaved under the Fourier transform and its inverse, while avoiding divergent integrals.

### Source excerpt

Last time we investigated the naive (which I'll henceforth call "classical") notion of the Fourier transform and its inverse. While the development wasn't quite rigorous, we nevertheless discovered elegant formulas and interesting properties that proved useful in at least solving differential equations. Of course, we wouldn't be following this trail of mathematics if it didn't result in some worthwhile applications to programming. While we'll get there eventually, this primer will take us deeper down the rabbit hole of abstraction.

## The Fourier Transform -- A Primer

DevFeed: [The Fourier Transform -- A Primer](<https://devfeed.tech/articles/the-fourier-transform-a-primer-40274.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2012/05/27/the-fourier-transform-a-primer/>)

Published: 2012-05-27T19:00:15Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [fourier transform](<https://devfeed.tech/topics/fourier-transform.md>), [function](<https://devfeed.tech/topics/function.md>)

Tags: [analysis](<https://devfeed.tech/tags/analysis.md>), [convergence](<https://devfeed.tech/tags/convergence.md>), [convolution](<https://devfeed.tech/tags/convolution.md>), [duality](<https://devfeed.tech/tags/duality.md>), [fourier-analysis](<https://devfeed.tech/tags/fourier-analysis.md>), [fourier-transform](<https://devfeed.tech/tags/fourier-transform.md>), [function](<https://devfeed.tech/tags/function.md>), [limit](<https://devfeed.tech/tags/limit.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [primer](<https://devfeed.tech/tags/primer.md>)

### AI overview

This primer introduces the Fourier transform as a limiting case of the Fourier series for functions without periodic behavior. It develops the transform from intuitive definitions and then addresses convergence more rigorously using distributions.

### Source excerpt

In our last primer we saw the Fourier series, which flushed out the notion that a periodic function can be represented as an infinite series of sines and cosines. While this is fine and dandy, and quite a powerful tool, it does not suffice for the real world. In the real world, very little is truly periodic, especially since human measurements can only record a finite period of time. Even things we wish to explore on this blog are hardly periodic (for instance, image analysis).