// SPDX-License-Identifier: AGPL-3.0-or-later
// Cholesky Decomposition - L·Lᵀ factorization of symmetric positive-definite matrices
// Computes lower triangular matrix L such that A = L·Lᵀ
//
// **Deep Debt Principles**:
// - ✅ Pure WGSL implementation (GPU-optimized)
// - ✅ Safe Rust (no unsafe blocks)
// - ✅ Hardware-agnostic via WebGPU
// - ✅ Runtime-configured matrix size
// - ✅ Capability-based dispatch
//
// Algorithm: Standard Cholesky (column-by-column)
// 1. For each column j:
// a. Compute diagonal: L[j,j] = sqrt(A[j,j] - Σ L[j,k]² for k<j)
// b. For each row i > j:
// L[i,j] = (A[i,j] - Σ L[i,k]*L[j,k] for k<j) / L[j,j]
//
// Sequential dependency in column j, parallel within column
// Optimized for N ≤ 30,000 (hotSpring surrogate use case)
struct Params {
n: u32, // Matrix size (n x n)
}
@group(0) @binding(0) var<storage, read> input: array<f32>; // Input symmetric positive-definite matrix
@group(0) @binding(1) var<storage, read_write> output: array<f32>; // Output lower triangular L
@group(0) @binding(2) var<uniform> params: Params;
@compute @workgroup_size(256)
fn main(@builtin(global_invocation_id) global_id: vec3<u32>) {
let n = params.n;
let epsilon = 1e-8;
// Check if this is the controller thread
if (global_id.x != 0u) {
return;
}
// Initialize output to zero
for (var i = 0u; i < n * n; i = i + 1u) {
output[i] = 0.0;
}
// Cholesky decomposition: column-by-column
for (var j = 0u; j < n; j = j + 1u) {
// Compute L[j,j] = sqrt(A[j,j] - Σ L[j,k]² for k<j)
var sum_sq = 0.0;
for (var k = 0u; k < j; k = k + 1u) {
let l_jk = output[j * n + k];
sum_sq = sum_sq + l_jk * l_jk;
}
let diag_val = input[j * n + j] - sum_sq;
// Check for positive definiteness
if (diag_val <= epsilon) {
// Matrix is not positive definite
// Return zero matrix as error indicator
return;
}
output[j * n + j] = sqrt(diag_val);
let l_jj = output[j * n + j];
// Compute L[i,j] for i > j (below diagonal)
for (var i = j + 1u; i < n; i = i + 1u) {
var sum_prod = 0.0;
for (var k = 0u; k < j; k = k + 1u) {
sum_prod = sum_prod + output[i * n + k] * output[j * n + k];
}
output[i * n + j] = (input[i * n + j] - sum_prod) / l_jj;
}
}
}