Function Repository Resource:

# FastFourierGraph

Create a fast Fourier transform calculation in graphical form

 ResourceFunction["FastFourierGraph"][dim] returns an edge-weighted, time-ordered multiway graph on 2dim×2dim vertices, which describes the fast Fourier transform of a length 2dim vector. ResourceFunction["FastFourierGraph"][data] takes a list of data with length 2dim and adds it to the graph under the annotation key VertexWeight.

## Details

Edge connections and edge weights (set to the phases) are determined by recursive decomposition of FourierMatrix[2dim].
Assuming data list input, ResourceFunction["FastFourierGraph"] takes the option "Evaluate" whose default value is False.
Setting "ComputeValues"True populates values through the Graph and returns a complete evaluation through the annotation key "VertexWeight".
This technique is slow compared to Compile-based methods, but still useful for teaching purposes and complexity analysis.

## Examples

### Basic Examples (5)

Calculate the graph for the base case of the fast Fourier transform:

 In[1]:=
 Out[1]=

Plot the next induced case:

 In[2]:=
 Out[2]=

Color edges according to phases:

 In[3]:=
 Out[3]=

Notice n log n complexity in rectangular dimensions of subsequent graphs:

 In[4]:=
 Out[4]=

Blow up the graphs to see their free-form structure using "SpringElectricalEmbedding":

 In[5]:=
 Out[5]=

Create a graph from data:

 In[6]:=
 Out[6]=

### Options (5)

Use the option "ComputeValues"True to compute the transformation values while generating the graph:

 In[7]:=
 Out[7]=

See the fast Fourier transformation values by retrieving the VertexWeight:

 In[8]:=
 Out[8]=

Depict results of the calculation as above:

 In[9]:=
 Out[9]=

Compare with the standard method using FourierMatrix:

 In[10]:=
 Out[10]=

Apply a similar validation technique for different input lengths:

 In[11]:=
 Out[11]=

### Properties and Relations (1)

Compare with ButterflyGraph:

 In[12]:=
 Out[12]=

### Possible Issues (2)

Input should be a list of length 2n for some integer n>0:

 In[13]:=
 Out[13]=
 In[14]:=
 Out[14]=

Timing statistics look very slow compared to the built-in Fourier:

 In[15]:=
 Out[15]=
 In[16]:=
 Out[16]=

Compile time is relatively slow compared to ButterflyGraph:

 In[17]:=
 Out[17]=

### Neat Examples (2)

Follow the different paths a value can take from input to output:

 In[18]:=
 Out[18]=

Plot an intensity profile:

 In[19]:=
 Out[19]=