Opened 9 years ago

Last modified 3 years ago

#11559 needs_work enhancement

Speed up Posets and toric Chow group

Reported by: vbraun Owned by:
Priority: major Milestone: sage-7.1
Component: algebraic geometry Keywords: toric, sd40.5
Cc: sage-combinat Merged in:
Authors: Volker Braun Reviewers: Andrey Novoseltsev, Jan Keitel
Report Upstream: N/A Work issues:
Branch: u/chapoton/11559 (Commits) Commit: a16336e08c9f967a5e1106406329f44b899261ee
Dependencies: Stopgaps:

Description (last modified by chapoton)

To my surprise, computing the Chow group spends most of the time comparing cones instead of doing linear algebra. 3/4 of the time is spent in PosetElement.__eq__():

   return self.parent() == other.parent() \
          and self.element == other.element \
          and self.vertex == other.vertex

Reordering this to first compare self.vertex == other.vertex speeds it up dramatically.

Patch has some other fixes. Changes the Chow group to use sparse matrices.

Attachments (4)

trac_11559_fix_Chow_group.patch (2.8 KB) - added by vbraun 9 years ago.
Updated patch
trac_11559_fix_Chow_group.2.patch (2.5 KB) - added by novoselt 8 years ago.
Rebased for Sage-5.1.beta0
trac_11559_hasattr_vertex_fc.patch (936 bytes) - added by chapoton 7 years ago.
trac_11559_fixdoctest.patch (3.5 KB) - added by chapoton 6 years ago.

Download all attachments as: .zip

Change History (40)

Changed 9 years ago by vbraun

Updated patch

comment:1 Changed 9 years ago by novoselt

  • Reviewers set to Andrey Novoseltsev

Can you clarify why hermit_form was replaced with echelon_form?

Also I don't like the very last change with forceful passing of check=False to the parent constructor. I think the correct way is to always pass whatever was received from the user and if it leads to a slowdown somewhere, then in that somewhere one should use check=False.

comment:2 Changed 9 years ago by rbeezer

I took a look at this earlier, so I'll add my 2 cents worth.

hermite_form is a straight replacement for echelon_form. Now that we have a rref command to obtain results over fields, I personally think it would be nice if "hermite form" went away, I think it confuses too many non-specialists.

I was going to vouch for the posets and linear algebra, but I don't know the Chow group stuff, so it is good that Andrey is on this one.

Rob

comment:3 Changed 9 years ago by vbraun

hermite_form is an alias for echelon_form for dense ZZ-matrices. Sparse ZZ-matrices currently don't have a hermite_form method, though I'll add that back in #11558.

I'm passing check=False to the element constructor because the input for the base constructor is computed. Usually when you extend some element class, you pass user-specified arguments through to the base constructor and its necessary to check their validity. Though I didn't see it taking much time when benchmarking, so if you insist I'll be happy to take it out again.

comment:4 Changed 9 years ago by vbraun

  • Status changed from new to needs_review

comment:5 Changed 9 years ago by hivert

  • Owner changed from AlexGhitza to (none)

What kind of parents are you using. Normally they should be unique so that parent comparisons should be done with is and thus instantaneous. Moreover, I don't think your solution is correct because in some case you will end up comparing things where eq will simply break. I'll try to cook an example.

Florent

comment:6 Changed 9 years ago by hivert

  • Cc sage-combinat added

I should also mention that before touching anything in posets you should test you code with #10998 applied. There where a major rewrite in posets with a lot of speedups and cleanups.

Florent

comment:7 Changed 9 years ago by vbraun

I agree that parents should be unique. The original code compared parents with == and I didn't change it.

My point is that the PosetElement.element comparison is potentially slow. In fact, I don't understand why PosetElement.__eq__ compares both vertex and element, I am under the impression that there is a bijection between vertices and elements.

The reordering does break comparison between PosetElements and other classes, though I'm not sure if we care. The patch does conflict with #10998, so that one needs to be reviewed first.

comment:8 Changed 9 years ago by novoselt

  • Dependencies changed from #11558 to #11558, #10998

comment:9 Changed 8 years ago by slabbe

Same lines are edited by #12351. One will have to adapt to the other one.

comment:10 follow-up: Changed 8 years ago by novoselt

  • Status changed from needs_review to needs_work

Does not apply on Sage-5.0.beta4!

comment:11 in reply to: ↑ 10 Changed 8 years ago by nthiery

Replying to novoselt:

Does not apply on Sage-5.0.beta4!

If it's the hunk in the poset code that fails, that's normal. #10998 already integrates this change (in fact a slightly better one).

comment:12 Changed 8 years ago by novoselt

  • Work issues set to rebasing

comment:13 Changed 8 years ago by novoselt

  • Status changed from needs_work to needs_review
  • Work issues rebasing deleted

Hey Volker,

Changing posets to compare again vertices first still shaves off a second on testing Chow group module - do you have an example where it used to be crucial? In any case if you are fine with my rebasing let's merge it!

comment:14 Changed 8 years ago by novoselt

  • Dependencies changed from #11558, #10998 to #11558, #10998, #13023
  • Keywords toric sd40.5 added

Changed 8 years ago by novoselt

Rebased for Sage-5.1.beta0

comment:15 Changed 8 years ago by novoselt

Now works fine after file move.

Changed 7 years ago by chapoton

comment:16 Changed 7 years ago by chapoton

  • Description modified (diff)

for the bot:

apply trac_11559_fix_Chow_group.2.patch trac_11559_hasattr_vertex_fc.patch

If you do not want to check the parent first, you need to make sure that other has the attribute "vertex" !

This ticket needs benchmarking, to see if something significant is still gained in term of time or not.

comment:17 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

Changed 6 years ago by chapoton

comment:18 Changed 6 years ago by chapoton

  • Description modified (diff)

here a patch correcting the failing doctests

Apply trac_11559_fix_Chow_group.2.patch trac_11559_fixdoctest.patch trac_11559_hasattr_vertex_fc.patch

comment:19 Changed 6 years ago by nthiery

I just noticed this ticket. Has someone tried using have_same_parent(self, other) ?

comment:20 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:21 Changed 6 years ago by chapoton

  • Branch set to u/chapoton/11559
  • Commit set to ad1701157f4c051ac160c72b7e63ba7ad7aeb822

here is a git branch


New commits:

7437e82Trac #11559: Speed up Posets and toric Chow group
3322d7ctrac #11559 fixing failing doctests
ad17011trac 11559 check if other has attribute vertex

comment:22 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:23 Changed 6 years ago by pbruin

  • Status changed from needs_review to needs_work

From the patchbot report:

File "src/sage/geometry/fan.py", line 158, in sage.geometry.fan
Failed example:
    sorted(L.hasse_diagram().neighbors(cone))
Expected:
    [1-d cone of Rational polyhedral fan in 3-d lattice M,
     1-d cone of Rational polyhedral fan in 3-d lattice M,
     3-d cone of Rational polyhedral fan in 3-d lattice M,
     3-d cone of Rational polyhedral fan in 3-d lattice M]
Got:
    [1-d cone of Rational polyhedral fan in 3-d lattice M, 3-d cone of Rational polyhedral fan in 3-d lattice M, 3-d cone of Rational polyhedral fan in 3-d lattice M, 1-d cone of Rational polyhedral fan in 3-d lattice M]

comment:24 Changed 6 years ago by git

  • Commit changed from ad1701157f4c051ac160c72b7e63ba7ad7aeb822 to 6cd90ca42510ca957f59363321ef24074eef1e30

Branch pushed to git repo; I updated commit sha1. New commits:

860f696Merge branch 'u/chapoton/11559' of ssh://trac.sagemath.org:22/sage into 11559
6cd90catrac #11559 correct failing doctest

comment:25 Changed 6 years ago by chapoton

  • Status changed from needs_work to needs_review

comment:26 Changed 6 years ago by jkeitel

  • Branch changed from u/chapoton/11559 to u/jkeitel/11559
  • Commit changed from 6cd90ca42510ca957f59363321ef24074eef1e30 to 85a053daeadeb7a8d1de24e354cc6fc99068df7f
  • Reviewers changed from Andrey Novoseltsev to Andrey Novoseltsev, Jan Keitel
  • Status changed from needs_review to positive_review

Hi, the patch looks good to me and seems to make sensible changes. However, I can't tell whether the patch is actually bringing any speed benefits. Volker, Andrey, what exactly is it that should be benchmarked?


New commits:

85a053dNitpicking for 11559: Added a space

comment:27 Changed 6 years ago by jkeitel

  • Status changed from positive_review to needs_review

comment:28 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:29 Changed 5 years ago by chapoton

  • Milestone changed from sage-6.4 to sage-6.6

This ticket seems to confuse the patchbot. But maybe any ticket would..

comment:30 Changed 5 years ago by chapoton

  • Status changed from needs_review to needs_info

Put to need info just to stop the bots loop-testing this ticket.

comment:31 Changed 5 years ago by novoselt

Related or not - when I click on the branch name to see the differences, it shows the intent to DELETE TWO MODULES completely!!! I do not see commits that attempt to do it, however.

comment:32 Changed 5 years ago by chapoton

  • Branch changed from u/jkeitel/11559 to u/chapoton/11559
  • Commit changed from 85a053daeadeb7a8d1de24e354cc6fc99068df7f to b94f43d70821674c635b318d964ec22974abe961

New commits:

b94f43dMerge branch 'u/jkeitel/11559' of ssh://trac.sagemath.org:22/sage into 11559

comment:33 Changed 5 years ago by chapoton

  • Milestone changed from sage-6.6 to sage-6.7

comment:34 Changed 5 years ago by pbruin

  • Status changed from needs_info to needs_work

Some patchbots are still testing this ticket, but there are various doctest failures; setting this back to "needs_work".

comment:35 Changed 4 years ago by chapoton

  • Dependencies #11558, #10998, #13023 deleted
  • Description modified (diff)
  • Milestone changed from sage-6.7 to sage-7.1

comment:36 Changed 3 years ago by git

  • Commit changed from b94f43d70821674c635b318d964ec22974abe961 to a16336e08c9f967a5e1106406329f44b899261ee

Branch pushed to git repo; I updated commit sha1. New commits:

a16336eMerge branch 'u/chapoton/11559' in 8.1.b5
Note: See TracTickets for help on using tickets.