Skip to content

GSoC 2013 Application Tom Bachmann: Extensions to the AGCA module

Jump to bottom Edit New page
ness01 edited this page Apr 15, 2013 · 6 revisions

This application is work in progress. . At this state of writing, it should nonetheless convey a good idea of what I am planning to do.

Preliminaries

See my other draft application for general information about me, not specific to this project.

Project

The aim of this project is to extend the commutative algebra module of sympy. I started the commutative algebra module ("agca") (and am currently the sole contributor) to integrate the groebner basis code in polys/ in a pythonic fashion into sympy. Specifically, the agca module focusses on commutative algebra computations involving modules over polynomial rings.

In its current state, the module is very incomplete, and in any case far behind the obvious competitors (macaulay2 and singular). Also, it is somewhat removed from the sympy core focus (although we had some interesting success regarding trigsimp).

My basic suggestion then would be to extend the agca module, not focussing on polynomial rings, but on fields and PIDs. In particular, I want to implement Ext and Tor functors for modules over finite-dimensional algebras.

Deliverables

Specifically, I plan to implement the following:

  • "basic operations" (see below) for vector spaces (using the matrices module)
  • a Smith normal form algorithm in the matrices module
  • basic operations for modules over euclidean domains (using the Smith normal form algorithm)
  • a polys domain, and supporting classes, to represent fre finite algebras over a ring in terms of composition of basis element; particular support for group algebras
  • basic operations for modules over finite algebras
  • classes for working with chain complexes
  • unoptimized free resolutions of modules over polynomial rings
  • bar resolution for finite-dimensional algebras over a field
  • classes for representing (derived) functors
  • computation of Hom and Tensor functors on all supported modules

These additions, taken together, allow the computation of group homology and cohomology, of Hochschild cohomology of finite-dimensional algebras, and much more.

The support for modules over PIDs also allows, given a finitely presented abelian group, to decompose it into a sum of free and cyclic modules.

I anticipate that all of these additions should be doable reasonably speedily, so there should be time left after they are all done. Here are some stretch goals which I could make progress on, in this case:

  • support for graded rings, and modules over them (specifically, graded versions of all of the above)
  • add groebner basis algorithms for polynomial rings over PIDs (such as (ZZ[X, Y]))
  • add groebner basis algorithms for non-commutative rings (e.g. group rings)
  • advanced operations, like radicals, primary decomposition, ...

Recollections about the AGCA module

Since the AGCA module was design without much input from the sympy community, I recall here its basic concepts. As part of the GSOC project, I am open to redesigning it, if the community feels this would lead to improvement.

The (polys) module is one of the workhorses of sympy (another notable workhorse being the matrices and logic modules). Like other workhorses, unless it is dressed up nicely, it will be used much less than would be possible. For example, there are very complicated and well-optimized multivariate polynomial factorization algorithms in the polys module. However, those by themselves are hard to use. They provide specialised, complicated interfaces, and one has to know very specifically what one is trying to accomplish in order to exploit them. On the other hand, these algorithms can work with essentially arbitrary expressions (treating everything unknown as its own variable), and are hence used throughout simplification and cancellation routines of sympy. Thus, the specialised, powerful algorithms are wrapped into user-friendly functions and classes.

In simple terms, the agca module was started to do the same thing for the groebner basis algorithms in the polys module. They are used by (solve()) for solving multivariate polynomial equations. But there are so many more possibilities if one is interested in commutative algebra: computing kernels, intersections, radicals etc etc.

So much for the motivation of the commutative algebra module. For its actual usage, refer to the documentation and the tutorial. Let me say a few words about the implementation. In general, the agca module (as in sympy module) deals with modules over rings, and homomorphisms between them (and ideals, but we can ignore that). Both rings and modules are (mathematically) sets, and their elements will be called ring or module elements.

The rings and ring elements are supplied by the (domains) submodule of polys. (Currently the only supported domains are (PolyRing) and (QuotientRing).) From the point of view of the agca module, these are relatively passive: the ring object can be used to convert (essentially) arbitrary objects into elements of the ring (or throw an exception if this is not possible), and then the ring elements are expected to behave reasonably -- i.e. it should be possible to add and multiply them, divide by them if they are units, they should print themselves, etc.

So much is dictated by the polys module. Now we come to the philosophy of the implementation of the agca module. The basic idea is to have abstract base classes, which provide rich interfaces, and implement them in terms of a few key methods. Subclasses then implement these key methods. The users themselves should never instantiate either the abstract classes (which would be useless) or the subclasses; instead they should call explicit constructor methods.

For example, (R = QQ[x, y, z]) creates a polynomial ring in three variables. Then (M = R.free_module(2)) creates a two-dimensional free module over (R). As with the domains, the modules can be used to convert arbitrary sympy expressions into module elements:

In [4]: M.convert([1, x])
Out[4]: [1, x]

In [5]: type(_)
Out[5]: sympy.polys.agca.modules.FreeModuleElement

In general, the agca module tries to do conversions automatically, where they are unambiguous (in general, whenever an expression involves only sympy objects, and elements of only one module), e.g.

In [6]: _4 + [y, x]
Out[6]: [y + 1, 2⋅x]

Now in order to create e.g. a submodule of (M), we call an explicit submodule constructor:

In [7]: N = M.submodule([x, y])

In [8]: N
Out[8]: <[x, y]>

In [9]: type(_)
Out[9]: sympy.polys.agca.modules.SubModulePolyRing

Here we see that the polys module automatically created a subclass of the abstract class (SubModule) which works for polynomial rings, i.e. uses groebner basis algorithms for computations, like module membership, equality, etc:

In [10]: N == M/[[x, y]]
Out[10]: False

In [11]: M/N == M/[[x, y]]
Out[11]: True

In [12]: [x**2, x*y] in N
Out[12]: True

In [13]: [x**2, x] in N
Out[13]: False

This basic philosophy is replicated throughout the agca module. Regarding modules, there exist the abstract classes (Module, FreeModule, SubModule, QuotientModule, SubQuotientModule), and they have implementations over polynomial rings (called (FreeModulePolyRing) etc) and over quotient rings. The implementations over polynomial rings use groebner basis algorithms, whereas those over quotient rings reduce to problems over the base rings. There are also classes for homomorphisms, working in essentially the same way (refer to the documentation for more details).

Notably, none of the agca classes derive from Basic, since there seemed no use for that. Also, the agca module uses manual caching. E.g. a submodule is initially created by passing just its generators. But any non-trivial problem (like module membership) requires a groebner basis, and this computation is cached in internal variables.

In general, if (R) is a ground ring (i.e. polys domain) which is supported by the agca module (currently these are only polynomial rings and their quotients), then the basic operations can be performed:

  • construct free modules, submodules, quotient modules, subquotients
  • answer submodule module membership, containment
  • represent homomorphisms between all these kinds of modules
  • compute kernels and images of homomorphisms
  • compute module quotients (this is not the same as quotient modules!)
  • some basic operations on ideals

Some details on the new additions

Here I provide some examples of how I envision the interface to the new additions. Of course, much of the project is "implement basic operations over ring XYZ", so this provides no new interfaces at all.

First of all, a Smith normal form algorithm. This takes a rectangular matrix with entries in a polys domain, a Euclidean function, and a division algorithm for this domain. It returns the matrix in Smith normal form, and optionally a basis transformation matrix. (Smith normal form does the following: given a free module (F) generated by (e_1, ..., e_n) over the euclidean domain R, and vectors (v_1, ..., v_m), we express the (v_i) in terms of the (e_j) to get a matrix. The algorithm finds a new basis (f_1, ..., f_n) such that the matrix expressing the (v_i) in terms of the (f_j) has a canonical form.) An example usage would be like so:

def euclidean_function(n):
    return abs(n)

def division_algorithm(p, q):
    """
    Given integers p, q, such that p != 0,
    return integers r, s such that p = rq + s, and s = 0 or |s| < |q|.
    """
    if p < 0:
        ...
    if q < 0:
        ...
    return p // q, p % q

>>> M = Matrix([[2, 4, 4], [-6, 6, 12], [10, -4, -16]])
>>> smith_normal_form(M, euclidean_function, division_algorithm)
⎡2  0  0 ⎤
⎢        ⎥
⎢0  6  0 ⎥
⎢        ⎥
⎣0  0  12⎦

(This tells us that the abelian group generated by x, y, z, subject to the relations 2x+4y+4z=0, 6x=6y+12z, 10x=4y+16z is isomorphic to the direct sum of cyclic groups of orders 2, 6 and 12.)

I will of course "write" euclidean functions and division algorithms for the domais of integers and univariate polynomials (or rather, pull together existing code in the uniform format described here). Next, I will implement new subclasses for the agca module, such as FreeModuleEuclideanDomain etc. These can reduce all operations to smith normal form computations (and the euclidean algorithm). Additionally, the submodule and quotient module implementations will provide nice interfaces to the smith normal form module, by exposing generators of a direct sum decomposition. These classes will all internally store the euclidean function and division algorithm. I will then add implementations of the method (free_module) to the domains of integers and univariate polynomials, which pass the correct euclidean function to the (FreeModuleEuclideanDomain) class. Once this is done, modules over these domains will be usable in precisely the same way as polynomial rings. (Of course, we could use univariate polynomial rings before, but the smith normal form method should be faster. And we can use Z and its quotients now.)

I will implement basic operations for vector spaces similarly (using gaussian elimination algorithm from matrices instead of the smith normal form one).

Next, I will add a domain for free finite algebras. Essentially this means to take a ring R, a free (finitely generated) R-module F, and a finite, linearly independent, multiplicatively closed subset S of the endomorphism ring of F containing the identity, i.e. a finite multiplicatively set of square matrices (of the same dimension) with entries in R. An element of our finite algebra is by definition an element of the span of S, multiplication being extended linearly. (This need not be a commutative ring.) This process is a very slight generalization of the following idea: we want an algebra with basis elements e_1, ..., e_n, and each multiplication e_i e_j can be expressed as a linear combination of the e_k. Collecting coefficients together, we get a set S of n nxn matrices, which we can plug in the above process, and get an algebra isomorphic to the one we desired (but sometimes it can be possible to represent the algebra more efficiently than via the regular representation just described).

The class for finite algebras will do very little more than store the set S and provide an element class which behaves just like any other ring element class. Also, there will be a method to compute enveloping algebra. Next, I will implement basic operations for modules over such finite algebras. This is not as crazy as it may sound -- the category of modules over a non-commutative ring is still abelian, so that we can theoretically expect it to behave very much like our other module categories, and it is clear that in practice, everything can be reduced to computations with R-modules.

Then I will implement classes for working with chain complexes (I actually already have some code for this). For us, chain complex is a set of modules M_i indexed by non-negative integers i, together with homomorphism M_i -> M_{i-1}, such that the composite of any two such morphisms is zero. Typical uses are free resolutions. Here, one starts with some module M_0, then computes another module M_1 surjecting onto M_0, then one surjecting onto the kernel, and so on. This illustrates a number of points: (1) the complex need not be bounded, (2) computing some term of the complex may require computing all preceeding terms, (3) the computations can be very costly [every kernel computation is in principle a groebner basis computation, although there are very clever algorithms nowadays for computing free resolutions]. The chain complex class is designed to be versatile. As everywhere throughout agca, there is an abstract base class, which provides convenience interfaces on core methods. In the case of chain complexes, the core methods are of course those for computing the ith module and homorphism. The convenience methods mainly focus on printing and homology. The abstract base class also handles caching etc.

Once implemented, given any module M, calling M.free_resolution() will return a chain complex representing a free resolution. Printing will usually display the first two terms, but no more computations will be done. As always, different concrete classes can implement free_resolution in different ways. Actually syzygy_module is a core method, and free_resolution can be implemented in terms of it. In general we cannot do much better, but for example polyoomial rings may wish to implement specialised algorithms. Also over PIDs, there is always a two-term free resolution, which can be written down directly, so we don't have to deal with a potentially infinite resolution. Similarly, over a finite free enveloping algebra A (x) A^{op} (actually flat suffices), the so-called standard (or bar) resolution of the bimodule A can be written down directly, and no computations need to be performed for that (it is however an infinite resolution). Similarly for trivial actions of augmented algebras (e.g. group algebras), and so on.

Finally, I will be implementing classes for functors and derived functors, and the functors Tensor and Hom. In principle, a functor just associates to every module another module, and to every homomorphism another homomorphism (satisfying certain axioms). If the functor is right exact (such es tensor, or contravariant hom), then its derived functors are computed by replacing the argument by a free resolution, applying the functor, and taking homology. However, there are some extra properties: the functors one usually deals with do not usually "come from thin air". For example, the Tensor product of two modules M and N does characteristically come with a bilinear map from MxN, and the Hom module relates to homomorphisms. Also, the derived functors additionally come with natural transformations between them, expressing the bonudary maps.

So I think there should be a base class Functor, which has very little content (except for delegating the * operator to a composition funtcor implementation), but provides an interface contract: the name of the functor, the variance, exactness properties, domain ring A and target ring B (so that the functor maps A-modules to B-modules). Then, there would be concrete implementations: ComposedFunctor, TensorFunctor, HomFunctor (of course the tensor and hom functors are actually bifunctors, but it seems sufficient to just provide left and right versions for starters), LeftDerivedFunctor. Each of these subclasses can implement additional special methods (e.g. for accessing the boundary maps corresponding to an exact sequence). Note that since all modules we are working with are explicitly presented, computing Hom and Tensor is fairly easy.

For example, if M, N are modules, one can compute Tor_1(M,N) via LeftDerivedFunctor(TensorFunctor(M), 1)(N). This will return the tor module as as ordinary quotient module, which can then be analyzed by whatever means are implemented over this ground ring. Note that this is not aiming to supplant the category theory module. The language of functors will only be used to the extent that it is useful for expressing the computation. As such the focus will not be on "being able to express everything functors where made for", but rather on implementing concrete functors.

Tentative schedule

In my experience, estimating a schedule for software projects is next to impossible. So the following is very tentative.

  • weeks 1 and 2 basic operations on vector spaces, smith normal form algorithm, euclidean domain implementations (4 PRs)
  • week 3 basic operations over PIDs (2 PRs)
  • week 4 finite algebras, group algebras (2 PRs)
  • week 5 basic operations over finite algebras (2 PRs)
  • weeks 6 and 7 chain complexes and resolutions (3 PRs)
  • weeks 8 to 10 functors and derived functors, group and hochschild homology and cohomology (5 PRs)

This accounts for most of the GSOC period. Being an optimist, I would hope to be quicker than that. If so, I would spend the rest of the time on graded modules, or perhaps advanced operations. (A good reference for advanced and basic operations is "A singular introduction to commutative algebra".)

Add a custom footer
Add a custom sidebar
Clone this wiki locally