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) f64 - Shader-First Implementation
//
// Full f64 precision via WGSL native f64 support (SPIR-V/Vulkan)
// FP64 performance: 1:2-3 (not 1:32 like CUDA consumer cards)
//
// 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)
//
// 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<f64>;         // Input [m × n]
@group(0) @binding(2) var<storage, read_write> B: array<f64>;   // AᵀA [n × n]
@group(0) @binding(3) var<storage, read_write> V: array<f64>;   // Right singular vectors [n × n]
@group(0) @binding(4) var<storage, read_write> sigma: array<f64>; // 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: f64 = 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;
    }
}

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

@group(0) @binding(0) var<uniform> rot_params: RotationParams;
@group(0) @binding(1) var<storage, read_write> B_rot: array<f64>;
@group(0) @binding(2) var<storage, read> cs: array<f64>;  // [cos(θ), sin(θ)]

// 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 = cs[0];
    let s = cs[1];
    
    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 = cs[0];
    let s = cs[1];
    
    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_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 = cs[0];
    let s = cs[1];
    
    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);  // native f64 sqrt
    } 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<f64>;
@group(0) @binding(2) var<storage, read> V_u: array<f64>;
@group(0) @binding(3) var<storage, read> sigma_u: array<f64>;
@group(0) @binding(4) var<storage, read_write> U: array<f64>;  // [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-14) {
        U[i * n + j] = 0.0;
        return;
    }
    
    // U[i,j] = (1/σⱼ) Σₖ A[i,k] * V[k,j]
    var sum: f64 = 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<f64>;
@group(0) @binding(2) var<storage, read_write> off_norm: array<f64>;

var<workgroup> shared_norm: array<f64, 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;
    
    var sum: f64 = 0.0;
    let num_pairs = n * (n - 1u) / 2u;
    
    var pair_idx = tid;
    while (pair_idx < num_pairs) {
        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];
    }
}

// Compute Jacobi rotation parameters for 2×2 block
// Given B[p,p], B[p,q], B[q,q], compute c=cos(θ), s=sin(θ)
// such that the rotation diagonalizes the 2×2 block
struct JacobiParams {
    n: u32,
    p: u32,
    q: u32,
    _pad: u32,
}

@group(0) @binding(0) var<uniform> jac_params: JacobiParams;
@group(0) @binding(1) var<storage, read> B_jac: array<f64>;
@group(0) @binding(2) var<storage, read_write> cs_out: array<f64>;  // [c, s]

@compute @workgroup_size(1, 1, 1)
fn compute_jacobi_rotation() {
    let n = jac_params.n;
    let p = jac_params.p;
    let q = jac_params.q;
    
    let B_pp = B_jac[p * n + p];
    let B_pq = B_jac[p * n + q];
    let B_qq = B_jac[q * n + q];
    
    // If already diagonal (or nearly so), use identity rotation
    if (abs(B_pq) < 1e-14) {
        cs_out[0] = 1.0;  // c
        cs_out[1] = 0.0;  // s
        return;
    }
    
    // Compute rotation angle
    // tan(2θ) = 2*B[p,q] / (B[p,p] - B[q,q])
    let diff = B_pp - B_qq;
    var tau: f64;
    
    if (abs(diff) < 1e-14) {
        // B[p,p] ≈ B[q,q], use θ = π/4
        if (B_pq > 0.0) {
            tau = 1.0;
        } else {
            tau = -1.0;
        }
    } else {
        let phi = 2.0 * B_pq / diff;
        // tau = tan(θ) = sign(phi) / (|phi| + sqrt(1 + phi²))
        let sign_phi = select(-1.0, 1.0, phi >= 0.0);
        tau = sign_phi / (abs(phi) + sqrt(1.0 + phi * phi));
    }
    
    // c = 1 / sqrt(1 + tau²)
    // s = tau * c
    let c = 1.0 / sqrt(1.0 + tau * tau);
    let s = tau * c;
    
    cs_out[0] = c;
    cs_out[1] = s;
}