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
// SVD (Singular Value Decomposition) - Shader-First Implementation
//
// Computes A = U Σ Vᵀ where:
//   - U is m×m orthogonal (left singular vectors)
//   - Σ is m×n diagonal (singular values)
//   - Vᵀ is n×n orthogonal (right singular vectors)
//
// Algorithm: One-sided Jacobi SVD
// 1. Compute B = AᵀA (parallel matmul)
// 2. Jacobi eigendecomp of B gives V and σ² (uses eigh.wgsl pattern)
// 3. U = A V Σ⁻¹ (parallel matmul)
//
// Sequential part (CPU):
//   - Jacobi sweep ordering (convergence loop)
//   - Rotation pair selection
//
// Parallel part (GPU):
//   - AᵀA computation (O(mn²) parallel)
//   - Jacobi rotation application (O(n²) per rotation, parallel)
//   - U computation (O(mn) parallel)
//
// This is SHADER-FIRST SVD:
// - Jacobi method is numerically stable
// - Each rotation is a parallel 2×2 transform across all rows
// - Foundation for low-rank approximation, pseudoinverse
//
// Reference: Demmel & Veselic (1992), "Jacobi's Method is More Accurate than QR"

struct SvdParams {
    m: u32,           // Rows of A
    n: u32,           // Columns of A
    _pad1: u32,
    _pad2: u32,
}

@group(0) @binding(0) var<uniform> params: SvdParams;
@group(0) @binding(1) var<storage, read> A: array<f32>;         // Input [m × n]
@group(0) @binding(2) var<storage, read_write> B: array<f32>;   // AᵀA [n × n]
@group(0) @binding(3) var<storage, read_write> V: array<f32>;   // Right singular vectors [n × n]
@group(0) @binding(4) var<storage, read_write> sigma: array<f32>; // Singular values [n]

// Compute B = AᵀA - parallel over (i,j)
@compute @workgroup_size(16, 16, 1)
fn compute_AtA(@builtin(global_invocation_id) global_id: vec3<u32>) {
    let i = global_id.y;  // Row of B
    let j = global_id.x;  // Column of B
    let m = params.m;
    let n = params.n;
    
    if (i >= n || j >= n) {
        return;
    }
    
    // B[i,j] = Σₖ A[k,i] * A[k,j]
    var sum: f32 = 0.0;
    for (var k = 0u; k < m; k = k + 1u) {
        sum = sum + A[k * n + i] * A[k * n + j];
    }
    
    B[i * n + j] = sum;
}

// Initialize V = I
@compute @workgroup_size(16, 16, 1)
fn init_V(@builtin(global_invocation_id) global_id: vec3<u32>) {
    let i = global_id.y;
    let j = global_id.x;
    let n = params.n;
    
    if (i >= n || j >= n) {
        return;
    }
    
    if (i == j) {
        V[i * n + j] = 1.0;
    } else {
        V[i * n + j] = 0.0;
    }
}

// Jacobi rotation parameters for a 2×2 symmetric matrix
// Given [[a, b], [b, c]], compute cos(θ) and sin(θ) for diagonalization
struct JacobiRotation {
    p: u32,           // First index
    q: u32,           // Second index (q > p)
    c: f32,           // cos(θ)
    s: f32,           // sin(θ)
}

// Apply Jacobi rotation to B (symmetric): B = JᵀBJ
// Only affects rows/columns p and q
struct RotationParams {
    n: u32,
    p: u32,
    q: u32,
    c: f32,           // cos(θ)
}

@group(0) @binding(0) var<uniform> rot_params: RotationParams;
@group(0) @binding(1) var<storage, read_write> B_rot: array<f32>;
@group(0) @binding(2) var<storage, read> s_val: array<f32>;  // sin(θ) passed separately

// Update row p and q of B
@compute @workgroup_size(256, 1, 1)
fn jacobi_rotate_B(@builtin(global_invocation_id) global_id: vec3<u32>) {
    let j = global_id.x;
    let n = rot_params.n;
    let p = rot_params.p;
    let q = rot_params.q;
    let c = rot_params.c;
    let s = s_val[0];
    
    if (j >= n || j == p || j == q) {
        return;
    }
    
    // B'[p,j] = c*B[p,j] + s*B[q,j]
    // B'[q,j] = -s*B[p,j] + c*B[q,j]
    let B_pj = B_rot[p * n + j];
    let B_qj = B_rot[q * n + j];
    
    B_rot[p * n + j] = c * B_pj + s * B_qj;
    B_rot[q * n + j] = -s * B_pj + c * B_qj;
    
    // Symmetric: also update columns
    B_rot[j * n + p] = B_rot[p * n + j];
    B_rot[j * n + q] = B_rot[q * n + j];
}

// Update the 2×2 block B[p,q] - makes it diagonal
@compute @workgroup_size(1, 1, 1)
fn jacobi_update_block() {
    let n = rot_params.n;
    let p = rot_params.p;
    let q = rot_params.q;
    let c = rot_params.c;
    let s = s_val[0];
    
    let B_pp = B_rot[p * n + p];
    let B_pq = B_rot[p * n + q];
    let B_qq = B_rot[q * n + q];
    
    // After rotation, the (p,q) block becomes diagonal
    // B'[p,p] = c²B[p,p] + 2cs·B[p,q] + s²B[q,q]
    // B'[q,q] = s²B[p,p] - 2cs·B[p,q] + c²B[q,q]
    // B'[p,q] = 0 (by construction)
    
    B_rot[p * n + p] = c*c*B_pp + 2.0*c*s*B_pq + s*s*B_qq;
    B_rot[q * n + q] = s*s*B_pp - 2.0*c*s*B_pq + c*c*B_qq;
    B_rot[p * n + q] = 0.0;
    B_rot[q * n + p] = 0.0;
}

// Apply Jacobi rotation to V: V = V * J
// Each column of V is updated
@compute @workgroup_size(256, 1, 1)
fn jacobi_rotate_V(@builtin(global_invocation_id) global_id: vec3<u32>) {
    let i = global_id.x;  // Row index
    let n = rot_params.n;
    let p = rot_params.p;
    let q = rot_params.q;
    let c = rot_params.c;
    let s = s_val[0];
    
    if (i >= n) {
        return;
    }
    
    // V'[i,p] = c*V[i,p] + s*V[i,q]
    // V'[i,q] = -s*V[i,p] + c*V[i,q]
    let V_ip = V[i * n + p];
    let V_iq = V[i * n + q];
    
    V[i * n + p] = c * V_ip + s * V_iq;
    V[i * n + q] = -s * V_ip + c * V_iq;
}

// Extract singular values from diagonal of B
// σᵢ = √B[i,i]
@compute @workgroup_size(256, 1, 1)
fn extract_sigma(@builtin(global_invocation_id) global_id: vec3<u32>) {
    let i = global_id.x;
    let n = params.n;
    
    if (i >= n) {
        return;
    }
    
    let diag = B[i * n + i];
    if (diag >= 0.0) {
        sigma[i] = sqrt(diag);
    } else {
        sigma[i] = 0.0;  // Numerical noise
    }
}

// Compute U = A * V * Σ⁻¹
// U[:,i] = (1/σᵢ) * A * V[:,i]
struct UParams {
    m: u32,
    n: u32,
    _pad1: u32,
    _pad2: u32,
}

@group(0) @binding(0) var<uniform> u_params: UParams;
@group(0) @binding(1) var<storage, read> A_u: array<f32>;
@group(0) @binding(2) var<storage, read> V_u: array<f32>;
@group(0) @binding(3) var<storage, read> sigma_u: array<f32>;
@group(0) @binding(4) var<storage, read_write> U: array<f32>;  // [m × n]

@compute @workgroup_size(16, 16, 1)
fn compute_U(@builtin(global_invocation_id) global_id: vec3<u32>) {
    let i = global_id.y;  // Row of U
    let j = global_id.x;  // Column of U (= singular vector index)
    let m = u_params.m;
    let n = u_params.n;
    
    if (i >= m || j >= n) {
        return;
    }
    
    let sig = sigma_u[j];
    if (sig < 1e-10) {
        U[i * n + j] = 0.0;
        return;
    }
    
    // U[i,j] = (1/σⱼ) Σₖ A[i,k] * V[k,j]
    var sum: f32 = 0.0;
    for (var k = 0u; k < n; k = k + 1u) {
        sum = sum + A_u[i * n + k] * V_u[k * n + j];
    }
    
    U[i * n + j] = sum / sig;
}

// Compute off-diagonal norm (for convergence check)
// ||off(B)||_F² = Σᵢ<ⱼ B[i,j]²
struct NormParams {
    n: u32,
    _pad1: u32,
    _pad2: u32,
    _pad3: u32,
}

@group(0) @binding(0) var<uniform> norm_params: NormParams;
@group(0) @binding(1) var<storage, read> B_norm: array<f32>;
@group(0) @binding(2) var<storage, read_write> off_norm: array<f32>;

var<workgroup> shared_norm: array<f32, 256>;

@compute @workgroup_size(256, 1, 1)
fn off_diagonal_norm(@builtin(local_invocation_id) local_id: vec3<u32>,
                     @builtin(global_invocation_id) global_id: vec3<u32>) {
    let tid = local_id.x;
    let n = norm_params.n;
    
    // Each thread sums its portion of off-diagonal elements
    var sum: f32 = 0.0;
    let num_pairs = n * (n - 1u) / 2u;
    
    var pair_idx = tid;
    while (pair_idx < num_pairs) {
        // Convert linear index to (i,j) with i < j
        // pair_idx = i*n - i*(i+1)/2 + j - i - 1
        // Solve for i,j (simpler: iterate)
        var i = 0u;
        var count = 0u;
        for (var ii = 0u; ii < n - 1u; ii = ii + 1u) {
            let pairs_in_row = n - 1u - ii;
            if (count + pairs_in_row > pair_idx) {
                i = ii;
                break;
            }
            count = count + pairs_in_row;
        }
        let j = pair_idx - count + i + 1u;
        
        let val = B_norm[i * n + j];
        sum = sum + val * val;
        
        pair_idx = pair_idx + 256u;
    }
    
    shared_norm[tid] = sum;
    workgroupBarrier();
    
    for (var stride = 128u; stride > 0u; stride = stride >> 1u) {
        if (tid < stride) {
            shared_norm[tid] = shared_norm[tid] + shared_norm[tid + stride];
        }
        workgroupBarrier();
    }
    
    if (tid == 0u) {
        off_norm[0] = shared_norm[0];
    }
}

// Find maximum off-diagonal element (for classical Jacobi)
@compute @workgroup_size(256, 1, 1)
fn find_max_off_diag(@builtin(local_invocation_id) local_id: vec3<u32>,
                     @builtin(global_invocation_id) global_id: vec3<u32>) {
    let tid = local_id.x;
    let n = norm_params.n;
    
    var max_val: f32 = 0.0;
    var max_p: u32 = 0u;
    var max_q: u32 = 1u;
    
    let num_pairs = n * (n - 1u) / 2u;
    var pair_idx = tid;
    
    while (pair_idx < num_pairs) {
        // Same indexing as above
        var i = 0u;
        var count = 0u;
        for (var ii = 0u; ii < n - 1u; ii = ii + 1u) {
            let pairs_in_row = n - 1u - ii;
            if (count + pairs_in_row > pair_idx) {
                i = ii;
                break;
            }
            count = count + pairs_in_row;
        }
        let j = pair_idx - count + i + 1u;
        
        let val = abs(B_norm[i * n + j]);
        if (val > max_val) {
            max_val = val;
            max_p = i;
            max_q = j;
        }
        
        pair_idx = pair_idx + 256u;
    }
    
    // Store in shared memory for reduction
    shared_norm[tid] = max_val;
    // Would need additional shared arrays for indices - simplified here
    workgroupBarrier();
    
    // Parallel max reduction (simplified - full impl needs index tracking)
    for (var stride = 128u; stride > 0u; stride = stride >> 1u) {
        if (tid < stride) {
            if (shared_norm[tid + stride] > shared_norm[tid]) {
                shared_norm[tid] = shared_norm[tid + stride];
            }
        }
        workgroupBarrier();
    }
    
    if (tid == 0u) {
        off_norm[0] = shared_norm[0];  // Max value
    }
}