Very inefficient scalar multiplication on FreeModule_ambient with somewhat large rank

[dansme]

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.

CC: @jdemeyer

Component: linear algebra

Author: Daniel Smertnig, Marc Mezzarobba

Branch/Commit: 8f09d51

Reviewer: Vincent Delecroix

Issue created by migration from https://trac.sagemath.org/ticket/13304

[dansme]

comment:1

Attachment: trac_13304_gen_speedup.patch.gz

The patch overrides gen in FreeModule_ambient to avoid generating the entire standard basis.

[sagetrac-tfeulner]

comment:3

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.

[nbruin]

comment:4

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

[sagetrac-tfeulner]

comment:5

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.

[nathanncohen]

comment:7

(from the previous comments, it looks like the patch in its current state is not waiting for a review)

[mezzarobba]

comment:9

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, ℤ¹⁰⁰⁰⁰, unless one absolutely needs the whole basis!

[mezzarobba]

Author: Daniel Smertnig, Marc Mezzarobba

[mezzarobba]

Branch: u/mmezzarobba/13304-free_module_ambient+coerce

[mezzarobba]

New commits:

3c87ef3	Trac 13304: FreeModule_Ambient.gen speedup
8fd7f88	Implement reviewer suggestions, + cosmetic changes

[mezzarobba]

Commit: 8fd7f88

[mezzarobba]

comment:11

I opened a separate ticket (#15953) for the more general issue of whether and when to cache the basis.

[fchapoton]

Changed branch from u/mmezzarobba/13304-free_module_ambient+coerce to public/ticket/13304

[fchapoton]

comment:15

I just made a small clean-up and checked that doc builds and look nice.

---

New commits:

8fba50f	Merge with 6.4.beta4
8f09d51	trac #13304 put raise statement into py3 shape, plus minor cleanup

[fchapoton]

Changed commit from 8fd7f88 to 8f09d51

[mezzarobba]

comment:16

Frédéric, did you review the commits prior to yours?

[videlec]

Reviewer: Vincent Delecroix

[videlec]

comment:17

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)

[mezzarobba]

comment:18

Replying to @videlec:

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)

Does it make the solution in this ticket inadequate? Or is it just a similar problem that can be handled separately?

[videlec]

comment:19

Replying to @mezzarobba:

Replying to @videlec:

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)

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?

[mezzarobba]

comment:20

Replying to @videlec:

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

[videlec]

comment:21

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?

[videlec]

comment:22

Replying to @videlec:

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

[jdemeyer]

comment:24

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.

[jdemeyer]

comment:25

Actually, #17585 fixes

sage: V = ZZ['x']^50000
sage: V([0]*50000)

but not

sage: vector([0]*50000)/1

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

[jdemeyer]

Work Issues: add doctest

[videlec]

comment:26

Replying to @jdemeyer:

Actually, #17585 fixes

sage: V = ZZ['x']^50000
sage: V([0]*50000)

but not

sage: vector([0]*50000)/1

Since 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?

[jdemeyer]

Changed work issues from add doctest to none

[jdemeyer]

comment:27

Sorry, there was a misunderstanding. I thought that this ticket fixed both issues.

[vbraun]

Changed branch from public/ticket/13304 to 8f09d51