leto-ops 0.45.2

Math, reduction, SIMD, and parallel kernels for Leto arrays
Documentation
//! Column-major working-buffer Golub–Kahan bidiagonal reduction, values-only
//! (`m ≥ n`). Local to the SVD values path — leto's global array layout stays
//! row-major; this transposes the input once into a column-major scratch so the
//! **left (column) reflector** lives in contiguous memory, mirroring leto's
//! column-major locality without regressing any other operation.
//!
//! # Theorem (singular values preserved)
//! Storing `Aᵀ`'s columns contiguously and applying the identical left/right
//! Householder reflectors yields the same bidiagonal `B` (hence the same singular
//! values) as the row-major reduction — only the memory layout of the working
//! buffer differs; the arithmetic and reflector sequence are identical. ∎
//!
//! Both applies are contiguous in this layout. The **left** reflector treats the
//! trailing column block as a row-major sub-matrix (rows = columns, length
//! `vlen`, row stride `m`) and applies it in two batched, register-blocked SIMD
//! calls — `gemv_strided` for the dots `dotⱼ = vᵀ·colⱼ` (TILE_M accumulators in
//! flight, ILP) and `axpy_rows` for the rank-1 update `colⱼ −= (τ·dotⱼ)·v` —
//! rather than `O(n)` per-column `dot`/`axpy` calls. The **right** reflector forms
//! `Aw = Σⱼ wⱼ·colⱼ` (`gemv_transpose_strided`) and updates `colⱼ -= τ·wⱼ·Aw`
//! (`axpy_rows`) over the trailing segment block, likewise batched. Only the
//! small `O(m)`/`O(n)` reflector gathers touch strided memory.

use crate::application::linalg::scaling::KernelWindow;
use crate::application::linalg::thresholds;
use crate::domain::real::RealScalar;
use leto::ArrayView2;

/// In-place Householder (`dlarfg`): `x[0] ← β`, `x[1..] ← v` (implicit `v[0]=1`);
/// returns `(τ, β)`.
///
/// Scale-safe: `α² + ‖x[1..]‖² ≤ len·m²` (`m = max|xᵢ|`, degree 2, bound
/// `2^⌈log₂ len⌉`) is formed unscaled while `m` keeps it normal and finite
/// (`window`, built by [`reduce_values`] for the longest reflector `len ≤ m`),
/// and otherwise from `x` divided by the
/// power of two bringing `m` into `[1, 2)` — LAPACK `dlarfg` forms the same
/// norm through `dnrm2`/`dlapy2`, whose accumulation is likewise scaled. `τ`
/// and `v = x/(α − β)` are scale-invariant and `β` is multiplied back, all
/// exactly, so inside the window the result is bit-for-bit the unscaled one.
fn larfg<T: RealScalar>(x: &mut [T], window: KernelWindow<T>) -> (T, T) {
    let n = x.len();
    if n == 0 {
        return (T::ZERO, T::ZERO);
    }
    if n == 1 {
        return (T::ZERO, x[0]);
    }
    let exponent = window.exponent(x);
    let alpha = x[0].scale_binary(-exponent);
    let mut xnorm_sq = T::ZERO;
    for &xi in &x[1..] {
        let xi = xi.scale_binary(-exponent);
        xnorm_sq = xnorm_sq.add(xi.mul(xi));
    }
    if xnorm_sq == T::ZERO {
        return (T::ZERO, x[0]);
    }
    let beta = {
        let b = alpha.mul(alpha).add(xnorm_sq).sqrt();
        if alpha <= T::ZERO {
            b
        } else {
            T::ZERO.sub(b)
        }
    };
    let tau = beta.sub(alpha).div(beta);
    let scal = T::ONE.div(alpha.sub(beta));
    for xi in &mut x[1..] {
        *xi = xi.scale_binary(-exponent).mul(scal);
    }
    let beta = beta.scale_binary(exponent);
    x[0] = beta;
    (tau, beta)
}

/// Reduce row-major `matrix` (`m×n`, `m ≥ n`) to the bidiagonal `(d, e)` via a
/// column-major working buffer.
pub(super) fn reduce_values<T: RealScalar>(matrix: &ArrayView2<'_, T>) -> (Vec<T>, Vec<T>) {
    let [m, n] = matrix.shape();
    // Transpose into column-major: cm[j*m + i] = A[i][j]; column j is contiguous.
    let mut cm = vec![T::ZERO; m * n];
    if let Some(a) = matrix.as_slice() {
        for i in 0..m {
            let row = &a[i * n..i * n + n];
            for (j, &val) in row.iter().enumerate() {
                cm[j * m + i] = val;
            }
        }
    } else {
        for i in 0..m {
            for j in 0..n {
                cm[j * m + i] = *matrix.get([i, j]).expect("in bounds");
            }
        }
    }

    let window = KernelWindow::new(2, 2, thresholds::ceil_log2_count(m));
    let mut d = vec![T::ZERO; n];
    let mut e = vec![T::ZERO; n];
    let mut vbuf = vec![T::ZERO; m]; // contiguous copy of the active left reflector
    let mut w = vec![T::ZERO; n]; // right reflector
    let mut aw = vec![T::ZERO; m]; // A·w column vector
    let mut dotbuf = vec![T::ZERO; n]; // batched left-reflector dots vᵀ·colⱼ

    for k in 0..n {
        // ---- Left reflector on column k, rows k..m (contiguous).
        let vlen = m - k;
        let (tau_q, beta_d) = {
            let col = &mut cm[k * m + k..k * m + m];
            larfg(col, window)
        };
        d[k] = beta_d;
        // v with implicit unit head: copy into vbuf[..vlen], vbuf[0] = 1.
        vbuf[0] = T::ONE;
        for r in 1..vlen {
            vbuf[r] = cm[k * m + k + r];
        }
        // Apply to trailing columns k+1..n: colⱼ −= (τ·vᵀcolⱼ)·v, batched as a
        // sub-matrix dot (gemv_strided) + rank-1 update (axpy_rows). Both keep
        // TILE_M independent SIMD accumulators in flight, where the prior
        // per-column loop serialized on each column's reduction/update — the
        // isolated dot batch measured ≈2× (hermes `reflector_dots` bench).
        if tau_q != T::ZERO {
            let ntrail = n - k - 1;
            if ntrail > 0 {
                // Batch the dots: dotbuf[t] = vᵀ·col_{k+1+t} over the trailing
                // column block (gemv_strided accumulates, so zero first).
                for slot in dotbuf[..ntrail].iter_mut() {
                    *slot = T::ZERO;
                }
                T::gemv_strided(
                    &cm[(k + 1) * m + k..],
                    &vbuf[..vlen],
                    &mut dotbuf[..ntrail],
                    ntrail,
                    vlen,
                    m,
                );
                // Scale in place to the per-column axpy coefficient, then batch
                // the rank-1 update via axpy_rows: colⱼ[i] += (−τ·dot[j])·v[i].
                for slot in dotbuf[..ntrail].iter_mut() {
                    *slot = T::ZERO.sub(tau_q.mul(*slot));
                }
                T::axpy_rows(
                    &dotbuf[..ntrail],
                    &vbuf[..vlen],
                    &mut cm[(k + 1) * m + k..],
                    m,
                    ntrail,
                    vlen,
                );
            }
        }

        // ---- Right reflector on row k, columns k+1..n (strided gather).
        if k + 1 < n {
            let rlen = n - k - 1;
            for (idx, j) in ((k + 1)..n).enumerate() {
                w[idx] = cm[j * m + k];
            }
            let (tau_p, beta_e) = larfg(&mut w[..rlen], window);
            e[k] = beta_e;
            w[0] = T::ONE; // implicit unit head
            if tau_p != T::ZERO {
                let rows = m - k - 1; // trailing rows k+1..m
                if rows > 0 {
                    // The trailing segment block colⱼ[k+1..m] (j=k+1..n) is a
                    // row-major sub-matrix (rows = columns = `rlen`, length `rows`,
                    // row stride m) starting at (k+1)·(m+1). Batch both applies:
                    //   Aw = Σⱼ wⱼ·segⱼ   = gemv_transpose_strided(block, w)
                    //   segⱼ −= (τ·wⱼ)·Aw  = axpy_rows(−τ·w, Aw, block)
                    // replacing O(rlen) per-column axpy calls with one
                    // register-blocked SIMD call each (ILP across columns).
                    let base = (k + 1) * m + (k + 1);
                    for v in aw[..rows].iter_mut() {
                        *v = T::ZERO; // gemv_transpose_strided accumulates
                    }
                    T::gemv_transpose_strided(
                        &cm[base..],
                        &w[..rlen],
                        &mut aw[..rows],
                        rlen,
                        rows,
                        m,
                    );
                    for (idx, slot) in dotbuf[..rlen].iter_mut().enumerate() {
                        *slot = T::ZERO.sub(tau_p.mul(w[idx]));
                    }
                    T::axpy_rows(&dotbuf[..rlen], &aw[..rows], &mut cm[base..], m, rlen, rows);
                }
            }
        }
    }

    (d, e)
}