Vectors and matrices

OverviewLinear algebra over generic rings and its specialisationsHow the generic matrix module gr_mat organises multiplication, LU and fraction-free LU decomposition, solving, determinants, ranks, echelon forms, characteristic polynomials and eigenvalues over any ring, how it handles rings that are not fields and inexact rings, and how nmod_mat, fmpz_mat, mpn_mod, arb_mat, acb_mat and fq_mat specialise or reuse these algorithms.

OverviewMultiplying matrices over Z/nZThe methods FLINT uses to multiply matrices modulo a word-size integer, from classical multiplication with delayed reduction to Strassen–Winograd, SIMD kernels, floating-point gemm with Chinese remaindering and bit-packed kernels for tiny moduli, and how nmod_mat_mul chooses among them.

AlgorithmDot products modulo a word-size integerHow FLINT computes \sum a_i b_i \bmod n with a single final reduction, accumulating the exact sum in one, two or three words, or in SIMD lanes, depending on n, the length and the processor.

AlgorithmStrassen–Winograd multiplicationThe 7-multiplication scheme FLINT uses for large matrix products over \mathbb{Z}/n\mathbb{Z}, with Bodrato's operation sequence, a schedule with two temporaries, and odd dimensions handled by virtual zero padding.

AlgorithmMatrix multiplication kernels modulo nThe blocked SIMD kernels nmod_mat_mul_u32, _u52, _k52 and _fp50, which multiply matrices modulo moduli up to 2^{52} in one pass with delayed reduction, and the floating-point route of nmod_mat_mul_blas with Chinese remaindering.

AlgorithmMatrix multiplication modulo small integersHow nmod_mat_mul_u8 multiplies matrices modulo N \le 255 with entries in bytes, replacing multiplications by in-register table lookups for N \le 16, and with bit-packed Strassen–Winograd and the method of four Russians for N = 2 and N = 3.

AlgorithmFloating-point matrix multiplication (gemm)How FLINT's own sgemm and dgemm kernels block, pack and thread a matrix product around a register-tile micro-kernel, and when floating-point matrix products of integers are exact.

OverviewMultiplying matrices over the integersThe methods FLINT uses to multiply integer matrices — word-size dot products, Waksman and Strassen–Winograd on multiprecision entries, multimodular products through nmod_mat, floating-point gemm modulo small primes, and transforming each entry once with the small-prime FFT — their costs, and when fmpz_mat_mul uses which.

AlgorithmGaussian elimination and LU decompositionLU decomposition with row pivoting over \mathbb{Z}/p\mathbb{Z} in its classical, delayed-reduction and recursive forms, and how FLINT derives triangular solving, linear system solving, inverses, determinants, ranks, echelon forms and nullspaces from it; plus division-free determinants and the Howell form over \mathbb{Z}/n\mathbb{Z}.

AlgorithmFraction-free eliminationBareiss' fraction-free Gaussian elimination over integral domains, Sylvester's identity, the fraction-free LU decomposition and how FLINT uses it for determinants, ranks, linear systems and echelon forms over \mathbb{Z}, \mathbb{Z}[x] and (\mathbb{Z}/p\mathbb{Z})[x].

AlgorithmCharacteristic and minimal polynomialsBerkowitz's division-free algorithm and Danilevsky's reduction to companion form for the characteristic polynomial over \mathbb{Z}/n\mathbb{Z}, and the Krylov method with least common multiples that FLINT uses for the minimal polynomial.

AlgorithmMultimodular and p-adic linear algebra over the integersHow FLINT computes determinants, solutions of linear systems, ranks, echelon forms, characteristic and minimal polynomials and products of integer matrices by working modulo word-size primes or prime powers, with Hadamard bounds, rational reconstruction, output-sensitive termination and exact certificates for every answer.

AlgorithmLattice reduction (LLL)LLL-reduced bases and the algorithms FLINT implements for them — the original rational LLL, Storjohann's integral variant, and the floating-point L² algorithm of Nguyen and Stehlé in fmpz_lll with Gram–Schmidt data in doubles, heuristic exact dot products or multiprecision floats, certified reducedness tests, removals for van Hoeij's factoring, and the truncation strategy (ULLL) used by fmpz_lll.

AlgorithmHermite and Smith normal formsThe Hermite and Smith normal forms of integer matrices and the algorithms FLINT implements for them — classical and gcd-based elimination, Kannan–Bachem, Domich–Kannan–Trotter and other computations modulo a determinant, the Pernet–Stein algorithm, Iliopoulos' algorithm, iterated Hermite forms, and Lübeck's p-adic method for elementary divisors — with the choices made by fmpz_mat_hnf and fmpz_mat_snf.

AlgorithmMatrices of polynomialsHow FLINT multiplies matrices over \mathbb{Z}[x] and (\mathbb{Z}/n\mathbb{Z})[x] — classical products of polynomials, Kronecker substitution into one integer matrix product, evaluation and interpolation, and transforming each entry once with the small-prime FFT — and how it computes determinants, ranks, inverses and solutions by fraction-free elimination or by evaluation and interpolation.

Vectors and matrices

In this section#

Referenced from#