primal-barracuda 0.4.0

barraCuda — BARrier-free Rust Abstracted Cross-platform Unified Dimensional Algebra. Vendor-agnostic GPU compute via WGSL.
Documentation
// SPDX-License-Identifier: AGPL-3.0-or-later
// Cyclic Reduction (f64) — Parallel Tridiagonal Solver for PDEs
//
// Solves tridiagonal system: a[i]*x[i-1] + b[i]*x[i] + c[i]*x[i+1] = d[i]
//
// **Deep Debt Evolution (Feb 16, 2026)**:
// - ✅ Pure WGSL f64 implementation
// - ✅ O(log n) parallel complexity (vs O(n) Thomas algorithm)
// - ✅ Hardware-agnostic (NVIDIA/AMD/Intel via WebGPU/Vulkan)
// - ✅ Science-grade precision for PDE stability
// - ✅ WGSL as unified math language
//
// Applications:
// - Crank-Nicolson PDE (heat, diffusion, Schrödinger)
// - Implicit finite difference schemes
// - Cubic spline interpolation
// - Poisson solvers
//
// Note: WGSL doesn't support `array<f64>` in workgroup memory,
// so this version uses global memory with careful synchronization.
// For small systems (n ≤ 128), the single-pass version is preferred.

struct Params {
    n: u32,           // System size
    step: u32,        // Current reduction step
    phase: u32,       // 0 = reduction, 1 = substitution
    _pad: u32,
}

@group(0) @binding(0) var<uniform> params: Params;
@group(0) @binding(1) var<storage, read_write> a: array<f64>;  // Sub-diagonal
@group(0) @binding(2) var<storage, read_write> b: array<f64>;  // Main diagonal
@group(0) @binding(3) var<storage, read_write> c: array<f64>;  // Super-diagonal
@group(0) @binding(4) var<storage, read_write> d: array<f64>;  // RHS / solution

// Helper for f64 constants
fn f64_const(x: f64, c: f32) -> f64 {
    return x - x + f64(c);
}

// Reduction step: Eliminate odd-indexed unknowns
@compute @workgroup_size(256, 1, 1)
fn reduction_f64(@builtin(global_invocation_id) global_id: vec3<u32>) {
    let stride = 1u << (params.step + 1u);  // 2^(step+1)
    let half_stride = stride >> 1u;          // 2^step
    
    let i = global_id.x * stride + half_stride;  // Odd indices at this level
    
    if (i >= params.n) {
        return;
    }
    
    let i_prev = i - half_stride;
    let i_next = i + half_stride;
    
    if (i_next >= params.n) {
        return;
    }
    
    let pivot_ref = b[i];
    let epsilon = f64_const(pivot_ref, 1e-14);
    
    // Skip if diagonal is too small
    if (abs(b[i_prev]) < epsilon || abs(b[i_next]) < epsilon) {
        return;
    }
    
    // Compute elimination factors
    let alpha = -a[i] / b[i_prev];
    let gamma = -c[i] / b[i_next];
    
    // Update coefficients for the reduced system
    b[i] = b[i] + alpha * c[i_prev] + gamma * a[i_next];
    d[i] = d[i] + alpha * d[i_prev] + gamma * d[i_next];
    
    // Update connections to farther neighbors
    a[i] = alpha * a[i_prev];
    c[i] = gamma * c[i_next];
}

// Substitution step: Back-substitute to recover solution
@compute @workgroup_size(256, 1, 1)
fn substitution_f64(@builtin(global_invocation_id) global_id: vec3<u32>) {
    let stride = 1u << (params.step + 1u);
    let half_stride = stride >> 1u;
    
    let i = global_id.x * stride + half_stride;
    
    if (i >= params.n) {
        return;
    }
    
    let i_prev = i - half_stride;
    let i_next = i + half_stride;
    
    let pivot_ref = b[i];
    let zero = f64_const(pivot_ref, 0.0);
    let epsilon = f64_const(pivot_ref, 1e-14);
    
    var x_prev = zero;
    var x_next = zero;
    
    if (i_prev < params.n) {
        x_prev = d[i_prev];
    }
    if (i_next < params.n) {
        x_next = d[i_next];
    }
    
    if (abs(b[i]) > epsilon) {
        d[i] = (d[i] - a[i] * x_prev - c[i] * x_next) / b[i];
    }
}

// =============================================================================
// SINGLE-THREAD SOLVER: For small systems, serial is faster than sync overhead
// =============================================================================

@compute @workgroup_size(1)
fn solve_serial_f64(@builtin(global_invocation_id) global_id: vec3<u32>) {
    if (global_id.x != 0u) {
        return;
    }
    
    let n = params.n;
    let pivot_ref = b[0];
    let epsilon = f64_const(pivot_ref, 1e-14);
    let zero = f64_const(pivot_ref, 0.0);
    
    // Thomas algorithm (serial, but optimal for small n)
    // Forward elimination
    for (var i = 1u; i < n; i = i + 1u) {
        if (abs(b[i - 1u]) < epsilon) {
            return;  // Singular
        }
        let m = a[i] / b[i - 1u];
        b[i] = b[i] - m * c[i - 1u];
        d[i] = d[i] - m * d[i - 1u];
    }
    
    // Back substitution
    if (abs(b[n - 1u]) < epsilon) {
        return;
    }
    d[n - 1u] = d[n - 1u] / b[n - 1u];
    
    for (var i_rev = 1u; i_rev < n; i_rev = i_rev + 1u) {
        let i = n - 1u - i_rev;
        if (abs(b[i]) < epsilon) {
            return;
        }
        d[i] = (d[i] - c[i] * d[i + 1u]) / b[i];
    }
}

// =============================================================================
// BATCHED SOLVER: Multiple independent systems
// =============================================================================

struct BatchParams {
    n: u32,           // System size per batch
    n_padded: u32,    // Padded size (power of 2)
    batch_size: u32,  // Number of systems
    step: u32,        // Current reduction step
}

@group(1) @binding(0) var<uniform> batch_params: BatchParams;

// Batched reduction step
@compute @workgroup_size(256, 1, 1)
fn reduction_batch_f64(@builtin(global_invocation_id) global_id: vec3<u32>,
                       @builtin(workgroup_id) wg_id: vec3<u32>) {
    let batch_idx = wg_id.y;
    let n_padded = batch_params.n_padded;
    let step = batch_params.step;
    
    if (batch_idx >= batch_params.batch_size) {
        return;
    }
    
    let offset = batch_idx * n_padded;
    let stride = 1u << (step + 1u);
    let half_stride = stride >> 1u;
    
    let i = global_id.x * stride + half_stride;
    
    if (i >= batch_params.n) {
        return;
    }
    
    let i_prev = i - half_stride;
    let i_next = i + half_stride;
    
    if (i_next >= batch_params.n) {
        return;
    }
    
    let idx = offset + i;
    let idx_prev = offset + i_prev;
    let idx_next = offset + i_next;
    
    let pivot_ref = b[idx];
    let epsilon = f64_const(pivot_ref, 1e-14);
    
    if (abs(b[idx_prev]) < epsilon || abs(b[idx_next]) < epsilon) {
        return;
    }
    
    let alpha = -a[idx] / b[idx_prev];
    let gamma = -c[idx] / b[idx_next];
    
    b[idx] = b[idx] + alpha * c[idx_prev] + gamma * a[idx_next];
    d[idx] = d[idx] + alpha * d[idx_prev] + gamma * d[idx_next];
    a[idx] = alpha * a[idx_prev];
    c[idx] = gamma * c[idx_next];
}

// Batched substitution step
@compute @workgroup_size(256, 1, 1)
fn substitution_batch_f64(@builtin(global_invocation_id) global_id: vec3<u32>,
                          @builtin(workgroup_id) wg_id: vec3<u32>) {
    let batch_idx = wg_id.y;
    let n_padded = batch_params.n_padded;
    let step = batch_params.step;
    
    if (batch_idx >= batch_params.batch_size) {
        return;
    }
    
    let offset = batch_idx * n_padded;
    let stride = 1u << (step + 1u);
    let half_stride = stride >> 1u;
    
    let i = global_id.x * stride + half_stride;
    
    if (i >= batch_params.n) {
        return;
    }
    
    let i_prev = i - half_stride;
    let i_next = i + half_stride;
    let idx = offset + i;
    
    let pivot_ref = b[idx];
    let zero = f64_const(pivot_ref, 0.0);
    let epsilon = f64_const(pivot_ref, 1e-14);
    
    var x_prev = zero;
    var x_next = zero;
    
    if (i_prev < batch_params.n) {
        x_prev = d[offset + i_prev];
    }
    if (i_next < batch_params.n) {
        x_next = d[offset + i_next];
    }
    
    if (abs(b[idx]) > epsilon) {
        d[idx] = (d[idx] - a[idx] * x_prev - c[idx] * x_next) / b[idx];
    }
}

// Batched serial solver (Thomas algorithm) for small systems
// One workgroup per system
@compute @workgroup_size(1)
fn solve_batch_serial_f64(@builtin(workgroup_id) wg_id: vec3<u32>) {
    let batch_idx = wg_id.x;
    
    if (batch_idx >= batch_params.batch_size) {
        return;
    }
    
    let n = batch_params.n;
    let offset = batch_idx * batch_params.n_padded;
    
    let pivot_ref = b[offset];
    let epsilon = f64_const(pivot_ref, 1e-14);
    
    // Thomas algorithm
    // Forward elimination
    for (var i = 1u; i < n; i = i + 1u) {
        let idx = offset + i;
        let idx_prev = offset + i - 1u;
        
        if (abs(b[idx_prev]) < epsilon) {
            return;
        }
        let m = a[idx] / b[idx_prev];
        b[idx] = b[idx] - m * c[idx_prev];
        d[idx] = d[idx] - m * d[idx_prev];
    }
    
    // Back substitution
    let last = offset + n - 1u;
    if (abs(b[last]) < epsilon) {
        return;
    }
    d[last] = d[last] / b[last];
    
    for (var i_rev = 1u; i_rev < n; i_rev = i_rev + 1u) {
        let i = n - 1u - i_rev;
        let idx = offset + i;
        
        if (abs(b[idx]) < epsilon) {
            return;
        }
        d[idx] = (d[idx] - c[idx] * d[offset + i + 1u]) / b[idx];
    }
}