Topology software for Sage

[Simon King]

Dear sage developers,

some people, including myself, believe that Sage should contain more
tools for topology. E.g., there was a thread
http://groups.google.com/group/sage-devel/browse_thread/thread/5bd11c7e9fe08e4c/6ba64c41dd86770e?lnk=gst&q=simplicial+complexes#6ba64c41dd86770e
about simplicial complexes and their homology.

John Palmieri has sent a post to some algebraic topology list (https://
lists.lehigh.edu/mailman/listinfo/algtop-l), pointed the people to
Sage and asked for contribution. Thank you, John!

Being subscriber of that list, I added that one way to contribute is
to point us to existing software packages. So far, there was one
answer (concerning "plex", see below).

My question: How should the work on inclusion of topology software be
organized? Should one open a single trac ticket (essentially
complaining that there is not enough topology around), on which
suggestions for inclusions are collected? Or should the collection be
on this thread, with one separate ticket for each suggestion?

Here are three suggestions:
1. Simplicial complexes / Homology (see thread above)
I asked Frank Lutz, and he said that Polymake had a module 'topaz'
that can compute homology. However, in a recent Polymake upgrade,
topaz was removed from the distribution, due to some compiler problem.
So, it might make sense to wait for on upgrade of topaz.

2. SnapPea
SnapPea is a program for creating and studying hyperbolic 3-manifolds
(http://www.geometrygames.org/SnapPea-old/index.html). It seems to be
widely used by computational topologists. AFAIK it can deal with ideal
triangulations, compute volume, has a census of hyperbolic manifolds,
can also work with hyperbolic knots, etc.
If I understand correctly, it is under GNU GPL and may be used as a
Python module.

3. Plex (suggestion of Ryan Lewis from the above-mentioned topology
list)
Plex is a software package for computing persistent homology of finite
simplicial complexes, often generated from point cloud data (http://
comptop.stanford.edu/programs/jplex/index.html).

4. I found a link to a list of topology related software:
http://www.math.uiuc.edu/~nmd/computop/
Some of these might be interesting.

I am not sure if Plex really is an option for Sage. Previous versions
were written for Matlab. The current version is written in Java and
can also run in a standalone mode, using an integrated Java
interpreter, called Beanshell. Dunno if that works for Sage.

Cheers,
Simon

[William Stein]

On Wed, Feb 11, 2009 at 6:52 AM, Simon King <ki...@mathematik.uni-jena.de> wrote:
>
> Dear sage developers,
>
> some people, including myself, believe that Sage should contain more
> tools for topology. E.g., there was a thread
> http://groups.google.com/group/sage-devel/browse_thread/thread/5bd11c7e9fe08e4c/6ba64c41dd86770e?lnk=gst&q=simplicial+complexes#6ba64c41dd86770e
> about simplicial complexes and their homology.
>
> John Palmieri has sent a post to some algebraic topology list (https://
> lists.lehigh.edu/mailman/listinfo/algtop-l), pointed the people to
> Sage and asked for contribution. Thank you, John!

I very much hope Algebraic Topology will be a theme at Sage Days 15:

http://wiki.sagemath.org/days15

Simon -- any chance you will be able to go to that?

> Being subscriber of that list, I added that one way to contribute is
> to point us to existing software packages. So far, there was one
> answer (concerning "plex", see below).
>
> My question: How should the work on inclusion of topology software be
> organized? Should one open a single trac ticket (essentially
> complaining that there is not enough topology around), on which
> suggestions for inclusions are collected?

No! A wiki.sagemath.org page and email discussion would be much
better for that.

> Or should the collection be
> on this thread, with one separate ticket for each suggestion?

Yes.

> Here are three suggestions:
> 1. Simplicial complexes / Homology (see thread above)
> I asked Frank Lutz, and he said that Polymake had a module 'topaz'
> that can compute homology. However, in a recent Polymake upgrade,
> topaz was removed from the distribution, due to some compiler problem.
> So, it might make sense to wait for on upgrade of topaz.
>
> 2. SnapPea
> SnapPea is a program for creating and studying hyperbolic 3-manifolds
> (http://www.geometrygames.org/SnapPea-old/index.html). It seems to be
> widely used by computational topologists. AFAIK it can deal with ideal
> triangulations, compute volume, has a census of hyperbolic manifolds,
> can also work with hyperbolic knots, etc.
> If I understand correctly, it is under GNU GPL and may be used as a
> Python module.

A longtime Sage user -- Nathan Dunfield -- I think wrote the Python
interface, and uses SnapPea from Sage for his research.

> 3. Plex (suggestion of Ryan Lewis from the above-mentioned topology
> list)
> Plex is a software package for computing persistent homology of finite
> simplicial complexes, often generated from point cloud data (http://
> comptop.stanford.edu/programs/jplex/index.html).
>
> 4. I found a link to a list of topology related software:
> http://www.math.uiuc.edu/~nmd/computop/
> Some of these might be interesting.
>
> I am not sure if Plex really is an option for Sage. Previous versions
> were written for Matlab. The current version is written in Java and
> can also run in a standalone mode, using an integrated Java
> interpreter, called Beanshell. Dunno if that works for Sage.

It's an option as an optional package. I doubt it will be standard,
but I doubt anything big will be added to standard sage anytime _this_
year due to porting being the number one goal. But that shouldn't
stop anybody from writing good interfaces between Sage and other
software. There's no a priori reason that there shouldn't be an
excellent Sage <--> X interface for all math software X.

-- William

[David Roe]

I very much hope Algebraic Topology will be a theme at Sage Days 15:

http://wiki.sagemath.org/days15

I would like to work on Algebraic Topology at SD15.  I'm talking to some topologists here at Harvard next week to see what they would like to see in Sage.
David

[mabshoff]

On Feb 11, 9:45 am, William Stein <wst...@gmail.com> wrote:
> On Wed, Feb 11, 2009 at 6:52 AM, Simon King <k...@mathematik.uni-jena.de> wrote:

Hi,

> > Dear sage developers,
>
> > some people, including myself, believe that Sage should contain more
> > tools for topology. E.g., there was a thread

> >http://groups.google.com/group/sage-devel/browse_thread/thread/5bd11c...

> > about simplicial complexes and their homology.
>
> > John Palmieri has sent a post to some algebraic topology list (https://
> > lists.lehigh.edu/mailman/listinfo/algtop-l), pointed the people to
> > Sage and asked for contribution. Thank you, John!
>
> I very much hope Algebraic Topology will be a theme at Sage Days 15:
>
> http://wiki.sagemath.org/days15
>
> Simon -- any chance you will be able to go to that?
>
> > Being subscriber of that list, I added that one way to contribute is
> > to point us to existing software packages. So far, there was one
> > answer (concerning "plex", see below).
>
> > My question: How should the work on inclusion of topology software be
> > organized? Should one open a single trac ticket (essentially
> > complaining that there is not enough topology around), on which
> > suggestions for inclusions are collected?
>
> No!  A wiki.sagemath.org page and email discussion would be much
> better for that.

Yes, and any spkg would need to make the journey from experimental to
optional to finally standard in case they are portable and voted in.

> >  Or should the collection be
> > on this thread, with one separate ticket for each suggestion?
>
> Yes.

Well, without an spkg don't open a ticket.

> > Here are three suggestions:
> >  1. Simplicial complexes / Homology (see thread above)
> > I asked Frank Lutz, and he said that Polymake had a module 'topaz'
> > that can compute homology. However, in a recent Polymake upgrade,
> > topaz was removed from the distribution, due to some compiler problem.
> > So, it might make sense to wait for on upgrade of topaz.

Polymake does not have a chance to become standard in Sage as long as
they use C++ template meta programming (it is code that compiles quite
a long time) and they keep on with theit plan to build future releases
on something that runs via a shared memory interface to Perl. The code
is just not portable and after some discussion last year pointing out
various problems with that approach I don't see the developers
changing their minds on that.

Well, the main problem is not that we are porting Sage, the main
problem is that any piece of software out there does not work out of
the box on the platforms we want it to and in most cases upstream is
content with the platform support that they have. Often enough their
build systems have issues that need to be fixed to bring it up to the
standard we want in Sage.

> But that shouldn't
> stop anybody from writing good interfaces between Sage and other
> software. There's no a priori reason that there shouldn't be an
> excellent Sage <--> X interface for all math software X.

+1

>  -- William

Cheers,

Michael

[David Joyner]

On Wed, Feb 11, 2009 at 12:45 PM, William Stein <wst...@gmail.com> wrote:
>

...

> I very much hope Algebraic Topology will be a theme at Sage Days 15:
>
> http://wiki.sagemath.org/days15
>

1) Thanks very much for making SD15 on those dates!

2) I wonder if imaging/graphics could also be a theme?
That would be consistent with topology since visualization tools are
involved. On the other hand, I'm not an expert in that
field but it is interesting and I think Marshall is also interested
in that.



...

>
> -- William
>
> >
>

[Nathan Dunfield]

> >  2. SnapPea
> > SnapPea is a program for creating and studying hyperbolic 3-manifolds
> > (http://www.geometrygames.org/SnapPea-old/index.html). It seems to be
> > widely used by computational topologists. AFAIK it can deal with ideal
> > triangulations, compute volume, has a census of hyperbolic manifolds,
> > can also work with hyperbolic knots, etc.
> > If I understand correctly, it is under GNU GPL and may be used as a
> > Python module.
>
> A longtime Sage user -- Nathan Dunfield -- I think wrote the Python
> interface, and uses SnapPea from Sage for his research.

Actually, most of the current Python interface was written by Jeff
Weeks, the author of SnapPea itself. The most recent version is
available here:

http://www.math.uic.edu/~t3m/

However, Marc Culler and I are working on a new interface making use
of Cython. It works with vanilla Python but includes some Sage-
specific features, in particular using GAP, Pari, and Magma (when
available) to do the algebraic heavy-lifting when finding finite
covers and computing homology (which boils down to finding the smith
normal form).
----
There is also a modified version of SnapPea called Snap:

http://snap-pari.sourceforge.net/

which uses the Pari C-library to compute arithmetic invariants of
hyperbolic 3-manifolds. If one were writing it today, one would no
doubt use Sage instead. Indeed, I implemented the most basic features
of Snap in just a few pages of Sage code as a proof of concept.
-----
Some examples of using SnapPea and Sage together can be found at

http://dunfield.info/fibered-faces/

which is a computational supplement to my paper with Dinakar
Ramakrishnan:

http://arxiv.org/abs/0712.3243

Best,

Nathan

[mabshoff]

On Feb 11, 10:20 am, Nathan Dunfield <nat...@dunfield.info> wrote:

Hi,

Ok.

> -----
> Some examples of using SnapPea and Sage together can be found at
>
> http://dunfield.info/fibered-faces/
>
> which is a computational supplement to my paper with Dinakar
> Ramakrishnan:
>
> http://arxiv.org/abs/0712.3243
>
> Best,
>
> Nathan

Having glanced at the other projects this one seems to be the most
promising, but it certainly seems rather strange regarding build
system and so on. I.e. I did not see any obvious way to build the
kernel as a library for example. There is no meaningful documentation,
but a longer worded version of RTFS :). So I did poke around in the
makefile and build some project foo I made up. Compilation of the 3.0
release instantly failed because a 4 line comment was in
fundamental_group.c:

gcc -c -g -Wall -Wstrict-prototypes -Wmissing-prototypes -Wmissing-
declarations -I/Users/michaelabshoff/Desktop/foo/SnapPea/
SnapPeaKernel/headers/ -I/Users/michaelabshoff/Desktop/foo/SnapPea/
SnapPeaKernel/unix_kit/ foo.c
mkdir -p KernelObjects
cd KernelObjects; \
date > BuildDate; \
gcc -c -g -Wall -Wstrict-prototypes -Wmissing-prototypes -Wmissing-
declarations -I/Users/michaelabshoff/Desktop/foo/SnapPea/
SnapPeaKernel/headers/ -I/Users/michaelabshoff/Desktop/foo/SnapPea/
SnapPeaKernel/unix_kit/ \
/Users/michaelabshoff/Desktop/foo/SnapPea/SnapPeaKernel/code/
*.c \
/Users/michaelabshoff/Desktop/foo/SnapPea/SnapPeaKernel/unix_kit/
unix_UI.c \
/Users/michaelabshoff/Desktop/foo/SnapPea/SnapPeaKernel/unix_kit/
unix_cusped_census.c \
/Users/michaelabshoff/Desktop/foo/SnapPea/SnapPeaKernel/unix_kit/
unix_file_io.c
/Users/michaelabshoff/Desktop/foo/SnapPea/SnapPeaKernel/code/
fundamental_group.c: In function ‘simplify’:
/Users/michaelabshoff/Desktop/foo/SnapPea/SnapPeaKernel/code/
fundamental_group.c:1367: error: ‘This’ undeclared (first use in this
function)
/Users/michaelabshoff/Desktop/foo/SnapPea/SnapPeaKernel/code/
fundamental_group.c:1367: error: (Each undeclared identifier is
reported only once
/Users/michaelabshoff/Desktop/foo/SnapPea/SnapPeaKernel/code/
fundamental_group.c:1367: error: for each function it appears in.)
/Users/michaelabshoff/Desktop/foo/SnapPea/SnapPeaKernel/code/
fundamental_group.c:1367: error: syntax error before ‘call’

After commenting this comment out it actually compiled the unix_kit on
OSX, but never the kernel. I could not find any documentation or
anything resembling a Makefile for the kernel, but the website
eventually lead me to a file called MAKEFILE in the Python directory.
One would obviously build the kernel as a static or dynamic lib from
inside the kernel directory.

After fixing all those various small issues the final link stage blows
up since we do not actually link any libpython2.5.a into the shared
library (and the flags are all wrong, etc):

gcc -shared -o SnapPeaC.so -m64 -g -Wall -Wstrict-prototypes -Wmissing-
prototypes -Wmissing-declarations \
SnapPeaC.o \
KernelObjects/*.o \
-lm
<BOOM>

In any case: Besides the obvious build system cleanup required for
this to stand a chance to become standard in Sage the licenses has the
be clear. Currently I see

* SnapPea 2.0 was funded by the University of Minnesota's
* Geometry Center and the U.S. National Science Foundation.
* SnapPea 3.0 is funded by the U.S. National Science Foundation
* and the MacArthur Foundation. SnapPea and its source code may
* be used freely for all noncommercial purposes. Please direct
* questions, problems and suggestions to Jeff Weeks
* (www.geometrygames.org/contact.html).

If that is the case and the license still forbids commercial use there
is no chance this code will ever make it into standard Sage. It is
also worrisome that the last dated release (3.0d3) was dates in 2000.

Cheers,

Michael

[mhampton]

I am defintely hoping to make it to SD15, I think those dates work for
me. Not counting the joint meetings, which is more about PR, I have
never been to a Sage Days so I am really looking forward to it.

I have some interest in adding support for some topology-related
things for dynamical systems, like Chomp. That would be a great time
for me to get started. Visualization is also fun, I would be happy to
work on something with that perhaps.

Marshall

[Nathan Dunfield]

> Having glanced at the other projects this one seems to be the most
> promising, but it certainly seems rather strange regarding build
> system and so on. I.e. I did not see any obvious way to build the
> kernel as a library for example. There is no meaningful documentation,
> but a longer worded version of RTFS :).  So I did poke around in the
> makefile and build some project foo I made up. Compilation of the 3.0
> release instantly failed because a 4 line comment was in
> fundamental_group.c:

Michael,

It sounds like you're using the version from GeometryGames.org:

http://www.geometrygames.org/SnapPea-old/SnapPea3.html

This has been superseded by the version at

www.math.uic.edu/~t3m/

One of the things that Marc and I fixed was the build system, so the
latter should compile in the usual pythonic way

cd SnapPeaPython/
sage -python setup.py build
sage -python setup.py install

at least on Unix-type operating systems. Let me know if it doesn't
work for you.

> In any case: Besides the obvious build system cleanup required for
> this to stand a chance to become standard in Sage the licenses has the
> be clear. Currently I see
>

> [...]

>
> If that is the case and the license still forbids commercial use there
> is no chance this code will ever make it into standard Sage. It is
> also worrisome that the last dated release (3.0d3) was dates in 2000.

Jeff later relicensed the code under GPL 2+. He continues to fix
bugs in the kernel, and Marc and I continue to make small tweaks to
the Python interface (most recently in July of 2008, according to
CVS).

As I mentioned, Marc and I have a new version of the Python interface
using Cython which should be a lot easier to maintain. We hope to
have it up on web shortly, but for now you can grab a copy at

http://math.uic.edu/~t3m/SnapPy.tgz

This is called SnapPy instead of SnapPea since it's not backward
compatible.

Best,

Nathan

[mabshoff]

On Feb 11, 12:05 pm, Nathan Dunfield <nat...@dunfield.info> wrote:

<SNIP>

> Michael,

Hi Nathan,

> It sounds like you're using the version from GeometryGames.org:
>
> http://www.geometrygames.org/SnapPea-old/SnapPea3.html

Yes, that is the URL given by Simon and I did not read your email
after I had send mine since I had spend a good half our on the website
and with the code. As you noticed I wasn't impressed, but it sounds
like the new code should be much better.

Note that nowhere on the old website I could find a link to the new
code (if it is there, I must have overlooked it, so my apologies
then).

> This has been superseded by the version at
>
> www.math.uic.edu/~t3m/
>
> One of the things that Marc and I fixed was the build system, so the
> latter should compile in the usual pythonic way
>
> cd SnapPeaPython/
> sage -python setup.py build
> sage -python setup.py install
>
> at least on Unix-type operating systems.  Let me know if it doesn't
> work for you.

Good, I will try on some Unixy systems as time permits. Looking at the
C code itself it seems to be fairly clean, i.e. sooner or later I will
try with MSVC.

The build system was the biggest problem (besides the license) and my
suggestion would have been to use distutils, which apparently you do.
I am downloading the new tarball to play with it, so I should give you
some feedback in case I run into problems.

> > In any case: Besides the obvious build system cleanup required for
> > this to stand a chance to become standard in Sage the licenses has the
> > be clear. Currently I see
>
> > [...]
>
> > If that is the case and the license still forbids commercial use there
> > is no chance this code will ever make it into standard Sage. It is
> > also worrisome that the last dated release (3.0d3) was dates in 2000.
>
> Jeff later relicensed the code under GPL 2+.   He continues to fix
> bugs in the kernel, and Marc and I continue to make small tweaks to
> the Python interface (most recently in July of 2008, according to
> CVS).

Good, I saw a 3.0d4 binary for OSX 10.4 on the old website which
stated that it was GPL, but I could not find any sources which
actually said so.

> As I mentioned, Marc and I have a new version of the Python interface
> using Cython which should be a lot easier to maintain.  We hope to
> have it up on web shortly, but for now you can grab a copy at
>
> http://math.uic.edu/~t3m/SnapPy.tgz
>
> This is called SnapPy instead of SnapPea since it's not backward
> compatible.

Excellent. I like Cython interfaces a whole lot more than pexpect
interfaces :)

> Best,
>
> Nathan

Cheers,

Michael

[John H Palmieri]

Hi Simon,

On Feb 11, 6:52 am, Simon King <k...@mathematik.uni-jena.de> wrote:
> Dear sage developers,
>
> some people, including myself, believe that Sage should contain more

> tools for topology. E.g., there was a threadhttp://groups.google.com/group/sage-devel/browse_thread/thread/5bd11c...

> about simplicial complexes and their homology.
>
> John Palmieri has sent a post to some algebraic topology list (https://
> lists.lehigh.edu/mailman/listinfo/algtop-l), pointed the people to
> Sage and asked for contribution. Thank you, John!
>
> Being subscriber of that list, I added that one way to contribute is
> to point us to existing software packages.

This was a good point; thank you for bringing it up.

> Here are three suggestions:
> 1. Simplicial complexes / Homology (see thread above)
> I asked Frank Lutz, and he said that Polymake had a module 'topaz'
> that can compute homology. However, in a recent Polymake upgrade,
> topaz was removed from the distribution, due to some compiler problem.
> So, it might make sense to wait for on upgrade of topaz.

I have a package pretty much ready for inclusion into Sage: see
<http://sage.math.washington.edu/home/palmieri/homology.patch>. (I'll
open up a trac ticket for it in a week or two.) I can see at least
two directions to go (e.g. at Sage Days 15): clean up and speed up
this code, and/or work on incorporating Polymake/topaz or one of the
other packages out there which does simplicial homology.

> 4. I found a link to a list of topology related software:http://www.math.uiuc.edu/~nmd/computop/
> Some of these might be interesting.

I agree.

Another direction: compute Ext groups over connected algebras,
especially Ext over the Steenrod algebra, since this is the E_2-term
of the Adams spectral sequence. Bob Bruner has C code which does
this, and he is very interested in porting it to Sage or writing an
interface between it and Sage.

John

[David Roe]

Another direction: compute Ext groups over connected algebras,
especially Ext over the Steenrod algebra, since this is the E_2-term
of the Adams spectral sequence.  Bob Bruner has C code which does
this, and he is very interested in porting it to Sage or writing an
interface between it and Sage.

I'm talking to Mike Hopkins about algebraic topology in Sage next week, and I think this is one of the things he would like to see happen.  If anyone's interested in thinking about good ways to incorporate it, let me know.  I don't know much about the package yet, but I'll probably learn some next week.
David

[Simon King]

Hi!

On Feb 11, 6:45 pm, William Stein <wst...@gmail.com> wrote:

> On Wed, Feb 11, 2009 at 6:52 AM, Simon King <k...@mathematik.uni-jena.de> wrote:
> > My question: How should the work on inclusion of topology software be
> > organized? Should one open a single trac ticket (essentially
> > complaining that there is not enough topology around), on which
> > suggestions for inclusions are collected?
>
> No! A wiki.sagemath.org page and email discussion would be much
> better for that.

I've created a Wiki page at http://wiki.sagemath.org/topology

Note that on the Wiki I can not express the fact that certain Java
applets of Moira Chas can compute the Goldman pairing: The word 'Gold'
is prohibited...

The informations on that page are quite basic. My intention was to
provide pointers, so that people can try and see what packages are
worth looking at. I hope Nathan is not upset that in some cases I
copied from his list at http://www.math.uiuc.edu/~nmd/computop/

I thought I'd start with a list that is probably too long. But I guess
that due to your comments some of the packages will be removed from
the list for whatever reason (license?), and so I hope that eventually
it will be short enough for being worked through at some Sage Day.

Admittedly I don't know all of the programs, and certainly my
suggestions are influenced by the fact that I started as a low-
dimensional topologist and switched to cohomology computations. Sorry
for being biased.

Cheers
Simon