# 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<f64> with its dimensions beside it.

```gizlang
import * as Linalg from "gizlang:linalg";
```

## Types

### `Eigen`

```gizlang
type Eigen = { values: Vec<f64>; vectors: Vec<f64>; }
```

The eigenvalues in descending order, and the unit eigenvector of each as a row of `vectors` (n × n).

- `values`: `Vec<f64>`
- `vectors`: `Vec<f64>`

### `Components`

```gizlang
type Components = { mean: Vec<f64>; components: Vec<f64>; variance: Vec<f64>; 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<f64>`
- `components`: `Vec<f64>`
- `variance`: `Vec<f64>`
- `total`: `f64`

## Functions

### `zeros`

```gizlang
function zeros(n: i64): Vec<f64>
```

A vector of N zeros.

Effects: fail.

### `gram`

```gizlang
function gram(x: Vec<f64>, n: i64, d: i64): Vec<f64>
```

xᵀx of an n × d matrix: d × d.

Effects: fail.

### `crossProduct`

```gizlang
function crossProduct(x: Vec<f64>, n: i64, d: i64, y: Vec<f64>, t: i64): Vec<f64>
```

xᵀy of an n × d matrix and an n × t matrix: d × t.

Effects: fail.

### `multiply`

```gizlang
function multiply(a: Vec<f64>, n: i64, m: i64, b: Vec<f64>, p: i64): Vec<f64>
```

a (n × m) times b (m × p).

Effects: fail.

### `cholesky`

```gizlang
function cholesky(a: Vec<f64>, n: i64): Option<Vec<f64>>
```

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<f64>, n: i64, b: Vec<f64>, t: i64): Vec<f64>
```

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<f64>, 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<f64>, n: i64, b: Vec<f64>, t: i64): Vec<f64>
```

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<f64>, n: i64, b: Vec<f64>, t: i64, rcond: f64): Vec<f64>
```

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<f64>, n: i64, d: i64): Vec<f64>
```

The mean of each column of an n × d matrix.

Effects: fail.

### `centered`

```gizlang
function centered(x: Vec<f64>, n: i64, d: i64, means: Vec<f64>): Vec<f64>
```

x with each column's mean subtracted.

Effects: fail.

### `principalComponents`

```gizlang
function principalComponents(x: Vec<f64>, 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<f32>, xi: i64, y: Vec<f32>, 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<f32>, xi: i64, y: Vec<f32>, 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<f32>, rows: Vec<i64>, count: i64, n: i64, q: Vec<f32>, out: mut Vec<f64>): 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<i64>, count: i64, stride: i64, n: i64, a: Vec<f32>, out: mut Vec<f64>): 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<f32>, 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<i64>, count: i64, stride: i64, n: i64, a: Vec<f32>, out: mut Vec<f64>): 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.

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<f64> with its dimensions beside it.

gizlang

import * as Linalg from "gizlang:linalg";

Types

`Eigen`

gizlang

type Eigen = { values: Vec<f64>; vectors: Vec<f64>; }

The eigenvalues in descending order, and the unit eigenvector of each as a row of vectors (n × n).

values: Vec<f64>
vectors: Vec<f64>

`Components`

gizlang

type Components = { mean: Vec<f64>; components: Vec<f64>; variance: Vec<f64>; 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<f64>
components: Vec<f64>
variance: Vec<f64>
total: f64

Functions

`zeros`

gizlang

function zeros(n: i64): Vec<f64>

A vector of N zeros.

Effects: fail.

`gram`

gizlang

function gram(x: Vec<f64>, n: i64, d: i64): Vec<f64>

xᵀx of an n × d matrix: d × d.

Effects: fail.

`crossProduct`

gizlang

function crossProduct(x: Vec<f64>, n: i64, d: i64, y: Vec<f64>, t: i64): Vec<f64>

xᵀy of an n × d matrix and an n × t matrix: d × t.

Effects: fail.

`multiply`

gizlang

function multiply(a: Vec<f64>, n: i64, m: i64, b: Vec<f64>, p: i64): Vec<f64>

a (n × m) times b (m × p).

Effects: fail.

`cholesky`

gizlang

function cholesky(a: Vec<f64>, n: i64): Option<Vec<f64>>

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<f64>, n: i64, b: Vec<f64>, t: i64): Vec<f64>

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<f64>, 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<f64>, n: i64, b: Vec<f64>, t: i64): Vec<f64>

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<f64>, n: i64, b: Vec<f64>, t: i64, rcond: f64): Vec<f64>

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<f64>, n: i64, d: i64): Vec<f64>

The mean of each column of an n × d matrix.

Effects: fail.

`centered`

gizlang

function centered(x: Vec<f64>, n: i64, d: i64, means: Vec<f64>): Vec<f64>

x with each column's mean subtracted.

Effects: fail.

`principalComponents`

gizlang

function principalComponents(x: Vec<f64>, 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<f32>, xi: i64, y: Vec<f32>, 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<f32>, xi: i64, y: Vec<f32>, 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<f32>, rows: Vec<i64>, count: i64, n: i64, q: Vec<f32>, out: mut Vec<f64>): 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<i64>, count: i64, stride: i64, n: i64, a: Vec<f32>, out: mut Vec<f64>): 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<f32>, 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<i64>, count: i64, stride: i64, n: i64, a: Vec<f32>, out: mut Vec<f64>): 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.