PhastFT

PhastFT 是一个纯 Rust 编写的、高性能的“量子启发”快速傅里叶变换 (FFT) 库。

特性

• 使用 Cooley-Tukey FFT 算法简单实现
• 性能与其他 Rust FFT 实现相当
• 无 unsafe 代码
• 利用最新的 CPU 特性（包括但不限于 AVX-512），即使在没有这些特性时也能良好运行
• 运行时选择最快的实现。无需 -C target-cpu=native!
• 可选地对某些步骤进行并行化，使用 2 个线程（计划更多）
• 比 RustFFT 低 2 倍的内存使用
• Python 绑定（通过 PyO3）

限制

• 仅支持长度为 2^n 的输入（即 2 的幂）-- 输入应填充零到下一个 2 的幂
• 由于使用可移植 SIMD，需要 nightly Rust 编译器

计划中的特性

• Bluestein 算法（用于处理任意大小的 FFT）
• 更多多线程
• 更多关于缓存优化的 FFT 的工作

为什么这么快？

PhastFT 是围绕现代硬件的能力和限制（即过去 10 年左右制造的任何东西）设计的。

FFT 的两个主要瓶颈是 CPU 周期 和 内存访问。

我们选择了一个高效、通用的 FFT 算法。我们的实现可以利用最新的 CPU 特性，如 AVX-512，即使在没有这些特性的情况下也能良好运行。

我们加快内存访问的关键洞察是，快速傅里叶变换（FFT）等价于对[0, n)中的所有量子比特应用门。这为我们利用与高性能量子态模拟器（Spinoza）相同的内存访问模式提供了机会。

我们还对大数据集使用Cache-Optimal Bit Reversal Algorithm（COBRA），并可选择在2个并行线程上运行它，进一步加速。

所有这些结合起来，结果是一个快速高效的FFT实现，其性能与现有Rust FFT库（包括RustFFT）相当，同时使用的内存显著减少。

快速入门

Rust

use phastft::{
    planner::Direction,
    fft_64
};

let big_n = 1 << 10;
let mut reals: Vec<f64> = (1..=big_n).map(|i| i as f64).collect();
let mut imags: Vec<f64> = (1..=big_n).map(|i| i as f64).collect();
fft_64(&mut reals, &mut imags, Direction::Forward);

Python

按照https://rustup.rs/上的说明安装Rust，然后使用以下命令切换到nightly频道：

rustup default nightly

然后您可以安装PhastFT本身

pip install numpy
pip install git+https://github.com/QuState/PhastFT#subdirectory=pyphastft

import numpy as np
from pyphastft import fft

sig_re = np.asarray(sig_re, dtype=np.float64)
sig_im = np.asarray(sig_im, dtype=np.float64)

fft(a_re, a_im)

归一化

phastft不归一化输出。用户可以在运行正向FFT后跟随反向FFT后，通过将每个元素乘以1/N来归一化输出，其中N是数据点的数量。

输出顺序

phastft总是通过在处理后的数据上运行位反转置换来结束输入数据的处理。

基准测试

PhastFT与几个其他FFT库进行了基准测试。重现基准测试结果和图表的脚本和说明可在此处找到。

贡献

欢迎为PhastFT做出贡献！如果您发现任何问题或建议改进，请打开一个问题或提交一个拉取请求。请按照CONTRIBUTING.md文件中概述的贡献指南操作。

许可

PhastFT根据您的选择，受MIT或Apache 2.0许可协议的约束。

PhastFT与RustFFT的比较

RustFFT是另一个纯Rust的出色FFT实现。RustFFT和PhastFT做出了不同的权衡。

RustFFT选择在稳定的Rust编译器上工作，这以牺牲unsafe代码为代价，而PhastFT不包含unsafe块，但需要Rust编译器的nightly构建来访问可移植SIMD API。

RustFFT实现了多个FFT算法，并尝试根据工作负载选择最佳算法，而PhastFT只有一个FFT实现，但仍能实现具有竞争力的性能。

PhastFT使用的内存比RustFFT少2倍，这对于处理大数据集非常重要。

这个名字是什么意思？

名称PhastFT来自量子傅里叶变换（QFT）的实现。具体来说，QFT的量子电路实现由P相门和Hadamard门组成。因此，PhastFT。