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.

[vbraun]

Updated patch

[novoselt]

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.

[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

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

[hivert]

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]

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]

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.

[slabbe]

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

[novoselt]

Does not apply on Sage-5.0.beta4!

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

[novoselt]

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]

Rebased for Sage-5.1.beta0

[novoselt]

Now works fine after file move.

[chapoton]

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.

[chapoton]

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

[nthiery]

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

[chapoton]

here is a git branch

---

New commits:

​7437e82	Trac #11559: Speed up Posets and toric Chow group
​3322d7c	trac #11559 fixing failing doctests
​ad17011	trac 11559 check if other has attribute vertex

[pbruin]

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]

[git]

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

​860f696	Merge branch 'u/chapoton/11559' of ssh://trac.sagemath.org:22/sage into 11559
​6cd90ca	trac #11559 correct failing doctest

[jkeitel]

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:

​85a053d

Nitpicking for 11559: Added a space

[chapoton]

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

[chapoton]

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

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

[chapoton]

New commits:

​b94f43d

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

[pbruin]

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

[git]

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

​a16336e

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