# gizlang:linalg dense linear algebra over row-major buffers: f32 vector products and distances (BLAS level 1), and in f64 products, Cholesky, the symmetric eigendecomposition (cyclic Jacobi), least squares and the principal components. A matrix is a Vec with its dimensions beside it. ```gizlang import * as Linalg from "gizlang:linalg"; ``` ## Types ### `Eigen` ```gizlang type Eigen = { values: Vec; vectors: Vec; } ``` The eigenvalues in descending order, and the unit eigenvector of each as a row of `vectors` (n × n). - `values`: `Vec` - `vectors`: `Vec` ### `Components` ```gizlang type Components = { mean: Vec; components: Vec; variance: Vec; total: f64; } ``` Principal components of an n × d matrix: the eigenvectors of the covariance, with the sign that makes the largest entry of each component positive (scikit-learn's svd_flip on Vᵀ), and the variance along each. - `mean`: `Vec` - `components`: `Vec` - `variance`: `Vec` - `total`: `f64` ## Functions ### `zeros` ```gizlang function zeros(n: i64): Vec ``` A vector of N zeros. Effects: fail. ### `gram` ```gizlang function gram(x: Vec, n: i64, d: i64): Vec ``` xᵀx of an n × d matrix: d × d. Effects: fail. ### `crossProduct` ```gizlang function crossProduct(x: Vec, n: i64, d: i64, y: Vec, t: i64): Vec ``` xᵀy of an n × d matrix and an n × t matrix: d × t. Effects: fail. ### `multiply` ```gizlang function multiply(a: Vec, n: i64, m: i64, b: Vec, p: i64): Vec ``` a (n × m) times b (m × p). Effects: fail. ### `cholesky` ```gizlang function cholesky(a: Vec, n: i64): Option> ``` The lower Cholesky factor L of a symmetric positive definite n × n matrix (a = L Lᵀ), or none. Effects: fail. ### `choleskySolve` ```gizlang function choleskySolve(l: Vec, n: i64, b: Vec, t: i64): Vec ``` The solution of L Lᵀ x = b for each of the t columns of b (n × t). Effects: fail. ### `symmetricEigen` ```gizlang function symmetricEigen(a0: Vec, n: i64): Eigen ``` The eigendecomposition of a symmetric n × n matrix by cyclic Jacobi rotations, to machine precision. Effects: fail. ### `solveSymmetric` ```gizlang function solveSymmetric(a: Vec, n: i64, b: Vec, t: i64): Vec ``` The minimum-norm solution of a x = b for a symmetric positive semidefinite a (n × n) and b (n × t): Cholesky, else the pseudo-inverse with eigenvalues below rcond × the largest dropped, as LAPACK's lstsq drops singular values. Effects: fail. ### `pseudoSolve` ```gizlang function pseudoSolve(a: Vec, n: i64, b: Vec, t: i64, rcond: f64): Vec ``` The least-squares solution X of A X = B, for the symmetric N × N matrix A and the N × T matrix B, through the pseudo-inverse: eigenvalues below RCOND times the largest count as zero. Effects: fail. ### `columnMeans` ```gizlang function columnMeans(x: Vec, n: i64, d: i64): Vec ``` The mean of each column of an n × d matrix. Effects: fail. ### `centered` ```gizlang function centered(x: Vec, n: i64, d: i64, means: Vec): Vec ``` x with each column's mean subtracted. Effects: fail. ### `principalComponents` ```gizlang function principalComponents(x: Vec, n: i64, d: i64): Components ``` The principal components of the N × D matrix X (rows are samples): the column means, the directions and their variances, largest first. Effects: fail. ### `dot32` ```gizlang function dot32(x: Vec, xi: i64, y: Vec, yi: i64, n: i64): f64 ``` The inner product of x[xi..xi+n] and y[yi..yi+n]. Effects: fail. ### `squaredL2` ```gizlang function squaredL2(x: Vec, xi: i64, y: Vec, yi: i64, n: i64): f64 ``` The squared Euclidean distance between x[xi..xi+n] and y[yi..yi+n], summed in f32 as pgvector and FAISS sum it: chunks of 32 into two sixteen-lane sums, so two chains of fused adds overlap. squaredL2Rows sums in the same order, so both give the same bits. Effects: fail. ### `squaredL2Rows` ```gizlang function squaredL2Rows(x: Vec, rows: Vec, count: i64, n: i64, q: Vec, out: mut Vec): void ``` squaredL2 of q[0..n] to rows[0..count] of x (n values a row), into out: two rows at a time share the loads of q (the faiss fvec_L2sqr_ny shape), and the rows four ahead are fetched to the cache while these are summed. The nearest-neighbour walks spend most of their time here. Effects: fail. ### `dotCodes` ```gizlang function dotCodes(codes: bytes, rows: Vec, count: i64, stride: i64, n: i64, a: Vec, out: mut Vec): void ``` For one-byte codes, sum(a[i] × code[i]) of a[0..n] with the n codes of rows[0..count] (row r from r × stride), into out: with a[i] = q[i] × step[i], the dot product of q with the decoded rows less sum(q[i] × lo[i]). A row is a quarter of its floats' bytes, so a walk that reads rows at random waits less on memory; the rows four ahead are fetched meanwhile. Effects: fail. ### `hadamard` ```gizlang function hadamard(x: mut Vec, at: i64, n: i64): void ``` The Walsh-Hadamard transform of x[at..at+n] in place (n a power of two), unscaled: n log n adds and subtracts (the butterflies of the fast transform). Sign flips and this transform make a rotation that spreads a vector's energy over every dimension, in n log n, not the n² of a dense rotation (RaBitQ codes, db/vector.giz). Effects: fail. ### `dotNibbles` ```gizlang function dotNibbles(codes: bytes, rows: Vec, count: i64, stride: i64, n: i64, a: Vec, out: mut Vec): void ``` For two four-bit codes a byte, sum(a[i] × low[i] + a[n + i] × high[i]) of byte i's low and high halves, with the n code bytes of rows[0..count] (row r from r × stride), into out: the dot product of a query with 4-bit RaBitQ codes, its even dimensions in a[0..n] and odd ones in a[n..2n] (db/vector.giz). The rows four ahead are fetched meanwhile. Effects: fail.