Fast Fourier Transform Calculator

CS-128 Honors Final Project

Group Name

LYD

Members

• Bailiu Li (bailiul2)

• Binchao Ye (binchao2)

• Haochen Ding (hd9)

Project Introduction

Our project focuses on implementing the Cooley-Tukey Fast Fourier Transform (FFT) algorithm in Rust, leveraging SIMD instructions and multithreading for improved performance. The Cooley-Tukey FFT is a widely used algorithm for efficiently computing the discrete Fourier transform of a sequence or its inverse. By integrating SIMD (Single Instruction, Multiple Data) instructions and multithreading, we aim to maximize parallelism and exploit hardware-level optimizations for faster FFT computation.

Technical Overview

Description

• Develop the core algorithm for computing the Cooley-Tukey FFT in Rust.
• Implement both forward and inverse FFT transformations.
• Verify the correctness of the implementation through unit tests and validation against known FFT results by Matlab.
• Implement frontend interface.

Checkpoint 1

• Completion of FFT algorithm implementation.
• Integration of SIMD instructions for parallelization.
• Successful validation against test cases.

Checkpoint 2

• Completion of multithreading optimization.
• Comprehensive performance analysis and benchmarking.
• Finalization of documentation and project submission.
• Implementation of frontend interface.

Possible Challenges

• Learning the basic concepts and principles of Fast Fourier Transform
• Creating and Calculating complex numbers in Rust
• Implementing non-power-of-2 FFTs.
• Handling SIMD optimization and multi-threading
• etc.

References

Cooley–Tukey FFT algorithm RustFFT SIMD | Rust by Example The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?