### Install Butterfly CUDA Implementation

Source: https://github.com/hazyresearch/butterfly/blob/master/README.md

This section provides instructions for installing the fast CUDA implementation of the butterfly multiply. It involves running the setup.py script. An example using conda to create an environment and install dependencies before the setup is also shown.

```shell
python setup.py install
```

```shell
conda create --name butterfly python=3.8 scipy pytorch=1.8.1 cudatoolkit=11.0 -c pytorch
conda activate butterfly
python setup.py install
```

--------------------------------

### Start Ray Cluster for Distributed Training

Source: https://github.com/hazyresearch/butterfly/blob/master/learning_transforms/README.md

These commands demonstrate how to start and stop a Ray cluster for distributed training. Ensure you are in the correct directory before executing these commands.

```bash
cd ../
./ray.sh start
```

```bash
cd ../
./ray.sh stop
```

--------------------------------

### Run Experiment with Specific Parameters

Source: https://github.com/hazyresearch/butterfly/blob/master/learning_transforms/README.md

This command shows how to execute a training job using Python, specifying parameters like target, model, and size. This is an example of how to run a training job after starting the Ray cluster.

```python
python learning_transforms.py with target=dft model=BP size=8
```

--------------------------------

### Install Butterfly PyTorch Extensions (Old Interface)

Source: https://github.com/hazyresearch/butterfly/blob/master/README.md

Instructions for installing the C++/CUDA PyTorch extensions for butterfly multiplication, specifically for the old interface. This is done by navigating to the respective directories and running setup.py.

```shell
cd butterfly/factor_multiply
python setup.py install
cd butterfly/factor_multiply_fast
python setup.py install
```

--------------------------------

### Run ImageNet Distributed Training with Python

Source: https://github.com/hazyresearch/butterfly/blob/master/cnn/README.md

Initiate distributed training for ImageNet experiments using the `imagenet_experiment.py` script and Python's multiprocess module. This command requires specifying learning rate, epochs, and the directory for ImageNet data. Refer to the fastAI documentation for detailed setup.

```python
python -m multiproc imagenet_experiment.py --lr 0.4 --epochs 45 --small [DIR FOR IMAGENET DATA]
```

--------------------------------

### Run CIFAR10 Single-Node Training with Python

Source: https://github.com/hazyresearch/butterfly/blob/master/cnn/README.md

Execute single-node training for CIFAR10 experiments using the `cifar_experiment.py` script. This command allows specifying the model, optimizer, and other training parameters. Ensure the script is available in your project.

```python
python cifar_experiment.py with model=LeNet optimizer=SGD lr_decay=True weight_decay=True
```

--------------------------------

### 2D FFT Implementation and Comparison (PyTorch)

Source: https://context7.com/hazyresearch/butterfly/llms.txt

Implements and demonstrates a 2D Fast Fourier Transform using butterfly factorizations. It includes comparisons with PyTorch's built-in torch.fft.fft2 for both standard and flattened versions, and an example of 2D frequency filtering.

```python
import torch
import torch_butterfly.special as special
import torch.fft

n1, n2 = 64, 128  # height, width
batch_size = 8

# Create 2D FFT module
fft2d_module = special.fft2d(n1, n2, normalized=True, br_first=True, with_br_perm=True, flatten=False)

# Complex 2D input
input_2d = torch.randn(batch_size, n2, n1, dtype=torch.complex64)

# Compare with torch.fft.fft2
output_butterfly = fft2d_module(input_2d)
output_torch = torch.fft.fft2(input_2d, norm='ortho')

print(f"2D FFT match: {torch.allclose(output_butterfly, output_torch, rtol=1e-3, atol=1e-5)}")
print(f"Output shape: {output_butterfly.shape}")

# Flattened version (combines into single butterfly, only works for power-of-2)
fft2d_flat = special.fft2d(n1, n2, normalized=True, br_first=True, with_br_perm=True, flatten=True)
output_flat = fft2d_flat(input_2d)
print(f"Flattened 2D FFT match: {torch.allclose(output_flat, output_torch, rtol=1e-3, atol=1e-5)}")

# Image processing example: 2D frequency filtering
def lowpass_filter_image(image, cutoff_ratio=0.1):
    # image: (batch, height, width) real values
    fft2d = special.fft2d(image.shape[1], image.shape[2], normalized=True,
                          br_first=True, with_br_perm=True, flatten=False)
    ifft2d = special.ifft2d(image.shape[1], image.shape[2], normalized=True,
                            br_first=True, with_br_perm=True, flatten=False)

    # Convert to complex and compute 2D FFT
    image_complex = torch.view_as_complex(torch.stack([image, torch.zeros_like(image)], dim=-1))
    freq_domain = fft2d(image_complex)

    # Create lowpass mask (keep low frequencies near DC)
    h, w = freq_domain.shape[1], freq_domain.shape[2]
    cutoff_h = int(h * cutoff_ratio)
    cutoff_w = int(w * cutoff_ratio)
    mask = torch.zeros_like(freq_domain)
    mask[:, :cutoff_h, :cutoff_w] = 1.0
    mask[:, -cutoff_h:, :cutoff_w] = 1.0
    mask[:, :cutoff_h, -cutoff_w:] = 1.0
    mask[:, -cutoff_h:, -cutoff_w:] = 1.0

    # Apply filter and inverse FFT
    filtered_freq = freq_domain * mask
    filtered_image = ifft2d(filtered_freq).real

    return filtered_image

image = torch.randn(4, 64, 128)
filtered = lowpass_filter_image(image, cutoff_ratio=0.2)
print(f"Filtered image shape: {filtered.shape}")
```

--------------------------------

### Single Channel Circular Convolution Example (PyTorch)

Source: https://context7.com/hazyresearch/butterfly/llms.txt

Demonstrates the usage of a single-channel circular convolution using the special.conv1d_circular_singlechannel function. It initializes weights, applies the convolution, and prints the output shape.

```python
import torch
import torch_butterfly.special as special

kernel_size = 512
n = 512
batch_size = 16

single_channel_weight = torch.randn(1, 1, kernel_size)
butterfly_single = special.conv1d_circular_singlechannel(n, single_channel_weight, separate_diagonal=False)
signal = torch.randn(batch_size, n)
output_single = butterfly_single(signal)
print(f"Single channel output shape: {output_single.shape}")
```

--------------------------------

### 2D Circular Convolution Implementation (PyTorch)

Source: https://context7.com/hazyresearch/butterfly/llms.txt

Implements efficient 2D convolution with circular boundary conditions using 2D FFT butterfly factorization. It shows the setup for both a standard Conv2d with manual padding and the butterfly-based approach for comparison.

```python
import torch
import torch.nn as nn
import torch.nn.functional as F
import torch_butterfly.special as special

# Image dimensions
n1, n2 = 64, 64
batch_size = 8
in_channels = 3
out_channels = 16
kernel_size = 7

# Create standard Conv2d for comparison
padding = (kernel_size - 1) // 2
conv2d = nn.Conv2d(in_channels, out_channels, kernel_size, padding=0, bias=False)

# Input image: (batch, channels, height, width)
input_image = torch.randn(batch_size, in_channels, n1, n2)

# Standard circular convolution with manual padding
input_padded = F.pad(input_image, (padding, padding, padding, padding), mode='circular')
output_conv2d = conv2d(input_padded)

# Butterfly-based circular convolution (efficient)
weight = conv2d.weight  # (out_channels, in_channels, kernel_h, kernel_w)
butterfly_conv2d = special.conv2d_circular_multichannel(n2, n1, weight, flatten=False)

```

--------------------------------

### Learnable Circular Convolution Layer (PyTorch)

Source: https://context7.com/hazyresearch/butterfly/llms.txt

Defines and demonstrates a learnable 1D circular convolution layer using PyTorch's nn.Module. It utilizes special.conv1d_circular_multichannel for the convolution operation and shows an example of its usage with random input.

```python
import torch
import torch.nn as nn
import torch_butterfly.special as special

class LearnableCircularConv1d(nn.Module):
    def __init__(self, in_channels, out_channels, signal_length, kernel_size):
        super().__init__()
        self.weight = nn.Parameter(torch.randn(out_channels, in_channels, kernel_size))
        self.signal_length = signal_length

    def forward(self, x):
        # x shape: (batch, in_channels, signal_length)
        butterfly_conv = special.conv1d_circular_multichannel(
            self.signal_length,
            self.weight
        )
        x_transposed = x.transpose(1, 2)  # (batch, length, channels)
        output = butterfly_conv(x_transposed)
        return output.transpose(1, 2)  # (batch, out_channels, length)

learnable_conv = LearnableCircularConv1d(3, 8, 512, 15)
x = torch.randn(16, 3, 512)
y = learnable_conv(x)
print(f"Learnable conv output: {y.shape}")
```

--------------------------------

### Hadamard Transform with Butterfly Factorization

Source: https://context7.com/hazyresearch/butterfly/llms.txt

Implements the Fast Walsh-Hadamard Transform (FWHT) using butterfly factorizations, useful for error correction, cryptography, and machine learning. It includes examples for creating normalized transforms, verifying self-inverse properties, and checking orthogonality. Dependencies include PyTorch and butterfly.special. Inputs are random tensors, and outputs are tensors representing the transformed signal.

```python
import torch
import torch_butterfly.special as special

n = 1024
batch_size = 16

# Create normalized Hadamard transform
hadamard = special.hadamard(n, normalized=True, increasing_stride=True)
input_signal = torch.randn(batch_size, n)

output = hadamard(input_signal)
print(f"Output shape: {output.shape}")  # torch.Size([16, 1024])

# Verify self-inverse property (H @ H = I for normalized)
reconstructed = hadamard(output)
print(f"Self-inverse: {torch.allclose(input_signal, reconstructed, rtol=1e-3, atol=1e-5)}")

# Verify orthogonality
eye = torch.eye(n)
hadamard_matrix = hadamard(eye).t()
should_be_identity = hadamard_matrix @ hadamard_matrix.t()
print(f"Orthogonal: {torch.allclose(should_be_identity, torch.eye(n), rtol=1e-3, atol=1e-5)}")
```

--------------------------------

### Implement Unitary Butterfly Layer for Norm-Preserving Transformations in PyTorch

Source: https://context7.com/hazyresearch/butterfly/llms.txt

Illustrates the use of `ButterflyUnitary` to create butterfly matrices that are constrained to be unitary (or orthogonal for real matrices). This is useful for reversible architectures and maintaining gradient flow, with examples verifying unitarity and demonstrating a reversible block.

```python
from torch_butterfly import ButterflyUnitary
import torch.nn as nn

# Create a unitary butterfly layer (always complex)
size = 256
unitary_layer = ButterflyUnitary(
    in_size=size,
    out_size=size,
    bias=False,
    increasing_stride=True,
    nblocks=2
)

# Verify unitarity: U @ U^H = I
input_eye = torch.eye(size, dtype=torch.complex64)
butterfly_matrix = unitary_layer(input_eye).t()
result = butterfly_matrix @ butterfly_matrix.conj().t()
identity = torch.eye(size, dtype=torch.complex64)

print(f"Is unitary: {torch.allclose(result, identity, rtol=1e-3, atol=1e-5)}")  # True
print(f"Max deviation from identity: {(result - identity).abs().max().item():.6f}")

# Use for norm-preserving transformations in deep networks
class ReversibleBlock(nn.Module):
    def __init__(self, size):
        super().__init__()
        self.transform = ButterflyUnitary(size, size, bias=False, nblocks=2)

    def forward(self, x):
        x_complex = torch.view_as_complex(torch.stack([x, torch.zeros_like(x)], dim=-1))
        y_complex = self.transform(x_complex)
        return y_complex.real

    def inverse(self, y):
        y_complex = torch.view_as_complex(torch.stack([y, torch.zeros_like(y)], dim=-1))
        x_complex = self.transform(y_complex, transpose=True, conjugate=True)
        return x_complex.real

block = ReversibleBlock(128)
x = torch.randn(10, 128)
y = block.forward(x)
x_reconstructed = block.inverse(y)
print(f"Reconstruction error: {(x - x_reconstructed).abs().max().item():.6f}")
```

--------------------------------

### Compile Cython Extension for Speed Benchmark

Source: https://github.com/hazyresearch/butterfly/blob/master/learning_transforms/README.md

This command compiles the Cython extension, which is necessary for running the speed benchmark. It uses Python's setup.py script with the build_ext --inplace arguments.

```bash
python setup.py build_ext --inplace
```

--------------------------------

### Exact FFT Implementation with Butterfly Factorization in PyTorch

Source: https://context7.com/hazyresearch/butterfly/llms.txt

This snippet shows how to create an exact Fast Fourier Transform (FFT) module using butterfly factorization. It supports normalized (unitary) and unnormalized transforms, and allows for learnable FFT variants by fine-tuning the initialized module. Comparisons with `torch.fft` are included to verify accuracy.

```python
import torch_butterfly.special as special
import torch
import torch.nn as nn

# Create exact FFT using butterfly factorization
n = 256
batch_size = 16

# Normalized FFT (unitary transform)
fft_module = special.fft(n, normalized=True, br_first=True, with_br_perm=True)
input_signal = torch.randn(batch_size, n, dtype=torch.complex64)

# Compare with torch.fft
output_butterfly = fft_module(input_signal)
output_torch = torch.fft.fft(input_signal, norm='ortho')

print(f"FFT match: {torch.allclose(output_butterfly, output_torch, rtol=1e-3, atol=1e-5)}")  # True
print(f"Max error: {(output_butterfly - output_torch).abs().max().item():.6e}")

# Unnormalized FFT
fft_unnorm = special.fft(n, normalized=False, br_first=True, with_br_perm=True)
output_unnorm = fft_unnorm(input_signal)
output_torch_unnorm = torch.fft.fft(input_signal, norm=None)
print(f"Unnorm FFT match: {torch.allclose(output_unnorm, output_torch_unnorm, rtol=1e-3, atol=1e-5)}")

# Create learnable FFT variant (start from exact FFT, then fine-tune)
learnable_fft = special.fft(n, normalized=True, br_first=True, with_br_perm=False)
optimizer = torch.optim.Adam(learnable_fft.parameters(), lr=1e-3)

# Fine-tune to learn a custom transform
target_output = torch.randn(batch_size, n, dtype=torch.complex64)
for epoch in range(100):
    output = learnable_fft(input_signal)
    loss = nn.functional.mse_loss(output, target_output)
    optimizer.zero_grad()
    loss.backward()
    optimizer.step()

print(f"Final loss after learning: {loss.item():.6f}")
```

--------------------------------

### Bit-reversal and Wavelet Permutations with FixedPermutation Layer

Source: https://context7.com/hazyresearch/butterfly/llms.txt

Demonstrates the usage of bit-reversal and wavelet permutations for fixed operations. It shows how to create a FixedPermutation layer, apply it to input data, and verify the correctness of the permutation, including its inverse. This is useful for operations like FFT where specific permutation orders are required.

```python
from torch_butterfly.permutation import (
    FixedPermutation,
    bitreversal_permutation,
    wavelet_permutation,
    invert
)
import torch
import numpy as np

n = 256
batch_size = 16

# Bit-reversal permutation (used in FFT)
br_perm = bitreversal_permutation(n, pytorch_format=True)
br_layer = FixedPermutation(br_perm)

input_data = torch.randn(batch_size, n)
output = br_layer(input_data)
print(f"Bit-reversal output shape: {output.shape}")

# Verify correct bit-reversal
for i in range(min(10, n)):
    binary = format(i, f'0{int(np.log2(n))}b')
    reversed_binary = binary[::-1]
    j = int(reversed_binary, 2)
    print(f"{i:3d} (binary: {binary}) -> {br_perm[i]:3d} (binary: {reversed_binary})")

# Inverse permutation
br_perm_inv = invert(br_perm)
br_inv_layer = FixedPermutation(br_perm_inv)
reconstructed = br_inv_layer(output)
print(f"Permutation inverse: {torch.allclose(input_data, reconstructed)}")

# Wavelet permutation
wavelet_perm = wavelet_permutation(n, pytorch_format=True)
wavelet_layer = FixedPermutation(wavelet_perm)
output_wavelet = wavelet_layer(input_data)
print(f"Wavelet permutation output: {output_wavelet.shape}")
```

--------------------------------

### Implement Butterfly Layer for Linear Transformations in PyTorch

Source: https://context7.com/hazyresearch/butterfly/llms.txt

Demonstrates how to create and use the Butterfly layer as a drop-in replacement for `nn.Linear` in PyTorch. It shows initialization with different weights and its integration into a simple neural network model for training.

```python
import torch
from torch_butterfly import Butterfly

# Create a butterfly layer as a linear transformation
batch_size = 32
in_features = 1024
out_features = 512

# Initialize with random weights
 butterfly_layer = Butterfly(
    in_size=in_features,
    out_size=out_features,
    bias=True,
    complex=False,
    increasing_stride=True,
    init='randn',
    nblocks=1
)

# Forward pass
input_data = torch.randn(batch_size, in_features)
output = butterfly_layer(input_data)
print(f"Input shape: {input_data.shape}")   # torch.Size([32, 1024])
print(f"Output shape: {output.shape}")       # torch.Size([32, 512])

# Use as a replacement for nn.Linear in a neural network
import torch.nn as nn

model = nn.Sequential(
    Butterfly(784, 256, bias=True, init='ortho'),
    nn.ReLU(),
    Butterfly(256, 128, bias=True, init='ortho'),
    nn.ReLU(),
    Butterfly(128, 10, bias=True)
)

# Train with standard PyTorch optimizers
optimizer = torch.optim.Adam(model.parameters(), lr=1e-3)
criterion = nn.CrossEntropyLoss()

mist_input = torch.randn(16, 784)
labels = torch.randint(0, 10, (16,))
output = model(mist_input)
loss = criterion(output, labels)
loss.backward()
optimizer.step()
```

--------------------------------

### Discrete Cosine Transform (DCT) Implementation with Butterfly Factorization

Source: https://context7.com/hazyresearch/butterfly/llms.txt

Implements DCT types II, III, and IV using butterfly factorizations, suitable for image/video compression and signal processing. It compares the butterfly implementation against SciPy's DCT for validation and demonstrates the inverse properties of DCT types. Dependencies include PyTorch, SciPy, and butterfly.special. Inputs are real tensors, and outputs are real tensors matching SciPy's results.

```python
import torch
import torch_butterfly.special as special
import scipy.fft

n = 128
batch_size = 10

# DCT Type-II (most common, used in JPEG)
dct_module = special.dct(n, type=2, normalized=True)
input_signal = torch.randn(batch_size, n)

output_butterfly = dct_module(input_signal)
output_scipy = torch.tensor(scipy.fft.dct(input_signal.numpy(), type=2, norm='ortho'))

print(f"DCT-II match: {torch.allclose(output_butterfly, output_scipy, rtol=1e-3, atol=1e-5)}")

# DCT Type-III (inverse of Type-II)
dct3_module = special.dct(n, type=3, normalized=True)
output_dct2 = dct_module(input_signal)
reconstructed = dct3_module(output_dct2)
print(f"DCT-II/III inverse: {torch.allclose(input_signal, reconstructed, rtol=1e-3, atol=1e-5)}")

# DCT Type-IV (self-inverse)
dct4_module = special.dct(n, type=4, normalized=True)
output_dct4 = dct4_module(input_signal)
reconstructed_dct4 = dct4_module(output_dct4)
print(f"DCT-IV self-inverse: {torch.allclose(input_signal, reconstructed_dct4, rtol=1e-3, atol=1e-5)}")

# Image compression example using DCT blocks
def compress_image_blocks(image, block_size=8, keep_coeffs=16):
    # image shape: (batch, height, width)
    dct_block = special.dct(block_size, type=2, normalized=True)

    # Process 8x8 blocks
    h, w = image.shape[1], image.shape[2]
    compressed = []
    for i in range(0, h, block_size):
        for j in range(0, w, block_size):
            block = image[:, i:i+block_size, j:j+block_size]
            # Apply 1D DCT to rows then columns
            dct_rows = dct_block(block.reshape(-1, block_size)).reshape(block.shape)
            dct_full = dct_block(dct_rows.transpose(1, 2)).transpose(1, 2)
            # Keep only top coefficients (compression)
            dct_full_flat = dct_full.reshape(-1, block_size * block_size)
            dct_full_flat[:, keep_coeffs:] = 0
            compressed.append(dct_full_flat)
    return compressed

image = torch.randn(2, 64, 64)
compressed = compress_image_blocks(image)
print(f"Compressed {len(compressed)} blocks with {keep_coeffs}/64 coefficients each")
```

--------------------------------

### Inverse FFT using Butterfly Structure in PyTorch

Source: https://context7.com/hazyresearch/butterfly/llms.txt

This code demonstrates the creation and usage of an inverse Fast Fourier Transform (iFFT) module based on butterfly factorization. It supports both normalized and unnormalized transforms for efficient frequency-to-time domain conversion.

```python
import torch_butterfly.special as special

n = 512
batch_size = 8

# Create inverse FFT module
ifft_module = special.ifft(n, normalized=True, br_first=True, with_br_perm=True)

# Note: The actual usage and comparison would follow, similar to the FFT example.
```

--------------------------------

### Converting Permutations to Butterfly Factorization

Source: https://context7.com/hazyresearch/butterfly/llms.txt

Illustrates how to convert an arbitrary permutation (random or otherwise) into its butterfly factorization representation. This allows for learnable and parameter-efficient approximations of the original permutation, suitable for fine-tuning within neural network architectures.

```python
from torch_butterfly.permutation import FixedPermutation
import torch

n = 256
batch_size = 16

random_perm = torch.randperm(n)
perm_layer = FixedPermutation(random_perm)

# Convert to butterfly for learning
perm_butterfly = perm_layer.to_butterfly(complex=False, increasing_stride=True)

# Now can fine-tune this butterfly to learn variations
input_test = torch.randn(batch_size, n)
output_fixed = perm_layer(input_test)
output_butterfly = perm_butterfly(input_test)
print(f"Initial butterfly approximation error: {(output_fixed - output_butterfly).abs().max().item():.4f}")
```

--------------------------------

### Fastfood Random Feature Maps for Kernel Approximation (PyTorch)

Source: https://context7.com/hazyresearch/butterfly/llms.txt

Implements the Fastfood algorithm for approximating kernel methods using random feature maps. It utilizes PyTorch's nn.Module for learnable parameters and SciPy's hadamard function for matrix operations. This module approximates the function H @ Diag @ Perm @ H @ Diag.

```python
import torch
import torch.nn as nn
from scipy import special

class FastfoodFeatures(nn.Module):
    def __init__(self, input_dim, num_features):
        super().__init__()
        assert input_dim == num_features  # Simplified version
        self.num_features = num_features

        # Hadamard matrices
        self.H1 = special.hadamard(num_features, normalized=True, increasing_stride=True)
        self.H2 = special.hadamard(num_features, normalized=True, increasing_stride=False)

        # Diagonal scaling matrices (learnable)
        self.diag1 = nn.Parameter(torch.randn(num_features))
        self.diag2 = nn.Parameter(torch.randn(num_features))
        self.diag3 = nn.Parameter(torch.randn(num_features))

        # Random permutation
        self.register_buffer('perm', torch.randperm(num_features))

    def forward(self, x):
        # Fastfood transform: H @ Diag @ Perm @ H @ Diag
        x = x * self.diag1
        x = self.H1(x)
        x = x[:, self.perm]
        x = x * self.diag2
        x = self.H2(x)
        x = x * self.diag3
        return x

features = FastfoodFeatures(1024, 1024)
x = torch.randn(32, 1024)
random_features = features(x)
print(f"Random features shape: {random_features.shape}")  # torch.Size([32, 1024])
```

--------------------------------

### Circulant Matrix Multiplication using Butterfly Transforms (PyTorch)

Source: https://context7.com/hazyresearch/butterfly/llms.txt

Demonstrates efficient circulant matrix multiplication using FFT-based butterfly transforms. This module is useful for circular convolutions and solving Toeplitz systems. It supports both real and complex matrices and can be tested against explicit matrix multiplication using SciPy.

```python
import torch_butterfly.special as special
import torch.nn.functional as F
import torch
from scipy.linalg import circulant

n = 256
batch_size = 8

# Define circulant matrix by its first column
first_column = torch.randn(n)

# Create circulant multiplication module
circulant_module = special.circulant(first_column, transposed=False, separate_diagonal=True)

# Test against explicit matrix multiplication
C = circulant(first_column.numpy())
input_vec = torch.randn(batch_size, n)
output_explicit = torch.tensor(input_vec.numpy() @ C.T)
output_butterfly = circulant_module(input_vec)

print(f"Circulant match: {torch.allclose(output_butterfly, output_explicit, rtol=1e-3, atol=1e-5)}")
print(f"Max error: {(output_butterfly - output_explicit).abs().max().item():.6e}")

# Example: Circular convolution using circulant multiplication
def circular_conv_via_circulant(signal, kernel):
    n = signal.shape[-1]
    kernel_size = kernel.shape[-1]

    # Pad kernel to signal length and create circulant matrix
    padding = (kernel_size - 1) // 2
    kernel_padded = F.pad(kernel, (0, n - kernel_size)).roll(-padding, dims=-1)

    circulant_conv = special.circulant(kernel_padded, separate_diagonal=False)
    return circulant_conv(signal)

signal = torch.randn(batch_size, n)
kernel = torch.randn(15)  # Small kernel
conv_output = circular_conv_via_circulant(signal, kernel)
print(f"Circular convolution output shape: {conv_output.shape}")

# Complex circulant matrices
first_column_complex = torch.randn(n, dtype=torch.complex64)
circulant_complex = special.circulant(first_column_complex, transposed=False, separate_diagonal=True)
input_complex = torch.randn(batch_size, n, dtype=torch.complex64)
output_complex = circulant_complex(input_complex)
print(f"Complex circulant output shape: {output_complex.shape}")
```

--------------------------------

### Using Permutations within Custom Linear Layers

Source: https://context7.com/hazyresearch/butterfly/llms.txt

Shows how to integrate permutation operations (bit-reversal, wavelet, or random) directly into custom PyTorch modules, specifically within a `nn.Linear` layer. This enables the creation of permutation-aware linear transformations that can be trained end-to-end.

```python
import torch.nn as nn
from torch_butterfly.permutation import FixedPermutation, bitreversal_permutation, wavelet_permutation
import torch

class PermutedLinear(nn.Module):
    def __init__(self, size, perm_type='random'):
        super().__init__()
        if perm_type == 'random':
            perm = torch.randperm(size)
        elif perm_type == 'bitreversal':
            perm = bitreversal_permutation(size, pytorch_format=True)
        elif perm_type == 'wavelet':
            perm = wavelet_permutation(size, pytorch_format=True)

        self.perm = FixedPermutation(perm)
        self.linear = nn.Linear(size, size)

    def forward(self, x):
        x = self.perm(x)
        return self.linear(x)

perm_linear = PermutedLinear(256, perm_type='bitreversal')
x = torch.randn(32, 256)
y = perm_linear(x)
print(f"Permuted linear output: {y.shape}")
```

--------------------------------

### 1D Circular Convolution using Butterfly Transforms (PyTorch)

Source: https://context7.com/hazyresearch/butterfly/llms.txt

Implements efficient 1D circular convolution using butterfly transforms, providing an O(n log n) alternative to standard `nn.Conv1d` with circular padding. This enables efficient learning of convolutional filters with circular boundary conditions.

```python
import torch_butterfly.special as special
import torch.nn as nn
import torch
import torch.nn.functional as F

# Input parameters
n = 512  # Signal length
batch_size = 16
in_channels = 3
out_channels = 8
kernel_size = 15

# Create standard Conv1d with circular padding for comparison
padding = (kernel_size - 1) // 2
conv1d = nn.Conv1d(in_channels, out_channels, kernel_size, padding=0, bias=False)
input_signal = torch.randn(batch_size, in_channels, n)

# Manual circular padding and convolution
input_padded = F.pad(input_signal, (padding, padding), mode='circular')
output_conv1d = conv1d(input_padded)

# Create butterfly-based circular convolution (more efficient)
weight = conv1d.weight  # (out_channels, in_channels, kernel_size)
butterfly_conv = special.conv1d_circular_multichannel(n, weight)

# Rearrange input from (batch, channels, length) to (batch, length) per channel
output_butterfly = butterfly_conv(input_signal.transpose(1, 2))
output_butterfly = output_butterfly.transpose(1, 2)

print(f"Conv1d output shape: {output_conv1d.shape}")  # torch.Size([16, 8, 512])
print(f"Butterfly output shape: {output_butterfly.shape}")  # torch.Size([16, 8, 512])
print(f"Match: {torch.allclose(output_butterfly, output_conv1d, rtol=1e-2, atol=1e-4)}")
```

--------------------------------

### FFT and iFFT Round-trip Test with Butterfly Factorization

Source: https://context7.com/hazyresearch/butterfly/llms.txt

Tests the round-trip capability of the FFT and iFFT modules implemented with butterfly factorizations. It verifies perfect reconstruction and calculates the maximum reconstruction error. Dependencies include PyTorch and the butterfly.special module. Inputs are random complex tensors, and outputs are boolean and float values indicating reconstruction quality.

```python
import torch
import torch_butterfly.special as special

batch_size = 1
n = 128

fft_module = special.fft(n, normalized=True, br_first=True, with_br_perm=True)
input_signal = torch.randn(batch_size, n, dtype=torch.complex64)

freq_domain = fft_module(input_signal)
# Assuming ifft_module is defined similarly or obtained from special.ifft
ifft_module = special.ifft(n, normalized=True, br_first=True, with_br_perm=True)
reconstructed = ifft_module(freq_domain)

print(f"Perfect reconstruction: {torch.allclose(input_signal, reconstructed, rtol=1e-3, atol=1e-5)}")
print(f"Max reconstruction error: {(input_signal - reconstructed).abs().max().item():.6e}")

# Unnormalized iFFT (scaling factor of 1/n)
ifft_unnorm = special.ifft(n, normalized=False, br_first=True, with_br_perm=True)
freq_input = torch.randn(batch_size, n, dtype=torch.complex64)
output_butterfly = ifft_unnorm(freq_input)
output_torch = torch.fft.ifft(freq_input, norm=None)
print(f"iFFT match: {torch.allclose(output_butterfly, output_torch, rtol=1e-3, atol=1e-5)}")
```

--------------------------------

### Batched Butterfly Matrix Multiplication with PyTorch

Source: https://context7.com/hazyresearch/butterfly/llms.txt

Demonstrates using ButterflyBmm for efficient batched matrix multiplication with multiple distinct butterfly matrices. It's useful for parallel computations in multi-head attention and ensemble models. The input tensor shape is (batch, matrix_batch, in_size), and the output shape is (batch, matrix_batch, out_size).

```python
from torch_butterfly import ButterflyBmm
import torch
import torch.nn as nn

# Create butterfly with multiple matrices
batch_size = 16
matrix_batch = 8  # Number of different butterfly matrices
in_size = 256
out_size = 256

butterfly_bmm = ButterflyBmm(
    in_size=in_size,
    out_size=out_size,
    matrix_batch=matrix_batch,
    bias=True,
    complex=False,
    increasing_stride=True,
    init='ortho',
    nblocks=1
)

# Input has shape (batch, matrix_batch, in_size)
# Each of the matrix_batch elements uses a different butterfly matrix
input_data = torch.randn(batch_size, matrix_batch, in_size)
output = butterfly_bmm(input_data)
print(f"Input shape: {input_data.shape}")    # torch.Size([16, 8, 256])
print(f"Output shape: {output.shape}")        # torch.Size([16, 8, 256])

# Example: Multi-head structured attention
class StructuredMultiHeadAttention(nn.Module):
    def __init__(self, embed_dim, num_heads):
        super().__init__()
        self.num_heads = num_heads
        self.head_dim = embed_dim // num_heads

        # Use butterfly for efficient multi-head projections
        self.qkv_projection = ButterflyBmm(
            in_size=embed_dim,
            out_size=self.head_dim,
            matrix_batch=num_heads * 3,  # Q, K, V for each head
            bias=True,
            init='ortho'
        )

    def forward(self, x):
        batch, seq_len, embed_dim = x.shape
        # Project and split into Q, K, V for each head
        x_expanded = x.unsqueeze(2).expand(batch, seq_len, self.num_heads * 3, embed_dim)
        x_flat = x_expanded.reshape(batch * seq_len, self.num_heads * 3, embed_dim)
        qkv = self.qkv_projection(x_flat)
        return qkv.view(batch, seq_len, self.num_heads * 3, self.head_dim)

attention = StructuredMultiHeadAttention(embed_dim=512, num_heads=8)
x = torch.randn(4, 20, 512)  # (batch, seq_len, embed_dim)
qkv = attention(x)
print(f"QKV shape: {qkv.shape}")  # torch.Size([4, 20, 24, 64])
```

--------------------------------

### Toeplitz Matrix Multiplication in PyTorch

Source: https://context7.com/hazyresearch/butterfly/llms.txt

Implements efficient Toeplitz matrix multiplication using `torch_butterfly.special.toeplitz`. This function embeds Toeplitz matrices into circulant matrices and utilizes FFT butterfly factorization. It supports square and non-square matrices, as well as symmetric Toeplitz matrices. It's useful for time-series analysis and autoregressive models.

```python
import torch
import torch.nn as nn
import torch_butterfly.special as special
from scipy.linalg import toeplitz

n = 128
batch_size = 10

# Define Toeplitz matrix by first column and row
first_column = torch.randn(n)
first_row = torch.randn(n)
first_row[0] = first_column[0]  # Convention: diagonal element from column

# Create Toeplitz multiplication module
toeplitz_module = special.toeplitz(first_column, first_row, separate_diagonal=True)

# Test against explicit matrix multiplication
T = toeplitz(first_column.numpy(), first_row.numpy())
input_vec = torch.randn(batch_size, n)
output_explicit = torch.tensor(input_vec.numpy() @ T.T)
output_butterfly = toeplitz_module(input_vec)

print(f"Toeplitz match: {torch.allclose(output_butterfly, output_explicit, rtol=1e-3, atol=1e-5)}")
print(f"Max error: {(output_butterfly - output_explicit).abs().max().item():.6e}")

# Symmetric Toeplitz (first_row = None defaults to conjugate of first_column)
first_column_symmetric = torch.randn(n)
toeplitz_symmetric = special.toeplitz(first_column_symmetric, None, separate_diagonal=True)
output_symmetric = toeplitz_symmetric(input_vec)
print(f"Symmetric Toeplitz output shape: {output_symmetric.shape}")  # torch.Size([10, 128])

# Example: Autoregressive model with Toeplitz structure
class ToeplitzAR(nn.Module):
    def __init__(self, seq_length, order):
        super().__init__()
        self.seq_length = seq_length
        self.order = order
        # AR coefficients as first row of Toeplitz matrix
        self.ar_coeffs = nn.Parameter(torch.randn(order))

    def forward(self, x):
        # x: (batch, seq_length)
        # Create Toeplitz matrix from AR coefficients
        first_column = torch.zeros(self.seq_length)
        first_column[0] = 1.0
        first_row = torch.zeros(self.seq_length)
        first_row[:self.order] = self.ar_coeffs
        first_row[0] = 1.0

        toeplitz_op = special.toeplitz(first_column, first_row, separate_diagonal=False)
        return toeplitz_op(x)

ar_model = ToeplitzAR(seq_length=256, order=10)
time_series = torch.randn(16, 256)
predicted = ar_model(time_series)
print(f"AR prediction shape: {predicted.shape}")  # torch.Size([16, 256])

# Non-square Toeplitz
n_out = 100
n_in = 150
col = torch.randn(n_out)
row = torch.randn(n_in)
row[0] = col[0]
toeplitz_nonsquare = special.toeplitz(col, row, separate_diagonal=True)
input_nonsquare = torch.randn(batch_size, n_in)
output_nonsquare = toeplitz_nonsquare(input_nonsquare)
print(f"Non-square Toeplitz output: {output_nonsquare.shape}")  # torch.Size([10, 100])
```

--------------------------------

### Circular Conv2d Layer in PyTorch

Source: https://context7.com/hazyresearch/butterfly/llms.txt

Defines a learnable circular Conv2d layer using `torch_butterfly.special.conv2d_circular_multichannel`. This layer is suitable for image filtering and can be integrated into sequential models. It expects input tensors of shape (batch, in_channels, height, width).

```python
import torch
import torch.nn as nn
import torch_butterfly.special as special

class CircularConv2d(nn.Module):
    def __init__(self, in_channels, out_channels, height, width, kernel_size):
        super().__init__()
        self.height = height
        self.width = width
        self.weight = nn.Parameter(torch.randn(out_channels, in_channels,
                                                kernel_size, kernel_size))

    def forward(self, x):
        # x shape: (batch, in_channels, height, width)
        conv_module = special.conv2d_circular_multichannel(
            self.width, self.height, self.weight, flatten=True
        )
        return conv_module(x)

circ_conv_layer = CircularConv2d(3, 16, 64, 64, kernel_size=7)
x = torch.randn(8, 3, 64, 64)
y = circ_conv_layer(x)
print(f"Circular Conv2d output: {y.shape}")  # torch.Size([8, 16, 64, 64])

# Learnable image filtering with circular convolution
model = nn.Sequential(
    CircularConv2d(3, 32, 64, 64, kernel_size=7),
    nn.ReLU(),
    CircularConv2d(32, 32, 64, 64, kernel_size=5),
    nn.ReLU(),
    CircularConv2d(32, 3, 64, 64, kernel_size=3)
)

image_in = torch.randn(4, 3, 64, 64)
image_out = model(image_in)
print(f"Processed image shape: {image_out.shape}")  # torch.Size([4, 3, 64, 64])
```

=== COMPLETE CONTENT === This response contains all available snippets from this library. No additional content exists. Do not make further requests.