Engineering / Mathematics — Polynomial Algorithms
Solving Sparse Linear Systems
Iterative methods for large sparse systems over finite fields, and their role as the bottleneck of sieve algorithms.
Executive summary
Sieve algorithms produce linear systems with millions of rows and only a handful of non-zero entries per row. Dense elimination is impossible at that scale because fill-in destroys the sparsity.
Iterative methods using only matrix-vector products preserve sparsity, and block Wiedemann reduces the problem to finding a minimal linear recurrence.
Learning objectives
- Explain why dense elimination fails on sparse systems.
- Describe the black-box iterative approach.
- Relate block Wiedemann to linearly generated sequences.
01Why elimination fails
| Property | Sieve matrix | After partial elimination |
|---|---|---|
| Rows | Millions | Millions |
| Non-zeros per row | Around 10 to 100 | Growing towards the row length |
| Storage | Feasible sparse | Infeasible dense |
| Cost | — | O(n³), impossible |
A filtering stage before the linear algebra reduces the matrix substantially — merging relations, removing singleton columns, and eliminating rows with a single non-zero — but it cannot avoid the fundamental problem for the remaining core.
02Black-box iterative methods
The remedy is to use the matrix only through matrix-vector products, never modifying it. Sparsity is then preserved because the matrix is never written to.
Wiedemann
Generates a scalar sequence from matrix-power projections, finds its minimal polynomial by Berlekamp-Massey, and uses it to construct a kernel vector.
Lanczos
Builds an orthogonal-style basis by iteration; effective over finite fields with care about self-orthogonal vectors.
Block variants
Process several vectors at once, improving parallelism and reducing the number of iterations.
- Dense elimination
O(n³) time, O(n²) memoryInfeasible at sieve scale - Wiedemann
O(n) matrix-vector productsMemory proportional to the sparse matrix - Block Wiedemann
Same, better distributedThe method used in records
03Block Wiedemann and minimal polynomials
Choose random projection vectors
Left and right vectors u and v.
Generate the sequence
The scalars uᴼAⁿv for n = 0, 1, 2, ... obtained by repeated sparse matrix-vector products.
Find the minimal polynomial
Run Berlekamp-Massey on the sequence; it divides the minimal polynomial of A.
Construct a kernel vector
Use the recovered polynomial to build an element of the kernel.
This is where the linearly generated sequence machinery earns its place in a number theory collection. The sparse system at the heart of factoring is solved by finding a minimal linear recurrence, so Berlekamp–Massey is a factoring subroutine.
04Frequently asked questions
Why not reorder rows to reduce fill-in?
Reordering helps and is used in the filtering stage, but the optimal ordering problem is NP-hard and heuristics only postpone the growth. For matrices of sieve size no ordering makes dense elimination viable.
How many iterations does Wiedemann need?
About 2n matrix-vector products for an n by n matrix, since that many sequence terms determine the minimal polynomial. Each product costs time proportional to the number of non-zeros.
Is the method randomised?
Yes — the projection vectors are random, and a bad choice gives a polynomial of smaller degree than needed. Failure is detected when the resulting vector is not in the kernel, and retrying with fresh vectors is cheap.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 435-438.
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.