# PencilFFTs

Fast Fourier transforms of MPI-distributed Julia arrays.

## Introduction

This package provides multidimensional FFTs and related transforms on MPI-distributed Julia arrays via the PencilArrays package.

The name of this package originates from the decomposition of 3D domains along two out of three dimensions, sometimes called pencil decomposition. This is illustrated by the figure below,[1] where each coloured block is managed by a different MPI process. Typically, one wants to compute FFTs on a scalar or vector field along the three spatial dimensions. In the case of a pencil decomposition, 3D FFTs are performed one dimension at a time, along the non-decomposed direction. Transforms must then be interleaved with global data transpositions to switch between pencil configurations. In high-performance computing environments, such data transpositions are generally the most expensive part of a parallel FFT computation, due to the large cost of communications between computing nodes.

More generally, PencilFFTs allows to decompose and perform FFTs on geometries of arbitrary dimension $N$. The decompositions can be performed along an arbitrary number $M < N$ of dimensions.[2] Moreover, the transforms applied along each dimension can be arbitrarily chosen (and combined) among those supported by FFTW.jl, including complex-to-complex, real-to-complex and real-to-real transforms.

The generic and efficient implementation of this package is greatly enabled by the use of zero-cost abstractions in Julia. As shown in the Benchmarks section, PencilFFTs scales well to large numbers of processes, and performs similarly to the Fortran implementation of P3DFFT, possibly the most popular library for computing parallel FFTs using 2D domain decomposition.

## Features

• distributed N-dimensional FFTs of MPI-distributed Julia arrays, using the PencilArrays package;

• FFTs and related transforms (e.g. DCTs / Chebyshev transforms) may be arbitrarily combined along different dimensions;

• in-place and out-of-place transforms;

• high scalability up to (at least) tens of thousands of MPI processes.

## Installation

PencilFFTs can be installed using the Julia package manager:

julia> ] add PencilFFTs

## Similar projects

• FFTW3 implements distributed-memory transforms using MPI, but these are limited to 1D decompositions. Also, this functionality is not currently included in the FFTW.jl wrappers.

• PFFT is a very general parallel FFT library written in C.

• P3DFFT implements parallel 3D FFTs using pencil decomposition in Fortran and C++.

• 2DECOMP&FFT is another parallel 3D FFT library using pencil decomposition written in Fortran.

• 1Figure adapted from this PhD thesis.
• 2For the pencil decomposition represented in the figure, $N = 3$ and $M = 2$.