scirs2-fft 0.3.3

Fast Fourier Transform module for SciRS2 (scirs2-fft)
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

//! Example demonstrating optimized N-dimensional FFT
//!
//! This example shows the performance benefits of the optimized
//! N-dimensional FFT implementation with better memory access patterns.

use scirs2_core::ndarray::Array3;
use scirs2_fft::{fftn, fftn_memory_efficient, fftn_optimized};
use std::time::Instant;

#[allow(dead_code)]
fn main() {
    println!("Optimized N-dimensional FFT Example");
    println!("===================================");
    println!();

    // Test different array sizes
    let sizes = vec![(64, 64, 64), (128, 128, 32), (256, 64, 64)];

    for size in sizes {
        println!("Testing size: {size:?}");

        // Create test array
        let array = Array3::from_shape_fn(size, |(i, j, k)| {
            ((i as f64).sin() + (j as f64).cos() + (k as f64).tan()) / 3.0
        });

        // Time standard FFT
        let start = Instant::now();
        let _result_std = fftn(&array.to_owned().into_dyn(), None, None, None, None, None)
            .expect("Operation failed");
        let time_standard = start.elapsed();

        // Time optimized FFT
        let start = Instant::now();
        let _result_opt = fftn_optimized(&array.view(), None, None).expect("Operation failed");
        let time_optimized = start.elapsed();

        // Calculate speedup
        let speedup = time_standard.as_secs_f64() / time_optimized.as_secs_f64();

        println!("  Standard FFT: {time_standard:?}");
        println!("  Optimized FFT: {time_optimized:?}");
        println!("  Speedup: {speedup:.2}x");
        println!();
    }

    // Demonstrate memory-efficient FFT for large arrays
    println!("Memory-efficient FFT for large arrays:");
    println!("-------------------------------------");

    // Create a large array
    let largesize = (512, 512, 16);
    let large_array = Array3::from_shape_fn(largesize, |(i, j, k)| (i + j + k) as f64);

    let memory_gb =
        (large_array.len() * std::mem::size_of::<f64>()) as f64 / (1024.0 * 1024.0 * 1024.0);
    println!("Array size: {largesize:?}, Memory: {memory_gb:.2} GB");

    // Test memory-efficient FFT with different memory limits
    let memory_limits = vec![0.5, 1.0, 2.0];

    for limit in memory_limits {
        println!("\nMemory limit: {limit:.1} GB");

        let start = Instant::now();
        let result = fftn_memory_efficient(&large_array.view(), None, limit);
        let duration = start.elapsed();

        match result {
            Ok(_) => println!("  Success! Time: {duration:?}"),
            Err(e) => println!("  Error: {e}"),
        }
    }

    // Demonstrate axis ordering optimization
    println!("\n\nAxis ordering optimization:");
    println!("--------------------------");

    // Create array with different axis sizes
    let asymmetric = Array3::from_shape_fn((256, 32, 128), |(i, j, k)| (i * j * k) as f64);

    // Test with different axis orders
    let axis_orders = vec![vec![0, 1, 2], vec![1, 2, 0], vec![2, 0, 1]];

    for axes in axis_orders {
        println!("\nAxis order: {axes:?}");

        let start = Instant::now();
        let _result =
            fftn_optimized(&asymmetric.view(), None, Some(axes)).expect("Operation failed");
        let duration = start.elapsed();

        println!("  Time: {duration:?}");
    }

    // Demonstrate cache-friendly chunking
    println!("\n\nCache-friendly chunking:");
    println!("-----------------------");

    let chunk_test = Array3::from_shape_fn((128, 128, 128), |(i, j, k)| (i ^ j ^ k) as f64);

    // This will use optimized chunking internally
    let start = Instant::now();
    let _result = fftn_optimized(&chunk_test.view(), None, None).expect("Operation failed");
    let duration = start.elapsed();

    println!("FFT with optimized chunking: {duration:?}");

    // Show how chunk size affects performance
    println!("\nChunk size analysis:");
    let total_elements = chunk_test.len();
    println!("Total elements: {total_elements}");
    println!("Optimal chunk size: determined automatically based on cache size");

    // Verify correctness by comparing results
    println!("\n\nVerifying correctness:");
    println!("---------------------");

    let test_array = Array3::from_shape_fn((32, 32, 32), |(i, j, k)| {
        (i as f64 * 0.1) + (j as f64 * 0.01) + (k as f64 * 0.001)
    });

    let result_standard = fftn(
        &test_array.to_owned().into_dyn(),
        None,
        None,
        None,
        None,
        None,
    )
    .expect("Operation failed");
    let result_optimized =
        fftn_optimized(&test_array.view(), None, None).expect("Operation failed");

    // Compare results
    let max_diff = result_standard
        .iter()
        .zip(result_optimized.iter())
        .map(|(a, b)| (a.re - b.re).abs() + (a.im - b.im).abs())
        .fold(0.0, f64::max);

    println!("Maximum difference between standard and optimized: {max_diff:.2e}");
    println!("Results match: {}", max_diff < 1e-10);
}