do not duplicate cache in Stream_uninitialized

[mantepse]

Currently, an instance of Stream_initialized duplicates the cache of its defining stream.

This ticket aims at removing this redundancy, at least in the case when the defining stream is dense.

Depends on #34636

CC: @tscrim

Component: combinatorics

Keywords: LazyPowerSeries

Author: Martin Rubey

Branch/Commit: u/mantepse/do_not_duplicate_cache_in_stream_uninitialized @ d64d3cb

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

[mantepse]

Branch: u/mantepse/do_not_duplicate_cache_in_stream_uninitialized

[mantepse]

Author: Martin Rubey

[mantepse]

Last 10 new commits:

bd3e3eb	make sparsity a decision of the user
814aa7c	remove Stream_cauchy_invert.get_coefficient, make sparse a mandatory argument, move _is_sparse an attribute of Stream_inexact
7043d1c	remove redundant `__init__` methods, remove finished TODOs
e6c4cae	make Stream_uninitialized always dense to avoid maximal recursion error
9577386	implement Polynomial_generic_sparse.__floordiv__
ec1eebd	Merge branch 'u/mantepse/__floordiv___for_sparse_polynomials' of trac.sagemath.org:sage into t/34636/make_sparsity_a_decision_of_the_user
de424bd	make internal rings sparse or dense if the lazy series ring is sparse or dense
66c1208	Merge branch 'u/mantepse/make_sparsity_a_decision_of_the_user' of trac.sagemath.org:sage into t/34611/fast_implementation_of_exp
5020b9d	adapt exp and log to new sparsity
8396a91	remove _target

[mantepse]

Commit: 8396a91

[mantepse]

comment:3

In principle, we could also make Stream_uninitialized inherit sparsity from it's defining stream, I doubt that this makes a big difference.

[mantepse]

comment:4

Unfortunately, the current branch fails. Here is a simplified illustration of what goes wrong:

sage: L.<z> = LazyPowerSeriesRing(ZZ)
sage: A = L.undefined(valuation=5)
sage: B = L.undefined()
sage: A.define(z^5 + B)
sage: B.define(z + A)
sage: A
z^5 + z^9 + z^10 + O(z^12)
sage: B
1 + z^4 + O(z^7)

I think we are sloppy about our use of _approximate_order and _offset, which are now both lazy attributes. This might eventually become a problem anyway (eg. with #34556), so we better solve it:

sage: A = L.undefined(valuation=5); B = L.undefined(); A.define(z^5 + B); B.define(z + A)
sage: A._coeff_stream._offset
5
sage: B._coeff_stream._offset
0
sage: B[0]
1

The iterator of B (which is just the default iterator of Stream_inexact) is

    def iterate_coefficients(self):
        n = self._approximate_order
        while True:
            yield self.get_coefficient(n)
            n += 1

When it is called by B._coeff_stream.__getitem__[0], we find n == self._approximate_order == 1, which does not correspond to self._offset, which is 0.

[mantepse]

Changed keywords from none to LazyPowerSeries

[mantepse]

comment:6

I think the problem is that the _approximate_order in the iterator comes from (z + A)._coeff_stream, i.e., from Stream_add, whereas the _approximate_order used to compute B._coeff_stream._offset comes from B, i.e., Stream_uninitialized.

This is quite confusing :-)

[mantepse]

comment:7

I am guessing, the essence of the problem is that we do not clearly specify with which coefficient Stream.iterate_coefficients begins.

The current behaviour is that it starts with the _approximate_order which is currently valid :-)

[mantepse]

comment:8

I should add that the definition above, A.define(z^5 + B); B.define(z + A), does not make sense with A = L.undefined(valuation=5). That is, it should fail because the valuation of B would then be 1, contradicting the stated valuation of A.

[mantepse]

comment:9

Actually, now I found a bug (or garbage in - garbage out without warning), without this ticket:

sage: L.<z> = LazyPowerSeriesRing(ZZ, sparse=False); A = L.undefined(valuation=3); B = L.undefined(); A.define(z^3 + B); B.define(z^2 + A^2)
sage: A
z^3 + z^6 + 2*z^9 + O(z^10)
sage: B
z^2 + z^6 + O(z^7)

This is wrong, because A != z^3 + B.

[mantepse]

Dependencies: #34636

[sagetrac-git]

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

72f2037	Merge branch 'develop' of trac.sagemath.org:sage into t/34661/do_not_duplicate_cache_in_stream_uninitialized
d64d3cb	experimentally also redefine the approximate order of the target

[sagetrac-git]

Changed commit from 8396a91 to d64d3cb

[mantepse]

comment:12

Resetting the approximate order of self and of coeff_stream in Stream_uninitialized.define seems to work roughly (unless coeff_stream._is_sparse, of course), but I am quite sure it is not the right way to do it. In particular, there are some failures which I don't quite understand (among others).

My hope would be to have a cleaner design, and more precise responsibilities for approximate_order.

Help would be very much appreciated.

I guess I should go through a simple recursive definition with pen and paper.

[mantepse]

comment:13

@tscrim, in case you have some time, this is the ticket I currently find most important.

I'd like to stress, however, that I do not find the aim as stated in the description important (in most cases, the savings will be negligible). Instead, what I hope for is a much cleaner (and therefore more robust) design.

In particular, this ticket should probably be considered together with #34556.

[tscrim]

comment:14

I am not sure this is possible when the undefined stream has an AO (= Approximate Order) larger than that of the target stream. If undef.AO > target.AO, then when you copy the cache of the target, then you get a misalignment of the undef cache with the AO. In particular, the is_nonzero is assuming that any nonzero entry in the cache corresponds to an entry at least the stream's AO.

[mantepse]

comment:15

Maybe we could have a meeting some time to talk about this. Things are not clear to me at all.

[tscrim]

comment:16

That would be good. Send me an email and we can set it up. I am basically free anytime you would be awake (including tomorrow) except for my Wednesday evenings.

[mantepse]

comment:17

I'm afraid I won't make it this week, I'll send mail as soon as I have time!

[tscrim]

comment:18

No problem. I will be at a conference next week, but I can talk during my evenings.