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
// Triangular Solve - Forward and Backward Substitution
// Solves L·x = b (forward) or Uᵀ·x = b (backward) for triangular matrices
//
// **Deep Debt Principles**:
// - ✅ Pure WGSL implementation (GPU-optimized)
// - ✅ Safe Rust (no unsafe blocks)
// - ✅ Hardware-agnostic via WebGPU
// - ✅ Runtime-configured matrix size
//
// Use Case: After Cholesky decomposition A = L·Lᵀ, solve:
// 1. L·z = b (forward substitution)
// 2. Lᵀ·x = z (backward substitution)
// Result: x is the solution to A·x = b
//
// Algorithm: Sequential substitution with dependency chain
// Forward:  x[i] = (b[i] - Σ L[i,j]*x[j] for j<i) / L[i,i]
// Backward: x[i] = (b[i] - Σ U[i,j]*x[j] for j>i) / U[i,i]

struct Params {
    n: u32,         // Matrix size (n x n)
    is_lower: u32,  // 1 for lower triangular (forward), 0 for upper (backward)
}

@group(0) @binding(0) var<storage, read> matrix: array<f32>;   // Triangular matrix (L or U)
@group(0) @binding(1) var<storage, read> rhs: array<f32>;      // Right-hand side vector b
@group(0) @binding(2) var<storage, read_write> solution: array<f32>;  // Solution vector x
@group(0) @binding(3) var<uniform> params: Params;

@compute @workgroup_size(1)
fn main(@builtin(global_invocation_id) global_id: vec3<u32>) {
    let n = params.n;
    let epsilon = 1e-10;
    
    // Check if this is the controller thread
    if (global_id.x != 0u) {
        return;
    }
    
    if (params.is_lower == 1u) {
        // Forward substitution: L·x = b
        // Solve for x starting from top (x[0], x[1], ...)
        for (var i = 0u; i < n; i = i + 1u) {
            var sum = 0.0;
            
            // Subtract known terms: Σ L[i,j]*x[j] for j<i
            for (var j = 0u; j < i; j = j + 1u) {
                sum = sum + matrix[i * n + j] * solution[j];
            }
            
            let diag = matrix[i * n + i];
            
            // Check for zero diagonal (singular matrix)
            if (abs(diag) < epsilon) {
                solution[i] = 0.0;  // Error indicator
                return;
            }
            
            // x[i] = (b[i] - sum) / L[i,i]
            solution[i] = (rhs[i] - sum) / diag;
        }
    } else {
        // Backward substitution: Uᵀ·x = b (or U·x = b)
        // Solve for x starting from bottom (x[n-1], x[n-2], ...)
        for (var i_rev = 0u; i_rev < n; i_rev = i_rev + 1u) {
            let i = n - 1u - i_rev;
            var sum = 0.0;
            
            // Subtract known terms: Σ U[i,j]*x[j] for j>i
            for (var j = i + 1u; j < n; j = j + 1u) {
                sum = sum + matrix[i * n + j] * solution[j];
            }
            
            let diag = matrix[i * n + i];
            
            // Check for zero diagonal (singular matrix)
            if (abs(diag) < epsilon) {
                solution[i] = 0.0;  // Error indicator
                return;
            }
            
            // x[i] = (b[i] - sum) / U[i,i]
            solution[i] = (rhs[i] - sum) / diag;
        }
    }
}