Opened 6 years ago

Closed 4 years ago

#11523 closed enhancement (fixed)

Implementation of Cohen-Macaulay test for simplicial complexes

Reported by: stumpc5 Owned by: malb
Priority: major Milestone: sage-5.6
Component: commutative algebra Keywords: Cohen-Macaulay, homology, simplicial complexes
Cc: jhpalmieri Merged in: sage-5.6.beta2
Authors: Christian Stump Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12587 Stopgaps:

Description (last modified by tscrim)

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: trac_11523-cohen_macaulay_complex-cs-jhp-review-ts.patch

Attachments (1)

trac_11523-cohen_macaulay_complex-cs-jhp-review-ts.patch (6.4 KB) - added by tscrim 5 years ago.

Download all attachments as: .zip

Change History (19)

comment:1 Changed 6 years ago by stumpc5

  • Description modified (diff)

comment:2 Changed 6 years ago by stumpc5

  • Description modified (diff)

comment:3 follow-up: Changed 6 years ago by jhpalmieri

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.

comment:4 in reply to: ↑ 3 ; follow-up: Changed 6 years ago by stumpc5

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

comment:5 follow-up: Changed 6 years ago by stumpc5

  • Status changed from new to needs_review

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!

comment:6 in reply to: ↑ 5 Changed 6 years ago by stumpc5

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.

comment:7 follow-up: Changed 6 years ago by 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..."?

comment:8 in reply to: ↑ 7 Changed 6 years ago by stumpc5

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!

comment:9 Changed 5 years ago by jhpalmieri

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.

comment:10 follow-up: Changed 5 years ago by tscrim

Because of the hashing of simplicial complexes, this is in conflict with #12587. I've started a topic on sage-devel on the mutability of SimplicialComplex.

comment:11 in reply to: ↑ 10 Changed 5 years ago by stumpc5

Replying to tscrim:

Because of the hashing of simplicial complexes, this is in conflict with #12587. I've started a topic on sage-devel on the mutability of SimplicialComplex.

Thanks for bringing this up. I will modify this ticket here as soon as the other ticket is ready.

comment:12 Changed 5 years ago by tscrim

Hey Christian,

Just wondering about the status of this patch now that #12587 is (code-wise) finalized.

Thanks,
Travis

comment:13 Changed 5 years ago by stumpc5

Okay, this is now ready for its final review, I guess... Thanks Travis for bringing it up again!

comment:14 follow-up: Changed 5 years ago by tscrim

  • Dependencies set to #12587
  • Description modified (diff)
  • Reviewers set to Travis Scrimshaw

Hey Christian and John,

This did not apply against #12587, so I did the very minor rebase in my review patch (it contains the entire patch; sorry if I overstepped here). I also made some minor docstring changes: some formatting and moved the note about the exception in a .. NOTE:: block. If you agree with the changes, feel free to set this to positive review.

Thanks for your work on this, I plan on putting this to good use,
Travis

For patchbot:

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

comment:15 in reply to: ↑ 14 Changed 5 years ago by stumpc5

  • Status changed from needs_review to positive_review

Replying to tscrim:

Thanks for your work on this, I plan on putting this to good use,

great!

The patch looks good to me, so I am marking it positive...

Best, Christian

comment:16 Changed 5 years ago by jdemeyer

Is the work issue still relevant?

comment:17 in reply to: ↑ 4 Changed 5 years ago by tscrim

  • Work issues further improvement of _enlarge_subcomplex deleted

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.

It seems like it's not.

comment:18 Changed 4 years ago by jdemeyer

  • Merged in set to sage-5.6.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.