// 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;
}