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: | 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, 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 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 10 years ago by
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 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 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 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 9 years ago by
Same lines are edited by #12351. One will have to adapt to the other one.
comment:10 follow-up: ↓ 11 Changed 9 years ago by
- Status changed from needs_review to needs_work
Does not apply on Sage-5.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 sage-5.11 to sage-5.12
Changed 7 years ago by
comment:18 Changed 7 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 7 years ago by
I just noticed this ticket. Has someone tried using have_same_parent(self, other) ?
comment:20 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.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 sage-6.2 to sage-6.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: [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 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 sage-6.3 to sage-6.4
comment:29 Changed 6 years ago by
- 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 6 years ago by
- Status changed from needs_review to needs_info
Put to need info just to stop the bots loop-testing 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 sage-6.6 to sage-6.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 sage-6.7 to sage-7.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