Implementation of Cohen-Macaulay test for simplicial complexes

[stumpc5]

Simplicial complexes were lacking a method to test Cohen-Macaulayness.

In order to implement this method, some other methods are improved, namely a hash function is implemented, and _enlarge_subcomplex has become faster.

For convinience, I also added a face_iterator.

Remark: the new line

int_facets = set( a.set().intersection(f_set) for a in new_facets ) 

in _enalarge_subcomplex improved speed for computing the homology by 65% (in the example I looked at -- needs to be verified). This method still has the potential to be speeded a lot, and it is responsible for a lot cpu time when computing the homology.

I also added a second version using parallel tests on multiple cpus.

---

Apply only: attachment: trac_11523-cohen_macaulay_complex-cs-jhp-review-ts.patch

Depends on #12587

CC: @jhpalmieri

Component: commutative algebra

Keywords: Cohen-Macaulay, homology, simplicial complexes

Author: Christian Stump

Reviewer: Travis Scrimshaw

Merged: sage-5.6.beta2

Issue created by migration from https://trac.sagemath.org/ticket/11523

[stumpc5]

Description changed:

--- 
+++ 
@@ -2,4 +2,12 @@
 
 In order to implement this method, some other methods are improved, namely a hash function is implemented, and _enlarge_subcomplex has become faster.
 
+For convinience, I also added a face_iterator.
 
+Remark: the new line
+
+```
+int_facets = set( a.set().intersection(f_set) for a in new_facets ) 
+```
+
+in _enalarge_subcomplex improved speed for computing the homology by 65%. This method still has the potential to be speeded a lot, and it is responsible for a lot cpu time when computing the homology.

[stumpc5]

Description changed:

--- 
+++ 
@@ -10,4 +10,6 @@
 int_facets = set( a.set().intersection(f_set) for a in new_facets ) 
 ```
 
-in _enalarge_subcomplex improved speed for computing the homology by 65%. This method still has the potential to be speeded a lot, and it is responsible for a lot cpu time when computing the homology.
+in _enalarge_subcomplex improved speed for computing the homology by 65% (in the example I looked at -- needs to be verified). This method still has the potential to be speeded a lot, and it is responsible for a lot cpu time when computing the homology.
+
+I also added a second version using parallel tests on multiple cpus.

[jhpalmieri]

comment:3

I'm sorry, I forgot about this ticket.

Overall, I think this looks pretty good. Some comments and questions:

• I had to rebase this against 4.7.2.alpha2.
• why have both is_cohen_macaulay and is_cohen_macaulay_parallel? When would you ever want to use the first one? With ncpus=1, the parallel one is about as fast as the first, so should we get rid of the first one?
• on the other hand, when I run the parallel version with ncpus=1, I sometimes see an error:

Exception OSError: (10, 'No child processes') in <generator object __call__ at 0x10d20ee10> ignored

and then the computation proceeds. Should we try to catch this and hide it? Can we do that if it says "ignored"?

• in my testing (timeit('simplicial_complexes.NotIConnectedGraphs(5,2).homology()')), I saw no change in the time required to do homology computations from the old version to the new one, but if you have other ideas for speeding things up, please implement them.
• the method face_iterator has no documentation.

I don't know if this was ready for review, but I'm attaching a new version of the patch which makes some of these changes: it renames is_cohen_macaulay to _is_cohen_macaulay_serial (so it's hidden), renames the parallel version to is_cohen_macaulay. I wonder if we should set ncpus to be 2 by default instead of 1? I'll try testing on a machine with just one cpu to see what effect that has.

[stumpc5]

comment:4

Replying to @jhpalmieri:

Thanks for looking at it again, I hope we can get it into sage soon, as it was pretty much done. The only reason why I stopped working was that I thought I can still speed things up, but I never found the time to do so. I vote for leaving it as it is for now, and if someone (maybe me) needs a faster version, we get back to it.

Overall, I think this looks pretty good. Some comments and questions:

• why have both is_cohen_macaulay and is_cohen_macaulay_parallel? When would you ever want to use the first one? With ncpus=1, the parallel one is about as fast as the first, so should we get rid of the first one?

that was just a left-over, as I first implemented is_cohen_macaulay and then started to play with the parallel version.

• on the other hand, when I run the parallel version with ncpus=1, I sometimes see an error:

Exception OSError: (10, 'No child processes') in <generator object __call__ at 0x10d20ee10> ignored

and then the computation proceeds. Should we try to catch this and hide it? Can we do that if it says "ignored"?

If I remember right, this happens not only for 1 cpu, but if a negative answer is returned without waiting the other parallel sessions to be finished. I agree that we should catch that error!

• in my testing (timeit('simplicial_complexes.NotIConnectedGraphs(5,2).homology()')), I saw no change in the time required to do homology computations from the old version to the new one, but if you have other ideas for speeding things up, please implement them.

See my comment at the beginning.

• the method face_iterator has no documentation.

I will add it!

I don't know if this was ready for review, but I'm attaching a new version of the patch which makes some of these changes: it renames is_cohen_macaulay to _is_cohen_macaulay_serial (so it's hidden), renames the parallel version to is_cohen_macaulay. I wonder if we should set ncpus to be 2 by default instead of 1? I'll try testing on a machine with just one cpu to see what effect that has.

Thanks again, I will update your patch as soon as I have done the changes...

Best, Christian

[stumpc5]

comment:5

I updated a new version. The only changes are that I import QQ as we need that, and I simplified the code for is_cohen_macaulay slightly. I saw that you added the documentation for face_iterator already, thanks!

[stumpc5]

comment:6

Replying to @stumpc5:

I updated a new version. The only changes are that I import QQ as we need that, and I simplified the code for is_cohen_macaulay slightly. I saw that you added the documentation for face_iterator already, thanks!

It is rebased against 4.7.2.alpha3.

[jhpalmieri]

comment:7

This is mostly good. The only problems are with the parallel version: if I run with more than one process, I get a message like

sage: X.is_cohen_macaulay(2)
Killing any remaining workers...
False

If I run it with one process, I get

sage: X.is_cohen_macaulay(1)
Killing any remaining workers...
Exception OSError: (10, 'No child processes') in <generator object __call__ at 0x10ca39a00> ignored
False

We should be able to catch the error. Can we also suppress the message "Killing any remaining workers..."?

[stumpc5]

comment:8

Replying to @jhpalmieri:

This is mostly good. The only problems are with the parallel version: if I run with more than one process, I get a message like

sage: X.is_cohen_macaulay(2)
Killing any remaining workers...
False

If I run it with one process, I get

sage: X.is_cohen_macaulay(1)
Killing any remaining workers...
Exception OSError: (10, 'No child processes') in <generator object __call__ at 0x10ca39a00> ignored
False

We should be able to catch the error. Can we also suppress the message "Killing any remaining workers..."?

I tried to catch it, but it it already caught somewhere inside the decorator, so I don't know how to suppress the output, do you?

Feel free to update the patch if you see a way to do it!

[jhpalmieri]

comment:9

I'm sorry this has languished for so long. Here is a new patch which turns off the message "Killing remaining workers...". I don't know how to get rid of the "No child processes warning", so I mentioned its possible presence in the docstring, so people won't be too concerned if they see it. I also removed the serial version altogether.