Speed up Posets and toric Chow group

vbraun commented 13 years ago

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 commented 13 years ago

Attachment: trac_11559_fix_Chow_group.patch.gz

Updated patch

novoselt commented 13 years ago

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 commented 13 years ago

Reviewer: Andrey Novoseltsev

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago

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 commented 13 years ago

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 commented 13 years ago

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 commented 13 years ago

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 commented 13 years ago

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 commented 13 years ago

Changed dependencies from #11558 to #11558, #10998

seblabbe commented 12 years ago

comment:9

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

novoselt commented 12 years ago

comment:10

Does not apply on Sage-5.0.beta4!

nthiery commented 12 years ago

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 commented 12 years ago

Work Issues: rebasing

novoselt commented 12 years ago

Changed work issues from rebasing to none

novoselt commented 12 years ago

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 commented 12 years ago

Changed keywords from none to toric, sd40.5

novoselt commented 12 years ago

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

novoselt commented 12 years ago

Rebased for Sage-5.1.beta0

novoselt commented 12 years ago

comment:15

Attachment: trac_11559_fix_Chow_group.2.patch.gz

Now works fine after file move.

fchapoton commented 11 years ago

Description changed:

--- 
+++ 
@@ -8,3 +8,8 @@
 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.
+
+Apply:
+
+- [attachment: trac_11559_fix_Chow_group.2.patch](https://github.com/sagemath/sage-prod/files/10653243/trac_11559_fix_Chow_group.2.patch.gz)
+- [attachment: trac_11559_hasattr_vertex_fc.patch](https://github.com/sagemath/sage-prod/files/10653244/trac_11559_hasattr_vertex_fc.patch.gz)

fchapoton commented 11 years ago

comment:16

Attachment: trac_11559_hasattr_vertex_fc.patch.gz

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.

fchapoton commented 11 years ago

Attachment: trac_11559_fixdoctest.patch.gz

fchapoton commented 11 years ago

Description changed:

--- 
+++ 
@@ -12,4 +12,5 @@
 Apply:

 - [attachment: trac_11559_fix_Chow_group.2.patch](https://github.com/sagemath/sage-prod/files/10653243/trac_11559_fix_Chow_group.2.patch.gz)
+- [attachment: trac_11559_fixdoctest.patch](https://github.com/sagemath/sage-prod/files/10653245/trac_11559_fixdoctest.patch.gz)
 - [attachment: trac_11559_hasattr_vertex_fc.patch](https://github.com/sagemath/sage-prod/files/10653244/trac_11559_hasattr_vertex_fc.patch.gz)

fchapoton commented 11 years ago

comment:18

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 commented 11 years ago

comment:19

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

fchapoton commented 10 years ago

comment:21

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`

fchapoton commented 10 years ago

Commit: ad17011

fchapoton commented 10 years ago

Branch: u/chapoton/11559

pjbruin commented 10 years ago

comment:23

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]

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from ad17011 to 6cd90ca

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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`

a1031e5c-5e2c-4c90-8ba4-91be67e304df commented 10 years ago

Changed commit from 6cd90ca to 85a053d

a1031e5c-5e2c-4c90-8ba4-91be67e304df commented 10 years ago

comment:26

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

a1031e5c-5e2c-4c90-8ba4-91be67e304df commented 10 years ago

Changed reviewer from Andrey Novoseltsev to Andrey Novoseltsev, Jan Keitel

a1031e5c-5e2c-4c90-8ba4-91be67e304df commented 10 years ago

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

fchapoton commented 9 years ago

comment:29

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

fchapoton commented 9 years ago

comment:30

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

novoselt commented 9 years ago

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 commented 9 years ago

New commits:

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

fchapoton commented 9 years ago

Changed commit from 85a053d to b94f43d

fchapoton commented 9 years ago

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

pjbruin commented 9 years ago

comment:34

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

fchapoton commented 8 years ago

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

fchapoton commented 8 years ago

Description changed:

--- 
+++ 
@@ -7,10 +7,4 @@

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.

-Apply:

-- attachment: trac_11559_fix_Chow_group.2.patch -- attachment: trac_11559_fixdoctest.patch -- attachment: trac_11559_hasattr_vertex_fc.patch +Patch has some other fixes. Changes the Chow group to use sparse matrices.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from b94f43d to a16336e

sagemath / sage

Speed up Posets and toric Chow group #11559

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

-Apply: