Math dj_fft

### Details

This repository provides a header-only library to compute fourier transforms in 1D, 2D, and 3D. Its goal is to provide a fast and easy-to-use fast fourier transform algorithm.

### Cloning

Clone the repository and all its submodules using the following command:

`git clone --recursive [email protected]:jdupuy/dj_fft.git`

If you accidentally omitted the `--recursive` flag when cloning the repository you can retrieve the submodules like so:

`git submodule update --init --recursive`

### Usage

The 1D, 2D, and 3D FFT routines return an `std::vector<std::complex<T>>`, given another `std::vector<std::complex<T>>` as input, which specifies the data that must be transformed, as well as an enum class `dj::fft_dir`, which specifies in which direction the FFT must be computed (specify `dj::fft_dir::DIR_FWD` for the forward direction and `dj::fft_dir::DIR_BWD` for the backward direction).

Note that the input vector is expected to be of size `N` for 1D FFT, `NxN` for a 2D FFT, and `NxNxN` for a 3D FFT, where `N` must be a power of two. Note that the 2D and 3D vectors are expected to be arranged in a flat row-major fashion, i.e., the 2D and 3D elements `(i, j)` and `(i, j, k)` are respectively located at index `i + N * j` and `i + N * (j + N * k)` in memory.

Below is a C++ pseudocode for computing a 2D FFT in forward direction:

```#define DJ_FFT_IMPLEMENTATION // define this in exactly *one* .cpp file
#include "dj_fft.h"

some_function()
{
int N = size_of_your_input; // input size
auto myData = std::vector<std::complex<T>>(N * N); // input data

// prepare data
for (int j = 0; j < N; ++j) {
for (int i = 0; i < N; ++i) {
myData[i + N * j] = some_value; // set element (i, j)
}
}

// compute forward 2D FFT
auto fftData = dj::fft2d(myData, dj::fft_dir::DIR_FWD);

// print the data
for (int j = 0; j < N; ++j) {
for (int i = 0; i < N; ++i) {
printf("{%f, %f} ", fftData[i + N * j].real(), fftData[i + N * j].imag());
}
printf("\n");
}
}```

To see examples that compile, see the examples/ directory.

### GPU Acceleration

Additionally, the library provides GPU accelerated 1D, 2D, and 3D FFTs for `std::vector<std::complex<float>>` inputs. GPU acceleration is especially relevant for large 2D and 3D datasets. For instance:

• for an input of size 4096x4096, a regular 2D FFT completes in roughly 18 seconds on an intel i7-8086k, and 0.9 seconds on an NVidia RTX 2080
• for an input of size 512x512x512, a regular 3D FFT completes in roughly 131 seconds on an intel i7-8086k, and 8.2 seconds on an NVidia RTX 2080

The following table provides a more comprehensive set of measurements for 2D FFTs:

2D FFT Resolution 256² 512² 1024² 2048² 4096² 8192²
CPU (i7-8086k) 0.05s 0.22s 0.99s 4.32s 18.85s 81.96s
GPU (RTX 2080) 0.01s 0.02s 0.07s 0.24s 0.94s 3.68s
GPU speed-up x5 x11 x14 x18 x20 x22

The following table provides a more comprehensive set of measurements for 3D FFTs:

3D FFT Resolution 64³ 128³ 256³ 512³
CPU (i7-8086k) 0.19s 1.72s 15.70s 141.18s
GPU (RTX 2080) 0.04s 0.15s 1.03s 8.10s
GPU speed-up x5 x11 x15 x17

Below is a C++ pseudocode for computing a 1D FFT in backward direction on the GPU:

```#define DJ_FFT_IMPLEMENTATION // define this in exactly *one* .cpp file
#include "dj_fft.h"

some_function()
{
int N = size_of_your_input; // input size
auto myData = std::vector<std::complex<float>>(N); // input data

// prepare data
for (int i = 0; i < N; ++i) {
myData[i] = some_float_value; // set element (i)
}

// compute backward 1D FFT
auto fftData = dj::fft1d_gpu(myData, dj::fft_dir::FFT_BWD);

// print the data
for (int i = 0; i < N; ++i) {
printf("{%f, %f}\n", fftData[i].real(), fftData[i].imag());
}
}```

Note that the return values of a GPU FFT may differ slightly from that of a regular FFT, due to the way floating point arithmetic is implemented.

For a complete example that compiles, see the examples/ directory.

By default, the GPU accelerated routines run on the primary GPU. Users who want to run the FFT on a secondary GPU will have to create an OpenGL context themselves and use the `fftNd_gpu_glready` functions. You can create a custom OpenGL context with a cross-platform windowing library such as GLFW (https://www.glfw.org/), and an OpenGL function loader such as glad (https://glad.dav1d.de/). I'll probably add a sample at some point.

This library is in the public domain. You can do anything you want with them. You have no legal obligation to do anything else, although I appreciate attribution.

It is also licensed under the MIT open source license, if you have lawyers who are unhappy with public domain. The `dj_fft.h` source file includes an explicit dual-license for you to choose from.

##### A work-in-progress C++20/23 header-only maths library for game development, embedded, kernel and general-purpose that works in constant context.

kMath /kmæθ/ A work-in-progress general-purpose C++20/23 header-only maths library that works in constant context Abstract The kMath Project aims to p

##### A C++ header only library for decomposition of spectra into a sum of response functions whose weights are positive definite.

DecompLib A C++ header only library for decomposition of spectra into a sum of response functions whose weights are positive definite. Introduction Bu

##### A matrix header-only library, uses graphs internally, helpful when your matrix is part of a simulation where it needs to grow many times (or auto expand)

GraphMat Header-only Library Matrix implemented as a graph, specially for the use case when it should be auto expanding at custom rate, specially in s

##### linalg.h is a single header, public domain, short vector math library for C++

linalg.h linalg.h is a single header, public domain, short vector math library for C++. It is inspired by the syntax of popular shading and compute la

##### A C library for statistical and scientific computing

Apophenia is an open statistical library for working with data sets and statistical or simulation models. It provides functions on the same level as t

##### P(R*_{3, 0, 1}) specialized SIMD Geometric Algebra Library

Klein 👉 👉 Project Site 👈 👈 Description Do you need to do any of the following? Quickly? Really quickly even? Projecting points onto lines, lines t

##### LibTomMath is a free open source portable number theoretic multiple-precision integer library written entirely in C.

libtommath This is the git repository for LibTomMath, a free open source portable number theoretic multiple-precision integer (MPI) library written en

##### a lean linear math library, aimed at graphics programming. Supports vec3, vec4, mat4x4 and quaternions

linmath.h -- A small library for linear math as required for computer graphics linmath.h provides the most used types required for programming compute

• #### Licensing problems prevent dj_fft from being used in most software

Public domain is a difficult concept to work around when it comes to OSS licensing and incorporating code into projects. Furthermore, dj_fft does not declare this formally using a document like CC0, meaning a few things:

• The definition of 'public domain' rests in the jurisdiction of the licensee or user
• Public domain software may be able to be revoked in some cases and jurisdictions.
• The status of the software being public domain is almost certainly illegitimate with such a small clause stating so (that does not explicitly waive copyright)
• You may be liable for your software that you release in public domain (ie. if your compute shader FFT implementation contributes to damaging graphics hardware)

Additionally, the incorporeality of public domain software in OSS projects encounters a problem with sub-licensing, where this is a gray area (the CC0 license is more explicit in this case and probably won't cause an issue, but your declaration of public domain makes this a problem).

Assuming you wished to grant full rights to your users, I suggest:

• Releasing the code under MIT
• Or, dual licensing the code under CC0 and MIT if you have a good reason to prefer the code released in the public domain.

However, if want to keep your software available to the public including modifications to it, use the GPLv3.

Obligatory: I am not a lawyer and this is not formal legal advice

opened by jarcode-foss 5
• #### Add new version of dj_fft::fft1d which avoids returning a new std::vector

I just added this function to my local version, and thought that it might be useful for others as well.

I've not used dj_fft::fft2d or dj_fft::fft3d, but I imagine similar versions can be added for those as well.

opened by MulattoKid 4
• #### 1dfft does not return correct result

Hello,

I'm struggling here with the algorithm.

I'm comparing the result of R's fft and another fft's I found on the internet and the result is not the same as dj-fft.

For example:

complex_vector = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}

fft(complex_vector) returns:

`````` [1] 11.0625353+0.0000073i -1.2694808-1.8365898i -0.8289607-1.0336070i -0.6982133-0.6797898i -0.6415854-0.4676793i -0.6127618-0.3175757i -0.5972594-0.1986772i
[8] -0.5894584-0.0958635i -0.5870695-0.0000038i -0.5894589+0.0958638i -0.5972596+0.1986813i -0.6127663+0.3175770i -0.6415888+0.4676792i -0.6982226+0.6797901i
[15] -0.8289628+1.0336033i -1.2694881+1.8365879i
``````

but the correct should be:

`````` [1] 136+ 0.000000i  -8+40.218716i  -8+19.313708i  -8+11.972846i  -8+ 8.000000i  -8+ 5.345429i  -8+ 3.313708i  -8+ 1.591299i  -8+ 0.000000i  -8- 1.591299i  -8- 3.313708i
[12]  -8- 5.345429i  -8- 8.000000i  -8-11.972846i  -8-19.313708i  -8-40.218716i
``````

I'm trying to find where is the problem meanwhile.

Thank you.

opened by franzbischoff 1
• #### Readme usage example error

Nothing big; just noticed that the enum class, specifying the direction in which to calculate the FFT, is outdated in the usage example in the README file. It should be dj::fft_dir::DIR_FWD and not dj::fft_dir::FFT_FWD.

Thanks for the repo - really useful 👍

opened by MulattoKid 1
###### A C++ header-only library of statistical distribution functions.

StatsLib StatsLib is a templated C++ library of statistical distribution functions, featuring unique compile-time computing capabilities and seamless

423 Jan 3, 2023
###### RcppFastFloat: Rcpp Bindings for the fastfloat C++ Header-Only Library

Converting ascii text into (floating-point) numeric values is a very common problem. The fast_float header-only C++ library by Daniel Lemire does this very well, and very fast at up to or over to 1 gigabyte per second as described in more detail in a recent arXiv paper.

18 Nov 15, 2022
###### C++ header-only fixed-point math library

fpm A C++ header-only fixed-point math library. "fpm" stands for "fixed-point math". It is designed to serve as a drop-in replacement for floating-poi

392 Jan 7, 2023
###### C++ header-only library with methods to efficiently encode/decode Morton codes in/from 2D/3D coordinates

Libmorton v0.2.7 Libmorton is a C++ header-only library with methods to efficiently encode/decode 64, 32 and 16-bit Morton codes and coordinates, in 2

488 Dec 31, 2022
###### Extremely simple yet powerful header-only C++ plotting library built on the popular matplotlib

matplotlib-cpp Welcome to matplotlib-cpp, possibly the simplest C++ plotting library. It is built to resemble the plotting API used by Matlab and matp

3.6k Dec 30, 2022
###### A modern, C++20-native, single-file header-only dense 2D matrix library.

A modern, C++20-native, single-file header-only dense 2D matrix library. Contents Example usage creating matrices basic operations row, col, size, sha

62 Dec 17, 2022
###### A header-only C++ library for large scale eigenvalue problems

NOTE: Spectra 1.0.0 is released, with a lot of API-breaking changes. Please see the migration guide for a smooth transition to the new version. NOTE:

609 Jan 2, 2023
###### libmpc++ is a C++ header-only library to solve linear and non-linear MPC

libmpc++ libmpc++ is a C++ library to solve linear and non-linear MPC. The library is written in modern C++17 and it is tested to work on Linux, macOS

46 Dec 20, 2022
###### Header-only C++11 library to handle physical measures

cpp-measures Header-only C++11 library to handle physical measures License: This project is released under the Mozilla Public License 2.0. Purpose Thi

20 Jun 28, 2018
###### Header only, single file, simple and efficient C++ library to compute the signed distance function to a triangle mesh

TriangleMeshDistance Header only, single file, simple and efficient C++11 library to compute the signed distance function to a triangle mesh. The dist

100 Dec 28, 2022