Opened 10 years ago
Last modified 4 years ago
#11559 needs_work enhancement
Speed up Posets and toric Chow group
Reported by:  vbraun  Owned by:  

Priority:  major  Milestone:  sage7.1 
Component:  algebraic geometry  Keywords:  toric, sd40.5 
Cc:  sagecombinat  Merged in:  
Authors:  Volker Braun  Reviewers:  Andrey Novoseltsev, Jan Keitel 
Report Upstream:  N/A  Work issues:  
Branch:  u/chapoton/11559 (Commits, GitHub, GitLab)  Commit:  a16336e08c9f967a5e1106406329f44b899261ee 
Dependencies:  Stopgaps: 
Description (last modified by )
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)
Change History (40)
Changed 10 years ago by
comment:1 Changed 10 years ago by
 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 10 years ago by
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 nonspecialists.
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 10 years ago by
hermite_form
is an alias for echelon_form
for dense ZZmatrices. Sparse ZZmatrices 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 userspecified 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 10 years ago by
 Status changed from new to needs_review
comment:5 Changed 10 years ago by
 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 10 years ago by
 Cc sagecombinat 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 10 years ago by
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 PosetElement
s 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 10 years ago by
 Dependencies changed from #11558 to #11558, #10998
comment:9 Changed 10 years ago by
Same lines are edited by #12351. One will have to adapt to the other one.
comment:10 followup: ↓ 11 Changed 9 years ago by
 Status changed from needs_review to needs_work
Does not apply on Sage5.0.beta4!
comment:11 in reply to: ↑ 10 Changed 9 years ago by
comment:12 Changed 9 years ago by
 Work issues set to rebasing
comment:13 Changed 9 years ago by
 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 9 years ago by
 Dependencies changed from #11558, #10998 to #11558, #10998, #13023
 Keywords toric sd40.5 added
comment:15 Changed 9 years ago by
Now works fine after file move.
Changed 8 years ago by
comment:16 Changed 8 years ago by
 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 8 years ago by
 Milestone changed from sage5.11 to sage5.12
Changed 8 years ago by
comment:18 Changed 8 years ago by
 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 8 years ago by
I just noticed this ticket. Has someone tried using have_same_parent(self, other) ?
comment:20 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:21 Changed 7 years ago by
 Branch set to u/chapoton/11559
 Commit set to ad1701157f4c051ac160c72b7e63ba7ad7aeb822
comment:22 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:23 Changed 7 years ago by
 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: [1d cone of Rational polyhedral fan in 3d lattice M, 1d cone of Rational polyhedral fan in 3d lattice M, 3d cone of Rational polyhedral fan in 3d lattice M, 3d cone of Rational polyhedral fan in 3d lattice M] Got: [1d cone of Rational polyhedral fan in 3d lattice M, 3d cone of Rational polyhedral fan in 3d lattice M, 3d cone of Rational polyhedral fan in 3d lattice M, 1d cone of Rational polyhedral fan in 3d lattice M]
comment:24 Changed 7 years ago by
 Commit changed from ad1701157f4c051ac160c72b7e63ba7ad7aeb822 to 6cd90ca42510ca957f59363321ef24074eef1e30
comment:25 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:26 Changed 7 years ago by
 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:
85a053d  Nitpicking for 11559: Added a space

comment:27 Changed 7 years ago by
 Status changed from positive_review to needs_review
comment:28 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:29 Changed 6 years ago by
 Milestone changed from sage6.4 to sage6.6
This ticket seems to confuse the patchbot. But maybe any ticket would..
comment:30 Changed 6 years ago by
 Status changed from needs_review to needs_info
Put to need info just to stop the bots looptesting this ticket.
comment:31 Changed 6 years ago by
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 6 years ago by
 Branch changed from u/jkeitel/11559 to u/chapoton/11559
 Commit changed from 85a053daeadeb7a8d1de24e354cc6fc99068df7f to b94f43d70821674c635b318d964ec22974abe961
New commits:
b94f43d  Merge branch 'u/jkeitel/11559' of ssh://trac.sagemath.org:22/sage into 11559

comment:33 Changed 6 years ago by
 Milestone changed from sage6.6 to sage6.7
comment:34 Changed 6 years ago by
 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 5 years ago by
 Dependencies #11558, #10998, #13023 deleted
 Description modified (diff)
 Milestone changed from sage6.7 to sage7.1
comment:36 Changed 4 years ago by
 Commit changed from b94f43d70821674c635b318d964ec22974abe961 to a16336e08c9f967a5e1106406329f44b899261ee
Branch pushed to git repo; I updated commit sha1. New commits:
a16336e  Merge branch 'u/chapoton/11559' in 8.1.b5

Updated patch