simplicial complexes, chain complexes, and their homology

[John H Palmieri]

I have a first draft of a module which implements simplicial
complexes, chain complexes, and their homology. It isn't perfect: it
is limited by Sage's abilities to deal with modules over arbitrary
commutative rings, or at least by my knowledge of Sage's abilities.
Thus for example, you can define a chain complex over a polynomial
ring on one or several variables, but you probably can't compute its
homology very reliably.

I would appreciate comments, and eventually I hope to submit it to the
trac server.

(I tried searching the various Sage groups to see if anyone was
working on similar stuff and didn't find anything. I hope I'm not
stepping on any toes.)

See the file 'http://sage.math.washington.edu/home/palmieri/
homology.patch' for more.

John

[William Stein]

On Sun, Jan 18, 2009 at 10:40 PM, John H Palmieri
<jhpalm...@gmail.com> wrote:
>
> I have a first draft of a module which implements simplicial
> complexes, chain complexes, and their homology. It isn't perfect: it
> is limited by Sage's abilities to deal with modules over arbitrary
> commutative rings, or at least by my knowledge of Sage's abilities.
> Thus for example, you can define a chain complex over a polynomial
> ring on one or several variables, but you probably can't compute its
> homology very reliably.
>
> I would appreciate comments, and eventually I hope to submit it to the
> trac server.
>
> (I tried searching the various Sage groups to see if anyone was
> working on similar stuff and didn't find anything. I hope I'm not
> stepping on any toes.)

If you are it is a surprise to me. The only time in my entire life
that I have heard of anybody implementing computation of generic
simplical homology in any math software system is right now from you.
I've never heard of anybody doing a single real thing in this
direction in Sage or Magma ever (I'm not saying nothing was done in
Magma, but I don't know about it). So I'm very enthusiastic about
this! I also think this is great motivation to finally implement
general finitely generated modules over ZZ, so, e.g., cokernels are
defined.

>
> See the file 'http://sage.math.washington.edu/home/palmieri/
> homology.patch' for more.
>
> John
>
>
> >
>

--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org

[Carlo Hamalainen]

On Mon, Jan 19, 2009 at 7:40 AM, John H Palmieri <jhpalm...@gmail.com> wrote:
> I have a first draft of a module which implements simplicial
> complexes, chain complexes, and their homology.

Cool!

Is there anything in CHomP that may be of use to you?

http://chomp.rutgers.edu/software/

It's GPL v2, mostly C++. It has programs for:

-------------
homchain - computes the homology groups over Z or Zp of a chain
complex, as well as the homomorphisms induced in homology by chain
maps

homcubes - computes the (relative) homology of a set of cubes or a
cubical set, as well as the homomorphism induced in homology by an
acyclic combinatorial cubical multivalued map

homsimpl - computes the homology of a finite abstract simplicial
complex or relative homology of a pair of simplicial complexes

indxpair - finds an index pair with Andrzej Szymczak's algorithm

homcub2l - computes the index map using double-layer cubical sets to
overcome the problem with excision, as introduced in a paper by P.
Pilarczyk and K. Stolot

chmap - constructs a chain selector of an almost perfect combinatorial
cubical multivalued map; this program was written by Marcin Mazur and
Jacek Szybowski (note: it does not support the common command-line
arguments listed above)

chom - computes homology of a cubical sets using a geometric reduction
approach; this program was written by Bill Kalies (note: it does not
support the common command-line arguments listed above)

chomp - computes homology of cubical sets using one of the
bitmap-based homology computation algorithms developped recently by
Marian Mrozek; the program is capable of reading data in a variety of
input formats, and it allows to use multiple homology computation
engines, including the ones implemented in homcubes and chom
-------------

Hope this helps.

--
Carlo Hamalainen
http://carlo-hamalainen.net

[David Joyner]

On Mon, Jan 19, 2009 at 1:40 AM, John H Palmieri <jhpalm...@gmail.com> wrote:
>
> I have a first draft of a module which implements simplicial
> complexes, chain complexes, and their homology. It isn't perfect: it
> is limited by Sage's abilities to deal with modules over arbitrary
> commutative rings, or at least by my knowledge of Sage's abilities.
> Thus for example, you can define a chain complex over a polynomial
> ring on one or several variables, but you probably can't compute its
> homology very reliably.
>
> I would appreciate comments, and eventually I hope to submit it to the
> trac server.
>
> (I tried searching the various Sage groups to see if anyone was
> working on similar stuff and didn't find anything. I hope I'm not
> stepping on any toes.)

You are not stepping on any toes AFAIK but doesn't the GAP package HAP
implement something like this? http://www.gap-system.org/Packages/hap.html
Maybe most of what he does requires a group action but there is this
example: http://hamilton.nuigalway.ie/Hap/www/SideLinks/About/aboutTensorSquare.html
(Not that I know a lot about the subject but isn't this the
kind of homology you are dealing with?) Anyway, he told me that there
are some resolutions which are "exponentially slow" and some which
are not so slow and I believe he has thought long and hard about
computing such things as quickly as possible. So it might be worth a look
if you don't know it already.

In any case, it's nice to have another version, especially in Python/Sage!

[mhampton]

It would be very cool to have CHomP in Sage. I think John's focus is
more on pure math, and my understanding of CHomP is that it is aimed
more at dynamical systems and symbolic-numeric applications, but there
is probably some overlap. At any rate, it would really help the
current state of dynamical systems in Sage which is almost non-
existent.

I have too many projects right now to try to spearhead that effort,
but I am interested and will be more qualified after some other things
happen - I need to learn more about interfaces to C and C++ libraries
in Sage. As the polyhedral code matures and I work on the phcpack
native port I should get a lot better at that. Anyway, if anyone
wants to start looking at CHomP I can at least help test and discuss.

Marshall Hampton

On Jan 19, 2:14 am, Carlo Hamalainen <carlo.hamalai...@gmail.com>
wrote:

[John H Palmieri]

On Jan 18, 10:46 pm, William Stein <wst...@gmail.com> wrote:
> On Sun, Jan 18, 2009 at 10:40 PM, John H Palmieri
>
>
>
> <jhpalmier...@gmail.com> wrote:
>
> > I have a first draft of a module which implements simplicial
> > complexes, chain complexes, and their homology.  It isn't perfect: it
> > is limited by Sage's abilities to deal with modules over arbitrary
> > commutative rings, or at least by my knowledge of Sage's abilities.
> > Thus for example, you can define a chain complex over a polynomial
> > ring on one or several variables, but you probably can't compute its
> > homology very reliably.
>
> > I would appreciate comments, and eventually I hope to submit it to the
> > trac server.
>
> > (I tried searching the various Sage groups to see if anyone was
> > working on similar stuff and didn't find anything.  I hope I'm not
> > stepping on any toes.)
>
> If you are it is a surprise to me.  The only time in my entire life
> that I have heard of anybody implementing computation of generic
> simplical homology in any math software system is right now from you.

Macaulay2 has this, although I've never used it (just looked at the
documentation and a little of the source code, which I found rather
opaque). See

<http://www.math.uiuc.edu/Macaulay2/doc/Macaulay2-1.1/share/doc/
Macaulay2/SimplicialComplexes/html/___Simplicial__Complex.htm>

> I've never heard of anybody doing a single real thing in this
> direction in Sage or Magma ever (I'm not saying nothing was done in
> Magma, but I don't know about it).   So I'm very enthusiastic about
> this!   I also think this is great motivation to finally implement
> general finitely generated modules over ZZ, so, e.g., cokernels are
> defined.

John

[John H Palmieri]

On Jan 19, 12:14 am, Carlo Hamalainen <carlo.hamalai...@gmail.com>
wrote:

> On Mon, Jan 19, 2009 at 7:40 AM, John H Palmieri <jhpalmier...@gmail.com> wrote:
>
> > I have a first draft of a module which implements simplicial
> > complexes, chain complexes, and their homology.
>
> Cool!
>
> Is there anything in CHomP that may be of use to you?
>
> http://chomp.rutgers.edu/software/

Thank you for pointing it out. It seems to focus on cubical homology
rather than simplicial, but I see a few simplicial computations in the
list you posted. I'll take a look. I'm sure my computations are not
very efficient, so having some outside help might be good.

John

[John H Palmieri]

On Jan 19, 5:44 am, David Joyner <wdjoy...@gmail.com> wrote:

> On Mon, Jan 19, 2009 at 1:40 AM, John H Palmieri <jhpalmier...@gmail.com> wrote:
>
> You are not stepping on any toes AFAIK but doesn't the GAP package HAP
> implement something like this?http://www.gap-system.org/Packages/hap.html

This does seem to do homology of chain complexes, but nothing about
simplicial complexes. There is also a different GAP package,

<http://linalg.org/gap.html>

but to install it you need the GNU Pascal compiler, and I decided that
I didn't want to install that.

> Maybe most of what he does requires a group action but there is this

> example:http://hamilton.nuigalway.ie/Hap/www/SideLinks/About/aboutTensorSquar...

> (Not that I know a lot about the subject but isn't this the
> kind of homology you are dealing with?) Anyway, he told me that there
> are some resolutions which are "exponentially slow" and some which
> are not so slow and I believe he has thought long and hard about
> computing such things as quickly as possible. So it might be worth a look
> if you don't know it already.

I think I'm doing things which are more naive: computing the homology
of a chain complex is simpler, conceptually, than computing the
homology of a specific space or group, because to do this you might be
able to first carefully choose a chain complex, then compute its
homology, and choosing the chain complex might require planning and
thought and things like that. But I'll take a look at this.

> In any case, it's nice to have another version, especially in Python/Sage!

John

[Robert Miller]

Magma also supports chain complexes:

http://magma.maths.usyd.edu.au/magma/htmlhelp/text625.htm

[Simon King]

Hi!

There seems to be an extension for Polymake that can compute
simplicial homology.

Quoted from http://www.math.tu-berlin.de/polymake/external.html
homology
by Frank Heckenbach, Uni Erlangen-Nürnberg
An efficient program computing homology groups of simplicial
complexes.

Unfortunately, the link that they give (apparently the home page of
Heckenbach) is broken.

Cheers,
Simon

[Michael Brickenstein]

I don't know the lib,
but there exists homolog.lib in Singular:
http://www.singular.uni-kl.de/Manual/latest/sing_763.htm#SEC822
(Link is assumed to break, when docs are updated)
Michael

[Simon King]

Hi Michael,

Michael Brickenstein schrieb:

I don't know much about that library either, but it seems to not
provide any tool to deal with simplicial complexes. Perhaps it can be
useful to implement something, though.

Frank Lutz did work on enumeration of triangulated manifolds, he did
compute cohomology, and as much as I know he relied on Polymake. So,
I'll ask him if he can give some advices.

Best regards,
Simon

[John H Palmieri]

Let me follow up on this discussion:

I looked at some papers on computing simplicial homology (including
what seems like a pretty nice one by Dumas, Heckenbach, Saunders, and
Welker, the authors of a GAP package for homology computations).
These papers are all focused on Smith normal form, which makes sense:
to compute simplicial homology, you need to compute the cokernel of a
(potentially large) integer matrix, and this appears to be the main
bottleneck. If you work with field coefficients, you just have to
compute the ranks of some matrices.

I'm using Sage's existing implementation of Smith normal form
(actually the elementary_divisors method, which claims to be faster).
Here is some timing on my iMac, with my current version of the files:

This is tested using the simplicial complex S = not_i_connected_graphs
(5,2), a simplicial complex which the four authors above used to test
their package. Its f-vector is [1, 10, 45, 120, 210, 240, 140, 20]:
it has 10 vertices, 45 edges, 120 triangles, ..., 20 6-dimensional
simplices. Its homology is trivial except in dimension 5, where it is
free abelian of rank 6.

S.homology(base_ring=QQ) takes 1.7 sec
S.homology(base_ring=ZZ) takes 56 sec (!)

But here's the thing: I have a different algorithm for simplicial
homology, which I have not seen mentioned in the literature, which
does the following:

S.homology(base_ring=QQ) takes 1.3 sec
S.homology(base_ring=ZZ) takes 1.33 sec (!!)

I think I ought to be able to squeeze some more speed out of it, too.
I'll keep working, and I'll post updated files soon.

John

On Jan 18, 10:40 pm, John H Palmieri <jhpalmier...@gmail.com> wrote:
> I have a first draft of a module which implements simplicial

> complexes, chain complexes, and their homology...

[John H Palmieri]

There is now a patch on the trac server implementing simplicial
complexes and their homology: <http://trac.sagemath.org/sage_trac/
ticket/5386>

John