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(2), using bit operations.
Efficient packed representation for matrices over all 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.
Input of matrices using the "Cambridge" compact format
Multiplication: Strassen algorithm over finite fields
Multiplication: Modular algorithm over large prime finite fields
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
Determinant
There are many algorithms to compute determinants, based on the different coefficient rings, including modular and heuristic methods. Since V2.11, an efficient elimination and minor expansion algorithm is used to compute determinants over multivariate polynomial rings with many variables.
Echelonization over fields and euclidean domains
Nullspace (many different techniques including sparse, p – adic and modular algorithms)
Determinant (modular algorithms over ℤ and ℚ)
Solution of systems of linear equations
Given a 301 by 300 matrix over ℤ with random entries between 0 and 10, Magma can compute its nullspace in 9.1 seconds on a 400Mhz Sun SPARC workstation (using the fast p-adic algorithm). (The nullity is nearly always 1, and the integer entries of the non-zero null vector usually have about 450 digits each.) This can be compared with an algorithm of J. Buchmann and D. Squirrel for computing nullspaces in the Lidia system[BuchSq] which takes 3 hours and 54 minutes for the same problem on an SPARC (speed unspecified). Even assuming conservatively that they have used a 200Mhz processor (so we halve their time), Magma is thus about 750 (sic) times faster.
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
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]. Since V2.11, a new asymptotically-fast algorithm of Allan Steel is used to construct the canonical forms over fields of characteristic zero.
Over an Euclidean domain, algorithms of Havas and others are used to compute characteristic 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 1.3 seconds (the largest elementary divisor is 50 digits) and its characteristic polynomial in 46 seconds.
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