Magma V2.2 Anouncement
Date: Thu, 3 Jul 1997 13:25:20 +1000
From: magma@maths.usyd.edu.au (Magma Computer Algebra System)
To: hwloidl@risc.uni-linz.ac.at
Subject: Announcement of MAGMA V2.2
---------------
| MAGMA V2.2 |
---------------
Magma V1 was released in December 1993. Since then it has undergone
enormous expansion and many original modules have been rewritten. This
document gives a terse summary of the scope and capabilities of the current
release V2.2 (some information is included about the the October, 1997
release (V2.3)). Timing data refers to Magma running on a SUN Ultra 2
with a 200 MHz processor. The Magma home page
http://www.maths.usyd.edu.au:8000/comp/magma/Overview.html
provides a much more detailed listing of facilities together with examples.
------------
| PHILOSOPHY |
------------
Magma is a Computer Algebra system designed specifically for computation
in all branches of algebra, number theory and geometry (and for other areas
that are heavily algebraic in nature). Features of its philosophy include:
ALGEBRAIC DESIGN PHILOSOPHY: The design principles underpinning both the
user language and system architecture are based on ideas from universal
algebra and category theory. The language attempts to approximate as
closely as possible, the usual mathematical modes of thought and notation.
In particular, the principal constructs in the user language are set,
(algebraic) structure and morphism.
UNIVERSALITY: In-depth coverage of all the major branches of algebra,
number theory, algebraic geometry and finite incidence geometry.
INTEGRATION: The facilities for each area are designed in a similar manner
using generic constructors wherever possible. The uniform design makes it
a simple matter to program calculations that span different classes of
mathematical structures or which involve the interaction of structures.
PERFORMANCE: The intention is that Magma provide the best possible
performance both in terms of the algorithms used and their implementation.
The design philosophy permits the kernel implementor to choose optimal data
structures at the machine level. Most of major algorithms currently
installed in the Magma kernel are state-of-the-art and give performance
similar to, or better than, specialized programs.
------------------
| SUMMARY OF AREAS |
------------------
The mathematical structures implemented in the Magma kernel may be loosely
grouped into eight areas:
* Semigroups, monoids, automata, rewriting systems.
* Groups: Finitely-presented groups, fg abelian groups, black-box
groups, permutation groups, matrix groups, soluble groups.
* Commutative rings: Ring of integers, polynomial rings, power
series rings, orders, valuation rings, rings of group invariants.
* Fields: Finite fields, number fields, function fields, local
fields, fields of Laurent series, real and complex fields.
* Modules: Vector spaces, R-modules over fields, R-modules over EDs,
R-modules over K[x_1, ..., x_n], K[G]-modules, Hom(M, N), lattices.
* Algebras: General finite-dimensional (fd) algebras, fd associative
algebras, fd Lie algebras, matrix algebras, group algebras,
finitely-presented associative algebras.
* Algebraic geometry: Elliptic curves, curves of genus greater
than 1, algebraic varieties.
* Combinatorics: Counting theory, directed and undirected graphs,
incidence structures, designs, planes, codes.
--------------
| GROUP THEORY |
--------------
________________________________________________________________________
Finitely-presented groups Automatic groups Abelian groups
Blackbox groups Soluble groups Permutation groups
Matrix groups Representations Cohomology
________________________________________________________________________
FINITELY-PRESENTED GROUPS: A key component is the Todd-Coxeter procedure
for enumerating cosets developed by George Havas. Built on top of this is
machinery for computing properties of subgroups of finite index. The
standard quotient constructions (abelian quotient, p-quotient and soluble
quotient) are provided. Eamonn O'Brien's p-group generation package is also
included. A particularly efficient search for low index subgroups (due to
Sims) allows the user to look for large subgroups. Subgroup rewriting is
included and the new Tietze simplification program of Havas and Lian
provides fast simplification of presentations. The KBMAG program developed
by Derek Holt will provide support for automatic groups in V2.3.
SOLUBLE GROUPS: Given a (finite) soluble group defined by means of a
polycyclic presentation, a large family of algorithms designed to take
advantage of this representation is provided. These include the finding
of characteristic subgroups, the computation of structural information
specific to soluble groups (e.g., Hall subgroups, Sylow basis), and the
determination of maximal subgroups, normal subgroups, and all conjugacy
classes of subgroups. For example, the maximal subgroups of the Burnside
group B(2, 6) of order 2^28 3^25, may be found in 115 seconds. In the
particular case of p-groups, specialized techniques are often employed.
In particular, the O'Brien algorithm for computing automorphism groups
and testing isomorphism of p-groups are available. Automorphism groups
of soluble groups will be available in the near future.
PERMUTATION GROUPS: A permutation action may be defined on any finite set
using a G-set mechanism. A huge range of permutation group algorithms (some
300) are incoporated -- many of them developed specifically for Magma. The
key to structural computation in large permutation groups is the use of a
base and strong generating set (BSGS). A range of techniques is provided
for finding a BSGS, including the Brownie-Cannon-Sims verification
procedure (applicable to degrees in excess of a million). Backtrack
searches are performed using Jeff Leon's PERM package. For analyzing the
structure of large permutation groups, reduction algorithms are often
employed. In particular, tools are provided to decompose a primitive group
according to the O'Nan-Scott theorem. For example, using a reduction
algorithm, the Sylow 2-subgroup of the wreath product of AGL(7, 3) with A5
(a group of degree 10,935 and order 1.30 x 10^134) is found in 1,035
seconds. A new family of algorithms has been developed for computing
conjugacy classes of elements, normal subgroups and all subgroups; it takes
2285 seconds to compute the 15,124 classes of subgroups of 2^6 A8 (of order
1,290,240).
MATRIX GROUPS: For finite groups of moderate degree and order, where an
orbit of length less than a few million can be found, BSGS techniques are
used. Structural information such as characteristic subgroups, local
subgroups, and conjugacy classes may then be computed. For groups of large
degree over finite fields, the specialized machinery developed by Cellar,
Holt, Leedham-Green, O'Brien, Pye and others will become available in
V2.3. The Magma implementation of the Niemeyer-Praeger algorithm is
capable of recognizing classical groups having degrees up to 10,000. For
example, SL(10000, 2) is recognized in 30,500 seconds.
REPRESENTATIONS AND COHOMOLOGY: A carefully tuned Dixon-Schneider algorithm
is employed for finding character tables. Extensive support is provided for
computing with KG-modules, including algorithms for composition series,
submodule lattice (if K is a finite field), testing equivalence,
endomorphism ring and testing indecomposability. In the case where K is a
small finite field, composition series may be found for modules of
dimension up to 20,000, while (in V2.3), if K is the rational field,
composition series may be found for dimensions up to 500-600. The first
and second cohomology groups, together with all extensions of a module
by a group, may be computed in the case of a permutation group.
-------------------
| COMMUTATIVE RINGS |
-------------------
________________________________________________________________________
Ring of integers Polynomial rings Rings of invariants
Orders of fields Valuation rings Power series rings
________________________________________________________________________
INTEGERS: A new fast integer arithmetic package was released in V2.2.
Among many highlights, it employs the Karatsuba algorithm for products, an
exact divide function and the Weber accelerated GCD algorithm. Assembler
macros are used for critical operations. Integer multiplication is 25-40%
faster than GNU gmp: the multiplication of two 10,000 bit integers takes
0.005 seconds. Integer factorization is performed using versions of the ECM
and MPQS algorithms developed by Arjen Lenstra. An 80-digit integer that
is the product of two 40-digit primes may be factored in about 10 hours.
Francois Morain's ECPP program is used for proving primality, taking about
800 seconds to prove a 200-digit integer prime.
UNIVARIATE POLYNOMIALS: An extensive module for computing in polynomial
rings over commutative rings is provided, and includes very fast imple-
mentations of factorization algorithms over finite fields, integers and
p-adics. Algorithms are also provided for factorization over number
fields and function fields. Magma factors the first challenge polynomial
of Zimmermann (degree 156, 78 digit coefficients over Z) in 6 seconds.
(See http://www.loria.fr/~zimmerma/mupad).
MULTIVARIATE POLYNOMIALS: Included are algorithms for GCDs and factor-
ization over F_q, Z, Q, number fields and rational function fields
(over F_q and Q); factorization over F_q, Z and rational function
fields (over F_q and Q). A comprehensive Groebner basis (GB) package is
provided which, in addition to a very fast implementation of the standard
GB algorithm includes both a Groebner Walk and a Hilbert-driven GB
algorithm. All the standard constructions associated with ideals:
variety, radical, dimension, primary decomposition and Hilbert series
are provided. Sample timings of the Magma GB include:
- Katsura-5 problem (lex order) -- 4.5 seconds;
- Cyclic 6-th roots problem (grevlex order) -- 2.5 seconds;
- Cyclic 7-th roots problem (grevlex order) -- 1200 seconds.
All examples are from the POSSO test suite (posso@dm.unipi.it).
INVARIANT RINGS: A module for constructing both characteristic 0 and
modular invariants of finite groups has been developed by Gregor Kemper and
Allan Steel. This includes a new algorithm for computing primary invariants
that guarantees the degrees of the invariants constructed are optimal (with
respect to their product and then sum). Both primary and secondary
invariants are available and many properties of the invariant ring may be
computed. The optimal primary invariants (degrees 3, 5, 8 and 12) for the
4-dimensional representation of the alternating group A_5 over GF(2) are
found in 1.5 seconds.
--------
| FIELDS |
--------
________________________________________________________________________
Rational field Finite fields Number fields
Quadratic fields Cyclotomic fields Function fields
Real & complex fields Local fields Laurent series fields
________________________________________________________________________
FINITE FIELDS: Finite field arithmetic is optimized through use of
specialized representations for fields GF(p^n), depending upon the
characteristic p and exponent n. Of particular note, is the ability to
efficiently solve the compatibility problem for embedded subfields. In
particular, if a field extension if constructed in two different ways,
a compatible embedding in an appropriate overfield is constructed.
NUMBER FIELDS: Facilities for general number fields are provided by the
KANT package. The core consists of machinery for performing arithmetic
with arbitrary orders and their ideals. The major capabilities include
facilities to determine the maximal order (round 2 and 4 algorithms),
class group, unit group and Galois group (up to degree 12). A very fast
algorithm is available for determining subfields. Algorithms for solving
norm equations, relative norm equations, Thue equations and unit equations
are included. The extension of Q by a root of x^9 - 57*x^6 + 165*x^3 - 6859
is shown to have class group Z/3Z and unit group Z/2Z + Z + Z + Z + Z in
143 seconds. The Galois group (of order 18) is found in 1 second.
QUADRATIC FIELDS: Magma contains special code for quadratic fields,
based on code from the PARI package. In particular, a subexponential
algorithm for computing the class number is used. Binary quadratic
forms with the usual reduction and composition operations provide a
convenient means of computing in class groups.
FUNCTION FIELDS: Fields of rational functions are available in V2.2. The
first release of the KANT facility for global function fields (i.e., finite
degree extensions of F_q(x)) will appear in V2.3. A fundamental operation
is the construction of the integral closures (maximal orders) of F_q[x]
and the valuation ring at the infinite place. Reduced integral bases
may be found using a reduction algorithm of Pohst and Schoernig. Ideals of
orders may be defined and a complete set of arithmetic operations on these
ideals are implemented. In particular, the factorization of an ideal may be
obtained. Important invariants of a field such as its genus may be found.
Finally, independent and fundamental units may be constructed.
COMPLEX FIELD: Real and complex arithmetic is provided by the PARI
package. This package includes a huge number of functions of interest to
number theorists including logarithmic and polylogarithmic functions,
elliptic and modular functions, Gamma and Bessel functions and, the
Riemann zeta-function. Xavier Gourdon's implementation of the Schoenhage
splitting circle method for computing the roots of an exact polynomial to
a specified precision is included. As an example, Magma takes 930 seconds
to determine the zeros of the degree 100 Laguerre polynomial to an
accuracy of 100 decimal digits.
LOCAL FIELDS: p-adic rings and fields are available in V2.2. General finite
extensions of p-adic rings (fields) will appear in V2.3. Apart from
arithmetic, the facilities include Hensel lifting, automorphisms,
factorization of polynomials and linear algebra over local fields.
----------------------
| MODULES AND LATTICES |
----------------------
________________________________________________________________________
R-modules K[G]-modules Hom modules Lattices
________________________________________________________________________
MODULES: An R-module M is viewed as a collection of n-tuples with the
action given by n x n matrices. Calculation with submodules requires M to
be defined over either a field, an euclidean domain or a polynomial ring
over a field. In the case of modules M and N defined over either F_q or a
number field, Magma can find composition series, composition factors,
Jacobson radical, socle series, End(M) and Hom(M, N). For example, taking
the simple group of Rudvalis and considering its permutation module P of
degree 4,600 over F_2, Magma determines the irreducible constituents of
P in 720 seconds. If the base ring is restricted to a finite field, maximal
and minimal submodules, and indeed the complete submodule lattice may be
found.
HOM MODULES: Given R-modules M and N, the set of all homomorphisms from M
to N, Hom(M, N), may be created as a module. In particular, rectangular
matrices are regarded as elements of an appropriate Hom module. In addition
to module-type operations, Hom modules support canonical forms and
morphism-type operations: image, kernel, cokernel etc. In the case of
Z-modules, the Hermite Normal Form and Smith Normal Form algorithms of
Havas have been implemented. Given a 1081 x 2657 integer matrix
corresponding to the abelianization of a certain finitely presented group,
Magma computes its elementary divisors, [2, 2, 2, 2, 102, 37842], in 82
seconds.
MODULES OVER K[x_1, ..., x_n]: Let R denote the ring K[x_1, ..., x_n],
where K is a field. Since R is not a PID, Groebner basis techniques are
employed to construct standard basis for submodules. This allows all the
usual submodule operations to be realized. Functions are provided for
computing syzygy modules and free resolutions. For homogeneous modules, it
is possible to find minimal bases and Hilbert series.
LATTICES: A powerful family of LLL algorithms based on the FP-LLL
algorithms of Schnorr and Euchner are included. Different variants on the
main algorithm are provided to achieve optimization across a wide range of
situations with particular attention being given to Z-lattices. Notable
algorithms include enumeration of shortest vectors, automorphism groups and
isomorphism testing. Given the 24-dimensional Leech lattice, Magma
enumerates the 98,280 (normalized) shortest vectors in 6.8 seconds and
finds its automorphism group in 175 seconds. The LLL algorithm can find
difficult Z-linear dependencies among the rows of matrices having
dimensions well over 500.
----------
| ALGEBRAS |
----------
________________________________________________________________________
Finite dimensional algebras Finite dimensional associative algebras
Matrix algebras Group algebras
Lie algebras (V2.3) Finitely presented associative algebras
________________________________________________________________________
STRUCTURE CONSTANT ALGEBRAS: A general finite dimensional algebra may be
defined by taking a free module over a field or Euclidean Domain (ED) and
giving a rule for multiplying basis elements (SC algebra). Subagebras as
well as left, right and two-sided ideals may be defined. The standard
arithmetic operations with ideals (membership, sum, intersection, product
etc) are available. In the case of an algebra defined over a field $K$,
quotient algebras, composition series, the composition factors and the
Jacobson radical may be constructed. If, in addition, $K$ is finite the
maximal and minimal left (right, two-sided) ideals, etc., may also be
found.
ASSOCIATIVE ALGEBRAS: If a SC algebra is associative, additional operations
are available. These include centre, commutator ideal, centralizer,
idealizer, left and right annihilators, and the construction of matrix
representations.
MATRIX ALGEBRAS: While a matrix algebra may be defined over any ring R,
most non-trivial computations require R to be an ED. If R is a field, a
new fast algorithm due to Allan Steel is used to construct the various
matrix canonical forms: Jordan, generalized Jordan, rational, primary
rational etc, while if R is an ED, recent algorithms of Havas and others
are used to compute characteristic polynomials and the Hermite and Smith
normal forms. Given a 100 x 100 matrix over Z with random one-digit
entries, Magma finds its Smith form in 40 seconds and its characteristic
polynomial in 270 seconds. The order of a unit over a finite field is found
using the very efficient algorithm of Leedham-Green. All of the operations
listed for associative algebras also apply to matrix algebras.
GROUP ALGEBRAS: Given a finite group of moderate order, its algebra over a
field or ED may be created. In addition to the standard operations for SC
associative algebras, specialized operations such as computing the
augmentation ideal are provided for group algebras.
FINITELY-PRESENTED ASSOCIATIVE ALGEBRAS: Given an algebra over a field, a
Todd-Coxeter procedure is used to construct matrix representations of
(finite dimensional) quotient algebras (Linton vector enumerator).
-----------------
| ELLIPTIC CURVES |
-----------------
________________________________________________________________________
Elliptic curves over a field or Z
________________________________________________________________________
ELLIPTIC CURVES: Elliptic curves may be defined over any field or Z.
Standard models are provided together with heights and invariants. For
curves with integer coefficients, invariants such as conductor, regulator,
and local information (Tate's algorithm) are available. For curves over Q,
the Mordell-Weil rank and group is computed using code based on John
Cremona's MWRANK program. Magma takes 280 seconds to determine that the
curve
y^2 + x*y = x^3 - 215*x + 1192
has group Z_2 x Z x Z, and 100 seconds to determine that the curve
y^2 = x^3 + 36861504658225*x^2 + 1807580157674409809510400*x
has rank 13.
----------------------
| INCIDENCE STRUCTURES |
----------------------
________________________________________________________________________
Enumerative combinatorics Graphs Incidence structures
Near-linear spaces Linear spaces t-designs
Projective planes Affine planes Linear codes
________________________________________________________________________
GRAPHS: Graphs may be directed or undirected. In addition, their vertices
and/or their edges may be labelled. Algorithms are implemented for all the
standard constructions and properties. Brendan McKay's automorphism program
(nauty) is used for computing automorphism groups and for testing pairs of
graphs for isomorphism. In accordance with the Magma philosophy, a graph
may be studied under the action of an automorphism group. Using the G-set
mechanism, an automorphism group can be made to act on any appropriate set
of configurations.
INCIDENCE STRUCTURES: General incidence structures provide a universe in
which families of incidence structures satisfying stronger conditions
(linear spaces, t-designs, etc) reside. Tools are provided for
constructing designs from difference sets, Hadamard matrices, codes and
other designs. The standard families of difference sets are incorporated.
A major feature is the ability to compute automorphism groups and to test
pairs of incidence structures for isomorphism.
FINITE PLANES: Although finite planes correspond to particular families of
designs, separate categories are provided for both projective and affine
planes in order to exploit the rich structure possessed by these objects.
Apart from elementary invariants, a reasonably fast method is available for
testing whether a plane is desarguesian. Among special configurations of
interest, a search procedure for k-arcs is provided. A specialized
algorithm developed by Jeff Leon is used to compute the collineation group
of a projective plane while the affine case is handled by the incidence
structure method. The collineation group (order 2^3 3^8) of a ``random''
projective plane of order 81 supplied by Gordon Royle was found in 1,202
seconds. As with graphs and designs, the G-set mechanism gives the action
of the collineation group on any appropriate set.
LINEAR CODES: Currently, the coding theory module is designed for linear
codes over finite fields though this will be extended to linear codes over
finite rings in the near future. A very large number of constructions are
supported together with the determination of all the standard invariants.
Carefully crafted algorithms are provided for computing the minimum weight
and weight enumerator. For example, computation of the minimum weight (15)
of a [79, 40, 15] quadratic-residue code takes 23 seconds; computation of
the weight distribution of the [64, 22, 16] Reed-Muller code (r = 2, m = 6)
takes 2.9 seconds. Automorphism groups may be computed over any field
GF(p), p a prime, and GF(4), again using Leon's PERM package. Finally,
some standard decoding techniques are supported.
________________________________________________________________________
MAGMA HOMEPAGE: The reader is referred to the Magma home page for a more
detailed listing of facilities together with numerous examples.
http://www.maths.usyd.edu.au:8000/comp/magma/Overview.html
GETTING MAGMA: For more information, or to order the system, contact:
Email: magma@maths.su.oz.au Telephone: +61 2 9351 3338 Fax: +61 2 9351 4534
Smail: Magma Group, Mathematics, University of Sydney, NSW 2006, Australia
--------------------------------------------------------------------------
Hans-Wolfgang Loidl <hwloidl@dcs.glasgow.ac.uk>
Last modified: Wed Jul 9 02:08:46 1997 Stardate: [-31]9605.23