Matrix operations
Vector spaces
Free modules
Modules over Dedekind domains
In this section we list the basic facilities available for computing with matrices over various rings. These algorithms underpin the vector space and module theory machinery.
Optimal packed representation for matrices over GF(q), using specialized bit operations, for q = 2,4,8,16.
Special packed representation for matrices over GF(q), using bit operations, for q = 3,5,7,9.
Efficient packed representation for matrices over all other small finite fields, using lookup tables for vector operations.
Fraction-free algorithms for matrices over ℚ, reducing computations to those over ℤ.
Internal modular representations of matrices over ℤ or ℚ, for several algorithms.
Fraction-free algorithms for matrices over rational function fields, reducing computations to those over polynomial rings.
Input of matrices using the "Cambridge" compact format
Multiplication: fast baby-step/giant-step algorithm for small characteristic finite fields
Multiplication: Strassen algorithm over finite fields
Multiplication: map to exact floating point over medium-sized prime finite fields (ATLAS package)
Multiplication: SSE 128-bit operations on Intel/AMD processors for small finite fields
Multiplication: modular algorithm for matrices over integers
Multiplication: evaluation/interpolation algorithm for matrices over K[x] and K[x]/ < f(x) >
Tensor products of matrices
Fast inverse of a rational matrix using modular methods
Fast algorithm for powering matrices over finite fields using the primary rational form
Order/projective order of matrices over finite fields (Leedham-Green algorithm)
Row and column operations
Submatrix operations
Fast trace of product of matrices
The Strassen algorithm for multiplying two n×n matrices over an arbitrary ring takes O(nlog2 7)≅O(n2.81) arithmetic operations, instead of the classical O(n3) operations. Magma uses the Strassen algorithm at whichever dimension is applicable for the relevant ring.
Echelonization over fields and euclidean domains
Nullspace (many different techniques including sparse, p – adic and modular algorithms)
Solution of systems of linear equations
Rank (for matrices over domains or Euclidean rings)
Determinant (for matrices over any commutative ring; modular algorithms over ℤ and ℚ)
Determinant (efficient elimination and minor expansion algorithm for multivariate polynomial rings with many variables)
Fundamental to Magma's fast linear algebra module is an asymptotically-fast echelon form algorithm for fields, which maps the problem to multiplication, thus taking advantage of all the fast multiplication algorithms above. Based on this, there are also asymptotically-fast algorithms for computing the nullspace, rank, or determinant of a matrix over a field.
For matrices over the integers or rationals, there are asymptotically-fast algorithms for all of the above operations, which are based on modular and p-adic methods.
Generalized Jordan canonical form of matrices over fields
Rational and primary rational canonical forms of matrices over fields
Hermite and Smith forms for matrices over Euclidean domains (fast modular algorithm over the integers)
Characteristic polynomial, minimal polynomial,
Eigenvalues and eigenspaces (modular algorithms used over ℤ and ℚ)
LLL-reduction of matrices over ℤ.
Over finite fields, a fast algorithm due to Allan Steel is used to construct the various matrix canonical forms: generalized Jordan, rational, and primary rational [AKS97]. Over the ring of integers, asymptotically-fast modular algorithms are used to compute characteristic and minimal polynomials polynomials and the Hermite and Smith normal forms.
Given a 100×100 matrix over Z with random one-digit entries Magma finds its Smith form in 0.06 seconds (the largest elementary divisor is 50 digits) and its characteristic polynomial in 0.1 seconds (on an 2.4GHz Opteron processor).
A special type for sparse matrices is provided so that the user can build up such matrices and then apply some non-trivial algorithms to them. An extended example in the Handbook implements the basic linear sieve for discrete logarithms in the Magma language, thus demonstrating how one can use the sparse matrix facilities when implementing index-calculus methods.
Features:
Creation of sparse matrices in compact form.
Creation of trivial sparse matrices followed by dynamic expansion.
Basic properties (density, etc.).
Conversion between sparse and normal (dense-representation) matrices.
Multiplication of dense vectors by sparse matrices.
Non-trivial invariants of sparse matrices: nullspace, rank and elementary divisors (equivalent to Smith form).
Computation of non-zero solution vector for sparse systems arising in index-calculus algorithms (Structured Gaussian elimination and Lanczos algorithms [LaOd91]).
Computation of general nullspace over fields and Euclidean rings using Markowitz-pivoting techniques.
Construction of vector spaces of n-tuples over a field
Construction of vector spaces comprising m×n matrices over a field
Extension and restriction of the field of scalars
Direct sum
Vector arithmetic
Normalization, rotation
Tensor product of vectors
Trace of a vector in a subfield
Weight, support
Construction of a subspace
Membership of a subspace
Transversal of a subspace (over a finite field)
Complement of a subspace
Sum and intersection of subspaces
Reduction of vectors over a subspace
Quotient spaces
Construction of a vector space with specified basis
Coordinates of a vector with respect to a basis
Test for linear independence of a set of vectors
Extend a linearly independent set to a basis
In this section we are mainly concerned with free modules. We consider R-modules M of n-tuples where R has scalar action on M. The case in which the action of R on M is via a matrix algebra is considered in the section on Representation Theory.
Construction of free modules of n-tuples
Construction of modules comprising m×n matrices
Arithmetic
Extension and restriction of the ring of scalars
Direct sum
Construction of submodules, quotient modules
Sum and intersection of submodules
Basis operations
Construction of modules Hom(M,N) for any free modules M and N
Explicit construction of Hom(U,V) for proper subspaces U and V
Explicit construction of Hom(H1, H2) for homomorphism modules H1 and H2 with left or right matrix action
Construction of the reduced module of a homomorphism module whose elements are with respect to the bases of the domain and codomain (not just the generic bases of these)
Image, kernel, cokernel
Echelon form (over a field)
Hermite and Smith normal forms (over an ED)
Modules over dedekind domains are supported only for maximal orders of Algebraic number fields and Algebraic function fields.
Creation of modules
Arithmetic with module elements
Submodules and quotients of modules
Determinant, dimension, pseudo-generators
Equality of modules, membership
Intersection of submodules
Product of a module by an ideal
Pseudo-basis and elementary divisors
Dual of a module
Steinitz class and Steinitz form
Construction of modules Hom(M,N) and standard calculations with morphisms
Complexes of modules are a fundamental object in homological algebra. Conceptually, a complex is an infinite sequence of modules, indexed by integers, with maps between successive modules such that the composition of any two maps is zero.
Creation of a complex from a list of A-modules
Subcomplexes and quotient complexes
Operations on complexes: Splice, shift, direct sum
Exact extensions, zero extensions
Dual of a complex
Homology groups of a complex
Boundary maps
Construction of chain maps between complexes
Composition of chain maps
Image, kernel and cokernel of a chain map
Predicates for chain maps: Surjection, injection, isomorphism
Injective resolution (for modules over a basic algebra)
Projective resolution (for modules over a basic algebra)
Extending cohomology elements as chain maps
Maps induced on homology by chain maps, long exact homology sequence