Speed up Posets and toric Chow group

[vbraun]

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.

CC: @sagetrac-sage-combinat

Component: algebraic geometry

Keywords: toric, sd40.5

Author: Volker Braun

Branch/Commit: u/chapoton/11559 @ a16336e

Reviewer: Andrey Novoseltsev, Jan Keitel

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

[vbraun]

Attachment: trac_11559_fix_Chow_group.patch.gz

Updated patch

[novoselt]

comment:1

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.

[novoselt]

Reviewer: Andrey Novoseltsev

[rbeezer]

comment:2

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

[vbraun]

comment:3

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.

[hivert]

comment:5

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

[hivert]

comment:6

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

[vbraun]

comment:7

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.

[novoselt]

Changed dependencies from #11558 to #11558, #10998

[seblabbe]

comment:9

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

[novoselt]

comment:10

Does not apply on Sage-5.0.beta4!

[nthiery]

comment:11

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).

[novoselt]

Work Issues: rebasing

[novoselt]

Changed work issues from rebasing to none

[novoselt]

comment:13

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!

[novoselt]

Changed keywords from none to toric, sd40.5

[novoselt]

Changed dependencies from #11558, #10998 to #11558, #10998, #13023

[novoselt]

Rebased for Sage-5.1.beta0

[novoselt]

comment:15

Attachment: trac_11559_fix_Chow_group.2.patch.gz

Now works fine after file move.

[sagetrac-jkeitel]

Changed branch from u/chapoton/11559 to u/jkeitel/11559

[fchapoton]

comment:29

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

[fchapoton]

comment:30

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

[novoselt]

comment:31

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.

[fchapoton]

New commits:

b94f43d

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

[fchapoton]

Changed commit from 85a053d to b94f43d

[fchapoton]

Changed branch from u/jkeitel/11559 to u/chapoton/11559

[pjbruin]

comment:34

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

[fchapoton]

Changed dependencies from #11558, #10998, #13023 to none

[sagetrac-git]

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

a16336e

Merge branch 'u/chapoton/11559' in 8.1.b5

[sagetrac-git]

Changed commit from b94f43d to a16336e