Release Notes V2.2 (18 April 1997)

This screen provides a terse summary of the new features installed in Magma for release version V2.2 (April 18, 1997).

Summary

• User-defined attributes for structures have been introduced.
• The database used for finding representatives of conjugacy classes of subgroups has been expanded so that the subgroups of a permutation group having a radical quotient of order up to 216,000 may now be found (previous limit was 20,160).
• The algorithm used for finding conjugacy classes of elements in permutation groups has been vastly improved.
• A new fast integer arithmetic package has been developed from scratch which provides very substantial speed-ups over the previous integer package used by Magma. All higher level integer functions, other than the ECM and QS factorization modules, have been rewritten or heavily revised to improve performance and to remove memory leaks.
• Primality proving is now performed using Francois Morain's ECPP package.
• The Groebner basis machinery (particular over the rational field and rational function fields) has been sped up significantly by careful new use of the new integer package and by improved strategies.
• The second stage of the Magma invariant theory module is completed with new improved algorithms for optimal-degree primary invariants and for modular secondary invariants (both due to G. Kemper) together with algorithms for computation of algebraic relations, free resolutions and other properties.
• A powerful family of LLL algorithms have been developed.
• A first version of modules for computing with algebras is included for the first time. The classes of algebra supported include general finite dimensional algebras (defined by structure constants), finite dimensional associative algebras, and group algebras.

General Groups [HB 15]

• The function CommutatorGroup has been extended to work for non-normal subgroups H and K.
• Preimage is now available for CosetAction.

Finitely Presented Groups and Soluble Groups [HB 16, 19]

• An important optimization has been introduced into the algorithm used for finding conjugacy classes in soluble groups. In some cases the enhanced algorithm is up to 100 times faster.
• The implementation of functions that apply to subgroups of finite index in a finitely-presented group have been made more robust.
• A bug in the function Core for fp-groups has been fixed.
• The ncl-constructor for fp-groups now returns objects of the correct type.
• A bug where the words corresponding to the generators of a rewritten subgroup were incorrect has been fixed. This affected functions Rewrite and Simplify. (Reported by Marston Conder.)

Abelian Groups [HB 18]

• Quotients are now presented on a minimal generating set.

Permutation Groups [HB 20]

• The database used for finding representatives of conjugacy classes of subgroups has been expanded so that the subgroups of a group having a radical quotient of order up to 216,000 may now be found (previous limit was 20,160).
• The algorithm used for finding conjugacy classes of elements has been vastly improved. This will extend its range of application enormously and has an impact on other algorithms, e.g. computing the character table of a group.
• A fast algorithm for computing the action of a permutation group on the cosets of a subgroup has been installed. This affects many other algorithms, e.g. testing whether a subgroup is maximal; computing transitive representations of a permutation group. See especially functions CosetTable, CosetAction. Transversal, IsMaximal and the quo-constructor.
• The function IsConjugate now computes the centralizer of one of its element arguments to improve speed. This may slow the function down slightly in easy cases but can lead to a big improvement in execution time for harder examples.
• A bug whereby factors of the socle of a primitive group were sometimes incorrect has been repaired.
• The function MinimalPartition now signals a user error if its argument is an intransitive group.
• A minor bug in ChiefSeries has been fixed.
• Many instances where memory blocks were not being deleted have been identified and fixed.
• A bug in the cohomology code has been fixed by Derek Holt.
• Changes have been made to the cohomology code to make it work correctly on 64-bit machines.

Matrix Groups [HB 21]

• Constructions for additional families of Chevalley groups: E_6(q), E_7(q), F_4(q), G_2(q), 3D_4(q), 2F_4(q), 2G_2(q), and the Tits group. A minor problem with the orthogonal group construction has been fixed.
• A fast algorithm for computing large powers of a matrix over a finite field has been installed (see Matrix Algebras below).
• An error that sometimes caused the function computing the centralizer of an element to crash has been fixed.
• It is now possible to compute an action on the orbit of a trivial group.

Characters of Finite Groups [HB 22]

• A subtle bug in the code used to split 2-dimensional character spaces in the algorithm used by CharacterTable has been fixed. (Reported by Sabrina Hessinger.)

Integer Ring [HB 24]

A new fast integer arithmetic package has been developed from scratch. This provides very substantial speed-ups over the previous integer package used by Magma. New data structures are employed and many new (for Magma) algorithms have been introduced. These include specialized Karatsuba for integer product, an exact divide function and the Weber accelerated GCD algorithm. Assembler macros are used for critical operations and 64-bit operations are used in DEC-Alpha machines. On a Sun Ultra 2, Magma V2.2 multiplies 300 bit integers 4 times faster than Magma V2.1 and 1500 bit integers 7 times faster.

As part of the upgrade of the integer module, all higher level integer functions, other than the ECM and QS factorization modules have been rewritten or heavily revised to improve performance and to remove memory leaks. Also improved memory management strategies have contributed to the performance upgrade. Significant functions included in this revision include the calculation of square roots modulo m (m not necessarily prime) and the solution of norm equations in quadratic fields.

A much more efficient strategy for integer factorization has been introduced. The central idea is to strike the right balance between the application of ECM and QS. The new strategy runs ECM for about 10% of the expected running time of QS so as to ensure any factors having fewer than 20 -- 25 digits are discovered (in the case of an 80 digit integer). The new strategy will, in the worst case, factor 70 digit integers in about an hour and 80 digit integers in about 8 hours using a single processor on a Sun Ultra 2. The average time for factoring a random 80 digit integer is less than one hour. Using a small network of workstations, factoring 90--100 digit integers is routine. Further improvements to the factorization capability are expected in the near future.

The Elliptic Curve Primality Prover (ECPP) designed and implemented by Francois Morain at INRIA has been installed in Magma V2.2. This provides fast rigorous primality proofs for integers having several hundred digits. The primality of a 100 digit integer is established in 24 seconds (on an Sun Ultra 2). ECPP is now used by default by the Magma functions IsPrime and Factorization.

Summary of new features:

• New main strategy for function Factorization with control over the amount of effort expended by each subalgorithm. The parameters have also been changed.
• Independent factorization functions TrialDivision, SQUFOF, PollardRho, pMinus1, ECM, MPQS with controlling arguments are now provided. (The function Factor has been removed.)
• New verbose flag Factorization.
• Primality proving is now performed using Morain's ECPP package (automatically called by the function IsPrime, etc.). The functions Primality and PrimeCertificate have been removed. New equivalent functions will follow soon which will be based on the ECPP package.
• An expanded version of the Cunningham database of factorizations of integers having the form a^n+/-1 compiled by Brent and associates (containing 199,044 factorizations for all bases less than 1000).
• Probabilistic primality testing of integers (function IsProbablePrime).
• Functions EulerPhi, CarmichaelLambda, MoebiusMu, and DivisorSigma now allow a factorized integer as argument.
• New functions FactoredEulerPhi and FactoredCarmichaelLambda which return their results as factored integers.

  Changes:

• Function InverseMod renamed to Modinv.
• Function Order (taking 2 integers) renamed to Modorder.

Rational Field and Rational Function Fields, [HB 26, 31]

Improved algorithms have been introduced for performing arithmetic on the elements of both the rational field and rational function fields. This has lead to a substantial speed-up for algorithms that make extensive use of rational arithmetic. Specialized fraction-free matrix and polynomial algorithms have also been introduced for these fields.

Summary of new features:

• Computation of the (complete) squarefree partial fraction decomposition of a function field element (function PartialFractionDecomposition).

Finite Fields [HB 27]

• Function IsPower to test whether an element of a finite field is a power and to return the root if so.
• Faster arithmetic in very large prime finite fields through use of the new integer package and the Montgomery modular multiplication algorithm (further improvements under development).

Univariate Polynomial Rings [HB 28]

• New function Round which takes a polynomial over a subring of the real field and rounds all of the coefficents to the nearest integer.
• New function HasRoot which takes a polynomial and returns a single root if existent (more efficient particularly over finite fields than computing all roots).

Multivariate Polynomial Rings [HB 29]

A range of improvements and optimizations have been made to the Groebner Basis machinery which improves its performance over the rational field (in particular, careful efficient use of the new integer package has led to very significant improvements). The Groebner Walk algorithm has been improved also in light of the new integer package (constructions with weight vectors). New improved strategies for the main Buchberger algorithm have been introduced, including (automatic) homogenization of ideals, and new techniques for reducing the basis during the computation. A grevlex Groebner basis for the Cyclic-7 roots example takes 930 seconds on a Sun Ultra 2. Many new features have been added which are related to Invariant Theory.

Summary of new features:

• New parameters Homogenize, ReduceInitial, and ReduceByNew for the procedure Groebner to allow control of strategy.
• A more efficient algorithm (the modular method) for computing univariate and multivariate resultants has been implemented.
• Multivariate GCD over Z and Q improved.
• Function Reduce to reduce a basis and function ReduceGroebnerBasis to reduce a (known) Groebner basis.
• Groebner basis computation over function fields has been significantly improved.
• Functions HomogeneousComponent and HomogeneousComponents for construction of homogeneous components of polynomials.
• Functions MonomialsOfDegree and MonomialsOfWeightedDegree for construction of all monomials of a given total degree or weighted degree.
• Function MinimalAlgebraGenerators for the construction of a minimal generating set of a polynomial subalgebra.
• Functions HomogeneousModuleTest and HomogeneousModuleTestBasis for computing with a submodule over a subalgebra in a polynomial ring.
• Multivariate GCD over finite fields fixed (included content in a particular variable too many times for some inputs).

Invariant Rings of Finite Groups [HB 30]

The first stage of the Magma module for computing with invariant rings of finite groups was released in V2.1. Magma V2.2 contains the second stage of our planned invariant theory machinery.

Summary of new features:

• The Reynolds operator has been improved significantly for matrix groups over the rational field (fraction-free methods) and all other computations over fields of characteristic zero have been sped up significantly as a consequence of the new integer package.
• A new algorithm developed by Gregor Kemper (late 1996) for computing primary invariants guarantees that the degrees of the invariants constructed are optimal (with respect to their product and then sum) (function PrimaryInvariants).
• Similarly, a new improved algorithm developed by Gregor Kemper (early 1997) for computing secondary invariants in the modular case has been implemented (function SecondaryInvariants).
• It is now possible to determine the (algebraic) relations between secondary invariants using the functions Relations and RelationIdeal (also algebra presentation given by function Algebra).
• Irreducible secondary invariants (which generate all secondary invariants under multiplication) may be accessed (function IrreducibleSecondaryInvariants).
• Function FundamentalInvariants has been vastly improved by using irreducible secondary invariants and a new minimalization algorithm.
• A free resolution of an invariant ring (i.e. of its corresponding module) may be computed (function FreeResolution).
• Depth and homological dimension of an invariant ring computable (functions HomologicalDimension, Depth).
• Construction of Steenrod operations (function SteenrodOperation).
• Many attributes of invariant rings may also be set or examined by the user (using the new user-attribute mechanism).
• Known invariants of a particular degree may be set (procedure SetAllInvariantsOfDegree).

Algebraic Number Fields [HB 33, 34]

The arithmetic for cyclotomic and quadratic fields has been completely rewritten to take maximum advantage of the new integer package. This has led to significant speed-ups.

Summary of new features:

• New functions GaussianIntegerRing, EisensteinIntegerRing.
• Memory leaks in the code for solving norm equations have been fixed.
• Bugs occurring on 64-bit machines in class group computation of quadratic fields have been fixed.
• Bugs occurring on 64-bit machines in galois group computations have been fixed.

Real and Complex Fields [HB 36]

• Function Round now takes a Complex number and yields a Gaussian integer.

Modules and Lattices

A powerful family of LLL algorithms have been developed. These are based on the FP-LLL algorithms of Schnorr and Euchner. Different variants on the main algorithm are provided to achieve optimized performance in different situations. The case for the ring of integers is specially optimized, particularly when the integers are small. C double precision floating-point numbers are used for efficiency but arbitrarily-sized integers are also handled robustly, avoiding overflow problems. Another version works off the Gram matrix of a basis rather than the basis itself. This algorithm is automatically used internally whenever it is more efficient. Further optimizations are under development.

Vector Spaces [HB 40]

• Tensor product of vector spaces and their elements (function TensorProduct).

Modules Hom(U, V) [HB 42]

• LLL algorithms for a lattice defined either by a basis matrix or a Gram matrix (functions LLL and LLLGram).

Modules over K[x_1, x_2, ..., x_n] [HB 43]

• Free resolutions of modules (functions FreeResolution and MinimalFreeResolution).

Finite Dimensional Algebras (New Category) [HB 44, 45, 46]

• Creation of both associative and non-associative algebras defined by structure constants.
• Direct sums.
• Creation of subalgebras, ideals, and quotient algebras.
• Operations on subalgebras: intersection, products, powers.
• Element operations and properties: arithmetic, identity, unit testing, zero divisors, nilpotency.
• Bases: dimension, independence, basis elements, coordinates (for algebras defined over a field).
• Algebra properties: associativity, commutativity, Lie properties.
• Ideal structure: maximal and minimal ideals, Jacobson radical, simplicity, semi-simplicity, composition series.
• Operations for associative algebras: centre, centralizer, idealizer, Lie product, commutator ideal, regular representation.

Group Algebras (New Category) [HB 47]

• Creation of group algebras: both vector and term representation of elements are supported -- allowing calculation in groups of arbitrary size.
• Creation of subalgebras, ideals, and quotient algebras.
• Operations on subalgebras: intersection, products, powers.
• Element operations and properties: arithmetic, identity, unit testing, zero divisors, nilpotency, involution, support.
• Bases: dimension, independence, basis elements, coordinates (for algebras defined over a field).
• Augmentation ideal, augmentation map.
• Algebra and subalgebra properties: commutativity, ideal testing.
• Ideal structure: maximal and minimal ideals, Jacobson radical, simplicity, semi-simplicity, composition series.
• Centre, centralizer, idealizer, annihilators, Lie product, commutator ideal, regular representation.

Matrix Algebras [HB 48]

• LLL algorithms for a lattice defined either by a basis matrix or a Gram matrix (functions LLL and LLLGram).
• A new algorithm to efficiently compute large powers of matrices over finite fields has been installed. The algorithm works by computing the Jordan form of the matrix, then directly writing down the appropriate powers of the blocks and finally transforming to obtain the result.

Finite Planes [HB 54]

• An improved version of Jeff Leon's algorithm for computing collineation groups of projective planes has been installed. This is capable of computing collineation groups of planes having order up to 81. (Functions CollineationGroup and Isomorphism.)

Error-correcting Codes [HB 55]

• Computation of the set of all words of a code having a specific weight which consist of zeros and ones alone (function ConstantWords).
• New version of minimum weight algorithm which allows for an early abort from a minimum weight computation (function VerifyMinimumWeight).
• Function ExtendCode now applies also to non-binary codes.