Engineering / Mathematics — Modules, Vector Spaces and Matrices
Gaussian Elimination
Gaussian elimination over a field, its complexity, pivoting, and its role as the bottleneck in sieve algorithms.
Executive summary
Gaussian elimination reduces a matrix to echelon form by row operations, from which rank, kernel, image and solutions are all read off. It costs cubic time in the matrix dimension.
Over finite fields it is exact and needs pivoting only to avoid zero pivots. In sieve algorithms it is the phase that does not parallelise well, and specialised sparse methods replace it.
Learning objectives
- State the algorithm and its cost.
- Explain pivoting over a finite field.
- Identify why sparse methods are needed at scale.
01The algorithm
Gaussian elimination to row echelon form
matrix A over a fieldrow echelon form with recorded pivots- Set the pivot row and column to 1.
- While rows and columns remain:
- Find a row at or below the pivot row with a non-zero entry in the pivot column.
- If none exists, advance the pivot column and continue.
- Swap that row into the pivot position.
- Scale the pivot row so the pivot entry is 1.
- Subtract multiples of the pivot row from all rows below to clear the column.
- Advance both the pivot row and column.
- Return the echelon form and the pivot positions.
O(n³) field operations for an n × n matrixThe rank is the number of pivots. Free columns correspond to kernel basis vectors, and pivot columns of the original matrix form a basis for the image.
02Pivoting over a finite field
Over a finite field, pivoting is required only to avoid a zero pivot — any non-zero entry serves equally well, because arithmetic is exact and there is no numerical error to control.
| Setting | Pivot choice | Reason |
|---|---|---|
| Finite field | Any non-zero entry | Exact arithmetic; correctness only |
| Floating point | Largest magnitude | Numerical stability |
| Exact rational | Smallest entries | Limit coefficient growth |
| Sparse | Preserve sparsity | Minimise fill-in |
03The bottleneck in sieve algorithms
Index calculus and the sieve factoring methods both end with a large sparse linear system over a small field, and that phase behaves very differently from the relation collection preceding it.
- Relation collection
Embarrassingly parallelEach candidate independent; scales across many machines - Dense elimination
O(n³), poor parallelismInfeasible at sieve matrix sizes - Block Lanczos
O(n²) with sparsityIterative; the practical choice - Block Wiedemann
Similar, better distributedUses linearly generated sequence machinery
Block Wiedemann is worth noting here because it connects directly to another stream in this collection: it reduces the linear system to finding a minimal linear recurrence for a sequence of vectors, which is the Berlekamp–Massey problem.
The practical consequence is that a factoring effort is limited less by total computation than by the memory and interconnect of the single system running the linear algebra phase.
04Frequently asked questions
Is O(n³) optimal?
No. Strassen's algorithm and its successors reduce matrix multiplication below cubic, and elimination inherits the improvement. The crossovers are high and the constants poor, so cubic methods dominate in practice.
Why does sparsity matter so much?
Because sieve matrices have millions of rows with only a handful of non-zero entries each. Storing them densely is impossible, and any method causing fill-in destroys the only property making the problem tractable.
Does pivoting affect the rank?
No. Rank is invariant under row operations and swaps, so any valid pivoting sequence yields the same rank. Only the specific echelon form differs.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 324-328.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.