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