|
[Next][Prev] [_____] [Left] [Up] [Index] [Root]
This screen provides a terse summary of the new features installed in
Magma for release version V2.8 (July 31, 2001). For more details, see
the full release notes in the files relv28.dvi or relv28.ps, or see the
full release notes at the top page of the HTML version of the Help system.
- Documentation
-
- Groups
-
-
Permutation Groups: An algorithm for determining the maximal subgroups
of a permutation group is provided. This is applicable to any group for
which the non-abelian composition factors either have order less than
1.6*10^7 or have a permutation representation of degree less than 32.
-
Permutation Groups: The machinery for finding all conjugacy classes of
subgroups has been extended to a much larger class of groups. In
particular, the former limitation that the trivial Fitting quotient
have order less than 216,000 has been removed. Variations are provided
to find all conjugacy classes of subgroups satisfying some condition.
-
Permutation Groups: The maximal subgroup algorithm is used as the basis
for an algorithm for determining all subgroups whose index is less
than some given bound. This is much more efficient than finding all
subgroups and selecting those which satisfy the index condition.
-
Permutation Groups: A new algorithm for finding the automorphism group
of a permutation group is also included. A variation may be used to
determine whether two permutation groups are isomorphic.
-
Matrix Groups: New algorithms for computing the conjugacy classes of
elements and the maximal normal p-subgroup in a finite matrix group
have been installed.
-
Matrix Groups: Several functions for analysing the action of a matrix
group over a finite field on subspaces of the underlying natural vector
space have been introduced. These functions are designed to handle
situations where the orbits may be large.
-
Finitely Presented Groups: Much of the basic infrastructure for
finitely presented groups has been redesigned, yielding improved
performance and greatly increased applicability of key functions for
fp-groups.
-
Finitely Presented Groups: New versions of the algorithms for coset
enumeration, simplification of presentations by Tietze transformations,
Reidemeister--Schreier re-writing and computation of p-quotients have
been installed. An interactive coset enumeration facility is now
available.
-
Finitely Presented Groups: The function Order for finitely presented
groups has been revised and now uses a much more sophisticated strategy
for determining the order of a (finite) group or for proving that the
group is infinite.
-
Polycyclic Groups: The functionality of the new category of polycyclic
groups introduced in V2.7 has been greatly increased. In particular,
algorithms have been implemented that compute the following: a normal
series where the factors are either elementary abelian p-groups or free
abelian groups; the Fitting subgroup; the Fitting series, the upper
central series; the centre. For the case of nilpotent groups, functions
that compute normalizers and centralizers have been installed.
-
p-Groups: New implementations by Eamonn O'Brien of an algorithm for
computing the automorphism group of a p-group and also an algorithm for
generating p-groups have been installed. The new p-group generation
implementation overcomes problems associated with file handling that
affected the previous implementation.
-
Generic Abelian Groups: A new category has been created for generic
(finite) abelian groups. The creation of a generic abelian group is a
new feature which allows the user to create an abelian group over any
domain given that an identity and a group operation have been defined.
Features include finding the order of an element, determining a
presentation from generators, and computing the discrete logarithm of
an element.
-
Subgroups of PSL(2, R): A package for working with congruence subgroups
of PSL(2, R) has been developed by Helena Verrill. The package includes
graphics facilities which allow the user to produce pictures of
fundamental domains.
-
Databases: Several new databases of groups have been created, e.g. for
perfect groups, almost simple groups, rational maximal finite matrix
groups and finite quaternionic matrix groups.
- Groups of Lie Type
-
-
Root Datum: A data type has been introduced for root datum of groups of
Lie type.
-
Coxeter Groups: The module for Coxeter groups has been considerably
expanded.
-
Lie Groups: A data type has been introduced for groups of Lie type.
The basic group operations have been implemented over any field.
- Basic Rings
-
-
Integers: An experimental implementation of the number field sieve
(NFS) for factoring large integers is now available.
-
Integers: The Factor} database maintained by Richard Brent has been
updated. It now contains 221,188 factors f of integers a^n +- 1, where
a < 10000, n < 10000, and f > 10^9.
-
Univariate Polynomial Rings: Polynomials over the integers or rationals
are now factored by the new algorithm of Mark van Hoeij. The search
for the correct combination of modular factors (which has exponential
worst-case complexity in the standard Berlekamp--Zassenhaus algorithm)
is performed by van Hoeij's algorithm, which efficiently finds the
correct combinations by solving a Knapsack problem via the LLL
lattice-basis reduction algorithm.
- Extensions of Rings
-
-
Galois Rings: Basic facilities for computing with Galois rings have
been implemented.
-
Number Fields: Algebraic number fields and their orders have been
substantially revised in Magma V2.8. A new field type has been created
for the field of fractions of an order of a number field. More
functionality has been provided for both absolute and relative fields
and orders.
-
Number Fields: Factorization of univariate polynomials defined over
number fields has become enormously more efficient through use of the
van Hoeij ideas. It is now possible to factor a difficult degree 15
polynomial over a degree 15 extension of Q in a few seconds.
-
Number Fields: Multi-step relative extensions are now fully supported
with most operations for absolute extensions generalized for this
situation. In particular, factorization and integral closure are now
supported for relative extensions.
-
Number Fields: Some restrictions on the creation of number fields
(orders) have been removed. Thus, it is now possible to create a field
or order using a non-monic polynomial. Further, it is possible to
construct non-simple and linear extensions.
-
Number Fields: Highly efficient arithmetic has been implemented for
residue class rings. In addition, the calculation of unit groups of
such rings is supported at least for quotients of absolute maximal
orders.
-
Number Fields: It is now possible to form the completion of a number
field at a (finite) prime.
-
Number Fields: Code implemented by Claus Fieker computes the p-Selmer
group at a list of primes.
-
Number Fields: Initial machinery has been provided for class field
theory. In particular, a new type for abelian fields} has been
provided. It is now possible to construct ray class groups and class
fields based on them (i.e. in terms of defining equations).
-
Number Fields: It is now possible to compute the relative Galois group
and relative subfields of a one-step relative extension of Q.
-
Quadratic Fields: Quadratic fields have been redesigned so that they
are now number fields with the addition of some special code
implementing fast algorithms peculiar to quadratic fields. Thus, for
the first time all number field operations are supported for quadratic
fields.
-
Cyclotomic Fields: Cyclotomic fields have been redesigned so that they
are now number fields with the addition of some special code
implementing fast algorithms peculiar to cyclotomic fields. Thus, for
the first time all number field operations are supported for cyclotomic
fields.
-
Function Fields: Machinery for constructing and working with
differentials has been introduced. It is possible to compute the space
of holomorphic differentials for a given divisor. Other operations
include computing the valuation of a differential at a place, computing
the residue of a differential at a place of degree 1 and working with
higher differentiations.
-
Function Fields: A function that determines the sequence of Weierstrass
places has been developed. Related functions compute the sequence of
global gap numbers of a divisor or the sequence of gap numbers of a
divisor at a place of degree 1.
-
Function Fields: The divisor class group of a global function field may
be computed using an algorithm and implementation due to Florian Hess.
This also allows other related information to be determined: e.g., unit
group, S-class group, S-units and S-regulator for a finite set of
places S.
-
Function Fields: Given the elliptic function field E: y^2 + xy + x^3 +
ax^2 + b defined over GF(q^n), a function is provided that computes a
hyperelliptic function field in the Weil restriction of E over GF(q).
This feature is of particular interest to cryptographers.
-
Function Fields: A generic algorithm is provided for the factorization
of univariate and multivariate polynomials over function fields.
-
Function Fields: The Galois group and lattice of subfields may be found
for a function field using code implemented by Katharina Geissler.
- Commutative Algebra
-
-
Ideal Theory: It is now possible to compute Groebner bases of ideals of
polynomial rings defined over Euclidean rings (including the important
case of the ring Z. Such Groebner bases are constructed by an
extension of Jean-Charles Faugere's F_4 algorithm which uses sparse
linear algebra (algorithm due to Allan Steel). Many of the standard
functions provided for ideals in polynomial rings defined over fields
are now generalized to ideals in polynomials rings defined over
Euclidean rings.
- Linear Algebra and Module Theory
-
-
Matrices: Several new advanced algorithms for matrices over Z or Q have
been implemented (and more will follow in the future). The new
algorithms are for computing determinants, characteristic polynomials
and minimal polynomials.
-
Modules over Orders: Modules over orders are now supported.
- Algebraic Geometry
-
-
Schemes: The algebraic geometry types together with their basic
functionality have been moved into the kernel. This includes the
integration of many of the specialised curve types such as elliptic and
hyperelliptic curves. This significantly increases the power of the
geometry types, allowing the user to apply the functionality of both a
specialised curve type and the general scheme type to a single object.
The change also makes available many generic constructors and standard
set and sequence operations, which were previously not available for
the geometry types.
-
Schemes: Maps between schemes have been enhanced with the provision of
new constructors and the ability to calculate images and pullbacks
available in more circumstances. Maps may now be defined between
actual schemes now rather than just between affine or projective
spaces.
-
Curves: Plane curves have been tied very closely to the function field
machinery in Magma. The result is that computations with divisors and
their Riemann--Roch spaces can be made entirely in the geometric
context. The applications include: gap numbers, canonical embeddings
of curves, class group computation over finite fields, constructions of
geometric codes from curves and many other standard methods in the
geometry of curves.
-
Curves: A new facility for computing with plane conic curves has been
written. Its major feature is an implementation of a new algorithm by
John Cremona (Nottingham) to find points with reduced coordinates on
conics defined over the rational numbers. This implementation is very
fast, improving on Cremona's initial test timings.
-
Elliptic Curves: Elliptic curves are now scheme types and inherit all
of the appropriate scheme functionality. In particular, all of the
machinery for divisors and differentials now applies to elliptic
curves. Subgroup schemes of elliptic curves are now also schemes. John
Cremona's database of elliptic curves has been updated to conductor
10,000.
-
Hyperelliptic Curves: Machinery for computing the automorphism group of
a hyperelliptic curve has been implemented by Michael Stoll. Pierrick
Gaudry has implemented a number of methods for counting points on the
Jacobian of a hyperelliptic curve. These include the Schoof algorithm
for a genus 2 curve. Code for determining Igusa invariants has been
provided by Everett Howe while Pierrick Gaudry has implemented an
algorithm for constructing a genus 2 curve from the Igusa invariants.
-
Modular Curves: A package for modular curves has been developed by
David Kohel of the Magma group. A modular curve is defined in terms of
standard affine modular equations which are stored in precomputed
databases. The possible model types are ``Atkin'', ``Canonical'', and
``Classical''.
-
Modular Forms: A package for modular forms developed by William Stein
is now included. Facilities include the computation of a basis of
modular forms on Gamma_1(N), the computation of all newforms of given
level, and the decomposition into Eisenstein, cuspidal, and new
subspaces.
-
Brandt Modules: A package for Brandt modules has been developed by
David Kohel. Facilities include the construction of a Brandt module on
the left ideal class of a definite order in a quaternion algebra over
Q, the decomposition of a Brandt module under the action of
Atkin--Lehner and Hecke operators and the construction of the
Eisenstein and cuspidal subspaces.
-
K3 Surfaces: A database of K3 surfaces has been added. It contains
characteristic data for K3 surfaces embedded in weighted projective
spaces in codimension up to 4. The functions used to create the
database are also included so that users can extend the database or
create similar databases.
-
Handbook: All geometric chapters of the Handbook have undergone major
revision. Many more examples have been included, some of which are
extended calculations which illustrate different parts of the new
geometry packages working together.
- Incidence Structures
-
-
Graphs: The nauty program due to Brendan McKay for finding
automorphisms in graphs has been updated to the latest version (2.0)
and its user interface within Magma has been enhanced. This new version
of nauty is often much faster than the previous version installed
within Magma.
-
Graphs: A database of strongly regular graphs due to Brendan McKay et
al is now available.
-
Graphs: A program for the orderly generation of graphs satisfying a
range of conditions, written by Brendan McKay, is now accessible from
within Magma.
- Coding Theory
-
-
Codes over Fields: Magma V2.8 incorporates a database containing
constructions of the best known linear codes over F_2 of length up to
256. The codes of length up to 36 are optimal. The database is complete
in the sense that it contains a construction for every set of
parameters. Thus the user has access to 33,152 best-known binary
codes. Similar databases for other small fields will be added in the
near future. The implementation of this database has been a joint
project with Markus Grassl.
-
Codes over Fields: Functions are provided to construct
Algebraic--Geometric codes.
-
Codes over Rings: Magma includes facilities for linear codes defined
over Z_4 for the first time.
- Optimization
-
|
