exact-linalg

exact-linalg computes the exact determinant, the exact rank, and an exact integer nullspace basis of an integer matrix on the GPU, loadable through kernels. Results are exact integers, not floating-point approximations, and no tolerance parameter exists anywhere. The reference baselines are FLINT fmpz_mat_det, fmpz_mat_rank, fmpz_mat_nullspace and a fraction-free Bareiss elimination compared digit for digit.

Floating-point linear algebra cannot answer these questions reliably: a determinant overflows or rounds to noise, and rank depends on a tolerance the caller has to guess. This kernel answers them exactly. A 1,728-digit determinant of a 256 x 256 integer matrix returns in 33 ms as a Python integer, rank is a theorem rather than a threshold, and every nullspace vector can be certified by multiplying it back in integer arithmetic.

The determinant of a random 24 x 24 integer matrix assembling from residues modulo 31-bit primes: the candidate churns until the prime product clears twice the Hadamard bound, then locks to the exact 77-digit value, verified digit for digit against Bareiss elimination. Below, an exact rank with no tolerance parameter, and a nullspace vector certified S @ v == 0 in integer arithmetic.

Usage

import torch
from kernels import get_kernel

el = get_kernel("phanerozoic/exact-linalg", version=1, trust_remote_code=True)

A = torch.randint(-10**6, 10**6, (256, 256), dtype=torch.int64, device="cuda")

el.det(A)         # exact determinant, a Python int
el.rank(A)        # rank over the rationals
el.nullspace(A)   # list of primitive integer vectors spanning {x : A x = 0}

version selects the release branch; trust_remote_code is required by kernels for publishers without the trusted-publisher mark. Entries must fit in int64. gmpy2 accelerates the reconstruction and is recommended.

API

A may be a torch integer tensor, a nested list, or a numpy array.

Method

One pass produces all three results. The matrix is reduced to reduced row echelon form modulo a set of 31-bit primes, one CUDA grid slice per prime, with per-prime pivot bookkeeping so a prime that loses rank proceeds independently. Primes stay below 2^31 so a product of residues fits in 62 bits and Barrett reduction needs one 64-bit high-multiply.

The determinant modulo each prime is the signed product of that prime's pivots, and a prime that loses rank has determinant zero, which is itself correct, so every prime contributes to the lift. The Hadamard bound prod_i ||row_i||_2 bounds the determinant; once the prime product exceeds twice the bound, CRT recovers the signed integer exactly.

Rank modulo a prime never exceeds rank over the rationals, and some r x r minor is nonzero and bounded by the same Hadamard bound, so it survives at least one prime in a set whose product exceeds the bound. The maximum of the per-prime ranks is therefore the exact rank.

For the nullspace, the reduced echelon form is rational, but scaling by the pivot-submatrix determinant d clears the denominators: the free columns of d * RREF are r x r minors of the input, again under the Hadamard bound. CRT lifts those and the gcd is divided out, giving a primitive integer basis. Only primes agreeing on both rank and pivot column set join the lift; the prime set grows and the reduction repeats if too few agree.

Measured

Random matrices, entries to 10^6:

Verification

Every result is checkable without trusting this kernel. A @ v == 0 certifies each nullspace vector in exact integer arithmetic, and the test suite compares determinants digit for digit against a fraction-free Bareiss elimination computed independently in Python, across sizes 1 to 32, entries to 10^12, singular and rank-deficient matrices of constructed rank, and the zero matrix.

Requirements and limits

• NVIDIA GPU with compute capability 8.0+.
• Entries must fit in int64.
• Rank-deficient inputs cost additional reduction rounds when primes disagree on the pivot set; the prime set grows until enough agree.

References

Hart et al., FLINT (Fast Library for Number Theory); fraction-free Bareiss elimination; Chinese Remainder Theorem lifting over word-size primes.

License

Apache-2.0.