Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Publication
Split-radix algorithms for length-p^m DFT's
Abstract
The split-radix algorithm for the discrete Fourier transform of length-2^m is by now fairly popular. First, we give the reason why the split-radix algorithm is better tant any single-radix algorithm on length 2^m DFT's. Then, the split-radix approach is generalized to length-p^m DFT's. It is shown that whenever a radix-p^2 outperforms a radix-p / p^2 algorithm will outperform both of them. As an exemple, a radix-3/9 algorithm is developed for length 3^m DFT's.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Ontological neighbourhood
Related concepts (24)
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.
Divide-and-conquer algorithm
In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem. The divide-and-conquer technique is the basis of efficient algorithms for many problems, such as sorting (e.g., quicksort, merge sort), multiplying large numbers (e.
Radix sort
In computer science, radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered. For this reason, radix sort has also been called bucket sort and digital sort. Radix sort can be applied to data that can be sorted lexicographically, be they integers, words, punch cards, playing cards, or the mail.
Related publications (38)
Verification of the Fourier-enhanced 3D finite element Poisson solver of the gyrokinetic full-f code PICLS
Laurent Villard, Stephan Brunner, Alberto Bottino, Moahan Murugappan
We introduce and derive the Fourier -enhanced 3D electrostatic field solver of the gyrokinetic full -f PIC code PICLS. The solver makes use of a Fourier representation in one periodic direction of the domain to make the solving of the system easily paralle ...
Elsevier2024The Claude Debussy Solo Piano Corpus
Martin Alois Rohrmeier, Johannes Hentschel, Gabriele Cecchetti, Sabrina Laneve, Ludovica Schaerf
This dataset originates from the DCML corpus initiative and contains musicological research data. For more information, please refer to its documentation page https://dcmlab.github.io/debussy_piano Please cite this dataset as Laneve, S., Schaerf ...
EPFL Infoscience2023The diachronic development of Debussy’s musical style: a corpus study with Discrete Fourier Transform
Martin Alois Rohrmeier, Johannes Hentschel, Gabriele Cecchetti, Sabrina Laneve, Ludovica Schaerf
Claude Debussy’s personal style is typically characterised as a departure from earlier diatonic tonality, including a greater variety of pitch-class materials organised in fragmented yet coherent compositions. Exploiting the music-theoretical interpretabil ...
2023Related MOOCs (11)
Digital Signal Processing I
Basic signal processing concepts, Fourier analysis and filters. This module can
be used as a starting point or a basic refresher in elementary DSP
Digital Signal Processing II
Adaptive signal processing, A/D and D/A. This module provides the basic
tools for adaptive filtering and a solid mathematical framework for sampling and
quantization
Digital Signal Processing III
Advanced topics: this module covers real-time audio processing (with
examples on a hardware board), image processing and communication system design.