Linear Algebra Algorithms
Matrix Representation and Cost Model
Dense and sparse matrix representations, the cost model for exact linear algebra, and why coefficient growth rather than operation count usually decides performance.
Engineering / MathematicsLinear Algebra Algorithms2 min readKV-MATH-0528
Exact linear algebra differs from numerical linear algebra in one decisive respect: the entries grow. Operation counts that are accurate over the reals badly understate the cost over the integers or the rationals.
Representations
| Representation | Storage | Suits |
|---|---|---|
| Dense array | O(m n) | Small matrices, most number field work |
| Sparse by rows | Proportional to non-zeros | Relation matrices from sieving |
| Structured | Implicit | Matrices with exploitable form, such as Hessenberg |
The cost model
Cost is counted as bit operations, so an operation on entries of b bits costs at least b. Since Gaussian elimination causes entries to grow, the average b during a computation can far exceed the input and output sizes.
Three responses to growth
Fraction-free elimination
Arrange the elimination so every intermediate entry is a determinant of a submatrix, bounded by Hadamard's inequality.
Modular methods
Compute modulo several primes and reconstruct via the Chinese remainder theorem. Entries never grow.
Lattice reduction
Apply LLL to keep a basis short. This is the standard fix for HNF explosion.
Where the matrices come from
- Number field arithmetic
- Small dense matrices over the integers or rationals, of size the field degree. Growth is the problem, not size.
- Polynomial factorisation
- Matrices over a finite field of size the polynomial degree — see Berlekamp. No growth; entries stay in the field.
- Relation collection
- Enormous sparse matrices over the field of two elements or over the integers. Size is the problem, not growth.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.1-2.2.1. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.