Opened 11 years ago
Closed 8 years ago
#13304 closed defect (fixed)
Very inefficient scalar multiplication on FreeModule_ambient with somewhat large rank
Reported by: | daniels | Owned by: | daniels |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | linear algebra | Keywords: | |
Cc: | jdemeyer | Merged in: | |
Authors: | Daniel Smertnig, Marc Mezzarobba | Reviewers: | Vincent Delecroix |
Report Upstream: | N/A | Work issues: | |
Branch: | 8f09d51 (Commits, GitHub, GitLab) | Commit: | 8f09d5198e060add5dea75ed240739f6485ba8ce |
Dependencies: | Stopgaps: |
Description
As reported in a thread in sage-support trivial scalar multiplication in FreeModule_ambient
can be extremely slow or lead to out of memory errors:
n = 10000 v = vector([0]*n) # ok so far v2 = v/1 # kaboom
The problem is that, during coercion, _an_element_impl()
and in turn gen(0)
of FreeModule_ambient
gets called. The default implementation of gen
calls basis()
, computing the entire standard basis, and then returns the first basis vector.
Attachments (1)
Change History (29)
Changed 11 years ago by
Attachment: | trac_13304_gen_speedup.patch added |
---|
comment:1 Changed 11 years ago by
comment:2 Changed 11 years ago by
Status: | new → needs_review |
---|
comment:3 Changed 10 years ago by
The change looks fine to me and passes all tests. Maybe you should
- fill in your real name as Author of this ticket
- add your name to the author section of the file
- mark the doctest with the ticket number as an in-line comment
- explain the speed efficiency gained after applying the patch.
comment:4 follow-up: 9 Changed 10 years ago by
It's possible that calling base_ring().one_element()
is a bit faster than converting the integer 1 into the ring every time. The method one_element
normally gets cached.
What's more, previously, asking for one basis element triggered basis computation and caching. After that, getting basis elements should be fast. With your patch this caching doesn't get triggered by asking for one basis vector any more. Code that previously benefited m might see a decrease in speed (which can be solved by first explicitly asking for the whole basis to trigger caching).
It might still be a good idea to not cache, but you might document the possible pitfall.
comment:5 Changed 10 years ago by
The question is, in which situations do we actually ask for the basis of the ambient space? I found out that there is a similar problem when constructing subspaces, see sage-devel. Unfortunately, this is not solved with this patch.
Surprisingly, there is a difference between the fields GF(4, 'a')
and QQ
.
comment:6 Changed 9 years ago by
Milestone: | sage-5.11 → sage-5.12 |
---|
comment:7 Changed 9 years ago by
Status: | needs_review → needs_work |
---|
(from the previous comments, it looks like the patch in its current state is not waiting for a review)
comment:8 Changed 9 years ago by
Milestone: | sage-6.1 → sage-6.2 |
---|
comment:9 Changed 9 years ago by
See also #10262.
Replying to nbruin:
What's more, previously, asking for one basis element triggered basis computation and caching. After that, getting basis elements should be fast.
If I understand correctly, the basis we are talking about is essentially the identity matrix. In fact, I am not convinced caching it (strongly at least) is such a good idea even in general—either recomputing it or computing whatever information one really needs instead sounds better in all cases I can think of. But in any case I think it is insane to call a function that may keep in cache a basis of, say, ℤ^{10000}, unless one absolutely needs the whole basis!
comment:10 Changed 9 years ago by
Authors: | → Daniel Smertnig, Marc Mezzarobba |
---|---|
Branch: | → u/mmezzarobba/13304-free_module_ambient+coerce |
Commit: | → 8fd7f887c5485001dbb8f6b2919db06ae8e686e2 |
comment:11 Changed 9 years ago by
Status: | needs_work → needs_review |
---|
I opened a separate ticket (#15953) for the more general issue of whether and when to cache the basis.
comment:12 Changed 9 years ago by
Priority: | minor → major |
---|
comment:13 Changed 9 years ago by
Milestone: | sage-6.2 → sage-6.3 |
---|
comment:14 Changed 8 years ago by
Milestone: | sage-6.3 → sage-6.4 |
---|
comment:15 Changed 8 years ago by
Branch: | u/mmezzarobba/13304-free_module_ambient+coerce → public/ticket/13304 |
---|---|
Commit: | 8fd7f887c5485001dbb8f6b2919db06ae8e686e2 → 8f09d5198e060add5dea75ed240739f6485ba8ce |
comment:17 follow-up: 18 Changed 8 years ago by
Reviewers: | → Vincent Delecroix |
---|---|
Status: | needs_review → needs_work |
Hello,
You got it right for integer vectors but the generic constructor of FreeModuleElement_generic_dense
does call the basis in a very stupid way
coefficient_ring = parent.basis()[0][0].parent()
In particular the following also takes life time for the very same reason
sage: V = ZZ['x']^50000 sage: V([0]*50000)
comment:18 follow-up: 19 Changed 8 years ago by
Replying to vdelecroix:
You got it right for integer vectors but the generic constructor of
FreeModuleElement_generic_dense
does call the basis in a very stupid waycoefficient_ring = parent.basis()[0][0].parent()In particular the following also takes life time for the very same reason
sage: V = ZZ['x']^50000 sage: V([0]*50000)
Does it make the solution in this ticket inadequate? Or is it just a similar problem that can be handled separately?
comment:19 follow-up: 20 Changed 8 years ago by
Replying to mmezzarobba:
Replying to vdelecroix:
You got it right for integer vectors but the generic constructor of
FreeModuleElement_generic_dense
does call the basis in a very stupid waycoefficient_ring = parent.basis()[0][0].parent()In particular the following also takes life time for the very same reason
sage: V = ZZ['x']^50000 sage: V([0]*50000)Does it make the solution in this ticket inadequate? Or is it just a similar problem that can be handled separately?
Second option. It is just a one line change (that I can even do myself). Do you prefer this one line change to be on another ticket?
comment:20 Changed 8 years ago by
Replying to vdelecroix:
Second option. It is just a one line change (that I can even do myself). Do you prefer this one line change to be on another ticket?
No, please feel free to do it here if you like. (I can't do it myself at the moment.)
comment:21 follow-up: 22 Changed 8 years ago by
Cc: | jdemeyer added |
---|
comment:22 Changed 8 years ago by
Replying to vdelecroix:
Wow! Because of #11751 that introduces a very weird behavior the call to
.basis()
is somewhat unavoidable. Jeroen already pointed that out in #11751 and proposed to revert the changes. I am in favor of also reverting the changes. Might be better within another ticket?
The problem mentioned in comment:17 and the follow-ups needs #17585. In the meantime I am running the test for this branch on sage-6.6.beta0 and will set a positive review accordinlgy.
Vincent
comment:23 Changed 8 years ago by
Status: | needs_work → positive_review |
---|
comment:24 Changed 8 years ago by
I think that #17585 provides a better and more fundamental fix to the problem: the line
coefficient_ring = parent.basis()[0][0].parent()
is just removed completely.
comment:25 follow-up: 26 Changed 8 years ago by
Status: | positive_review → needs_work |
---|---|
Work issues: | → add doctest |
comment:26 Changed 8 years ago by
Replying to jdemeyer:
Actually, #17585 fixes
sage: V = ZZ['x']^50000 sage: V([0]*50000)but not
sage: vector([0]*50000)/1Since this ticket looks quite independent of #17585, it makes sense to have both.
I do suggest to add the two doctests above, since they clearly test different issues.
The first one should go in #17585, no?
comment:27 Changed 8 years ago by
Status: | needs_work → positive_review |
---|---|
Work issues: | add doctest |
Sorry, there was a misunderstanding. I thought that this ticket fixed both issues.
comment:28 Changed 8 years ago by
Branch: | public/ticket/13304 → 8f09d5198e060add5dea75ed240739f6485ba8ce |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
The patch overrides
gen
inFreeModule_ambient
to avoid generating the entire standard basis.