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
// QR 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)
//
// Householder QR factorization: A = QR
//
// For each column k:
// 1. Compute Householder vector v (parallel reduction for norm)
// 2. Apply H = I - 2vvᵀ to remaining columns (parallel matrix update)
// 3. Accumulate Q (optional, parallel)
//
// Reference: Golub & Van Loan, "Matrix Computations" (2013)

struct QrParams {
    m: u32,           // Rows
    n: u32,           // Columns
    k: u32,           // Current column
    _pad: u32,
}

@group(0) @binding(0) var<uniform> params: QrParams;
@group(0) @binding(1) var<storage, read_write> A: array<f64>;    // Matrix [m × n], row-major
@group(0) @binding(2) var<storage, read_write> v: array<f64>;    // Householder vector [m]
@group(0) @binding(3) var<storage, read_write> tau: array<f64>;  // Householder scalars [min(m,n)]

var<workgroup> shared_sum: array<f64, 256>;

// Step 1: Compute column norm ||A[k:m, k]||
// Parallel reduction
@compute @workgroup_size(256, 1, 1)
fn column_norm(@builtin(local_invocation_id) local_id: vec3<u32>,
               @builtin(global_invocation_id) global_id: vec3<u32>,
               @builtin(workgroup_id) wg_id: vec3<u32>) {
    let tid = local_id.x;
    let m = params.m;
    let n = params.n;
    let k = params.k;
    
    // Sum of squares for rows k to m-1 in column k
    var sum_sq: f64 = 0.0;
    var i = k + tid;
    while (i < m) {
        let val = A[i * n + k];
        sum_sq = sum_sq + val * val;
        i = i + 256u;
    }
    
    shared_sum[tid] = sum_sq;
    workgroupBarrier();
    
    // Parallel reduction
    for (var stride = 128u; stride > 0u; stride = stride >> 1u) {
        if (tid < stride) {
            shared_sum[tid] = shared_sum[tid] + shared_sum[tid + stride];
        }
        workgroupBarrier();
    }
    
    if (tid == 0u) {
        // Store norm squared in v[0] temporarily
        v[0] = shared_sum[0];
    }
}

// Step 2: Compute Householder vector v and scalar tau
// v = (A[k:m,k] - sign(A[k,k])*||A[k:m,k]||*e₁) / ||...||
// tau = 2 / (vᵀv)
struct HouseholderParams {
    m: u32,
    n: u32,
    k: u32,
    _pad: u32,
}

@group(0) @binding(0) var<uniform> hh_params: HouseholderParams;
@group(0) @binding(1) var<storage, read> A_hh: array<f64>;
@group(0) @binding(2) var<storage, read_write> v_hh: array<f64>;
@group(0) @binding(3) var<storage, read_write> tau_hh: array<f64>;
@group(0) @binding(4) var<storage, read> norm_sq_buf: array<f64>;  // norm_sq from previous kernel

@compute @workgroup_size(256, 1, 1)
fn compute_householder(@builtin(global_invocation_id) global_id: vec3<u32>) {
    let i = global_id.x;
    let m = hh_params.m;
    let n = hh_params.n;
    let k = hh_params.k;
    
    // Only process rows k to m-1
    let row = k + i;
    if (row >= m) {
        return;
    }
    
    let norm_sq = norm_sq_buf[0];
    let norm = sqrt(norm_sq);  // native f64 sqrt
    let a_kk = A_hh[k * n + k];
    
    // sign(A[k,k]) * ||A[k:m,k]||
    var alpha: f64;
    if (a_kk >= 0.0) {
        alpha = -norm;
    } else {
        alpha = norm;
    }
    
    // v = A[k:m,k], then v[0] = v[0] - alpha
    if (row == k) {
        let v_0 = A_hh[row * n + k] - alpha;
        v_hh[i] = v_0;
        
        // Compute tau = 2 / (vᵀv)
        // vᵀv = (v[0])² + ||A[k+1:m,k]||²
        // ||A[k+1:m,k]||² = norm_sq - a_kk²
        let v_norm_sq = v_0 * v_0 + (norm_sq - a_kk * a_kk);
        if (v_norm_sq > 1e-14) {
            tau_hh[k] = 2.0 / v_norm_sq;
        } else {
            tau_hh[k] = 0.0;
        }
    } else {
        v_hh[i] = A_hh[row * n + k];
    }
}

// Step 3: Apply Householder to remaining columns
// A[k:m, j] = A[k:m, j] - tau * v * (vᵀ * A[k:m, j])  for j > k
//
// Two sub-steps:
// 3a. Compute w[j] = vᵀ * A[k:m, j] for all j > k (parallel over j)
// 3b. Update A[i,j] -= tau * v[i] * w[j] (parallel over i,j)

struct ApplyParams {
    m: u32,
    n: u32,
    k: u32,
    _pad: u32,
}

@group(0) @binding(0) var<uniform> apply_params: ApplyParams;
@group(0) @binding(1) var<storage, read> v_apply: array<f64>;
@group(0) @binding(2) var<storage, read_write> A_apply: array<f64>;
@group(0) @binding(3) var<storage, read_write> w: array<f64>;  // Work array [n]
@group(0) @binding(4) var<storage, read> tau_apply: array<f64>;

// Compute w[j] = vᵀ * A[k:m, j] for column j
// Each workgroup handles one column
@compute @workgroup_size(256, 1, 1)
fn compute_vTA(@builtin(local_invocation_id) local_id: vec3<u32>,
               @builtin(workgroup_id) wg_id: vec3<u32>) {
    let tid = local_id.x;
    let j = wg_id.x + apply_params.k + 1u;  // Column index (j > k)
    let m = apply_params.m;
    let n = apply_params.n;
    let k = apply_params.k;
    
    if (j >= n) {
        return;
    }
    
    // Dot product of v with column j
    var sum: f64 = 0.0;
    var i = tid;
    while (i < m - k) {
        let row = k + i;
        sum = sum + v_apply[i] * A_apply[row * n + j];
        i = i + 256u;
    }
    
    shared_sum[tid] = sum;
    workgroupBarrier();
    
    for (var stride = 128u; stride > 0u; stride = stride >> 1u) {
        if (tid < stride) {
            shared_sum[tid] = shared_sum[tid] + shared_sum[tid + stride];
        }
        workgroupBarrier();
    }
    
    if (tid == 0u) {
        w[j] = shared_sum[0];
    }
}

// Update A[i,j] -= tau * v[i-k] * w[j] for i >= k, j > k
@compute @workgroup_size(16, 16, 1)
fn apply_householder(@builtin(global_invocation_id) global_id: vec3<u32>) {
    let rel_i = global_id.y;  // Relative row (0 = row k)
    let rel_j = global_id.x;  // Relative column (0 = column k+1)
    
    let m = apply_params.m;
    let n = apply_params.n;
    let k = apply_params.k;
    
    let i = k + rel_i;
    let j = k + 1u + rel_j;
    
    if (i >= m || j >= n) {
        return;
    }
    
    let tau_k = tau_apply[k];
    let v_i = v_apply[rel_i];
    let w_j = w[j];
    
    A_apply[i * n + j] = A_apply[i * n + j] - tau_k * v_i * w_j;
}

// Update column k (set to R values)
// A[k,k] = -sign(A[k,k]) * ||A[k:m,k]||, A[i,k] = 0 for i > k
@compute @workgroup_size(256, 1, 1)
fn update_column_k(@builtin(global_invocation_id) global_id: vec3<u32>) {
    let i = global_id.x;
    let m = apply_params.m;
    let n = apply_params.n;
    let k = apply_params.k;
    
    let row = k + i;
    if (row >= m) {
        return;
    }
    
    if (row > k) {
        // Zero below diagonal
        A_apply[row * n + k] = 0.0;
    }
    // Note: A[k,k] is updated separately or left as computed
}

// Accumulate Q = H₁ * H₂ * ... * Hₙ
// Q starts as identity, then Q = Q * Hₖ for each k
// Hₖ = I - tau[k] * vₖ * vₖᵀ
struct QAccumParams {
    m: u32,
    k: u32,
    _pad1: u32,
    _pad2: u32,
}

@group(0) @binding(0) var<uniform> q_params: QAccumParams;
@group(0) @binding(1) var<storage, read> v_q: array<f64>;
@group(0) @binding(2) var<storage, read_write> Q: array<f64>;  // [m × m]
@group(0) @binding(3) var<storage, read> tau_q: array<f64>;
@group(0) @binding(4) var<storage, read_write> w_q: array<f64>;  // temp [m]

// Q = Q - tau * (Q * v) * vᵀ
// First compute w = Q * v (parallel), then update Q (parallel)
@compute @workgroup_size(256, 1, 1)
fn Q_times_v(@builtin(local_invocation_id) local_id: vec3<u32>,
             @builtin(workgroup_id) wg_id: vec3<u32>) {
    let tid = local_id.x;
    let i = wg_id.x;  // Row of Q
    let m = q_params.m;
    let k = q_params.k;
    
    if (i >= m) {
        return;
    }
    
    // w[i] = Σⱼ Q[i,j] * v[j-k] for j >= k
    var sum: f64 = 0.0;
    var j = k + tid;
    while (j < m) {
        sum = sum + Q[i * m + j] * v_q[j - k];
        j = j + 256u;
    }
    
    shared_sum[tid] = sum;
    workgroupBarrier();
    
    for (var stride = 128u; stride > 0u; stride = stride >> 1u) {
        if (tid < stride) {
            shared_sum[tid] = shared_sum[tid] + shared_sum[tid + stride];
        }
        workgroupBarrier();
    }
    
    // Store in w_q for this row
    if (tid == 0u) {
        w_q[i] = shared_sum[0];
    }
}

// Update Q[i,j] -= tau * w_q[i] * v[j-k] for j >= k
@compute @workgroup_size(16, 16, 1)
fn update_Q(@builtin(global_invocation_id) global_id: vec3<u32>) {
    let i = global_id.y;
    let rel_j = global_id.x;
    let m = q_params.m;
    let k = q_params.k;
    
    let j = k + rel_j;
    
    if (i >= m || j >= m) {
        return;
    }
    
    let tau_k = tau_q[k];
    let w_i = w_q[i];
    let v_j = v_q[rel_j];
    
    Q[i * m + j] = Q[i * m + j] - tau_k * w_i * v_j;
}