Implementation of streams as backend for LazyLaurentSeries

[tejasvicsr1]

We rewrite the input data for LazyLaurentSeries to use a Stream that has both a dense version similar to a lazy_list and a sparse version using a dict. We use various subclasses to build an evaluation tree for expressions involving lazy Laurent series elements.

We provide additional features not previously implemented for lazy Laurent series, such as functional definitions and composition. This provides enhancements for features such as exact arithmetic, equality, and performance. This is supplemented by an extensive suite of tests and examples.

This ticket is part of the meta ticket #31651. It provides the underlying data structures for lazy series, which later tickets include lazy, e.g., Taylor (usual power series) and Dirichlet series. This will eventually serve as a replacement for LazyPowerSeries (#32367; see also #15673).

CC: @mantepse @tscrim

Component: combinatorics

Keywords: LazyPowerSeries, FormalSeries, gsoc2021

Author: Tejasvi Chebrolu, Travis Scrimshaw

Branch/Commit: 1ff0cac

Reviewer: Travis Scrimshaw, Martin Rubey, Samuel Lelièvre

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

[mantepse]

Changed keywords from LazyPowerSeries, FormalSeries, GSoC to LazyPowerSeries, FormalSeries, GSoC21

[tejasvicsr1]

Branch: u/gh-tejasvicsr1/a_dense_implementation_for_the_lazy_laurent_series

[sagetrac-git]

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

5f7e600

Incomplete code for the dense implementation added.

[sagetrac-git]

Commit: 5f7e600

[sagetrac-git]

Changed commit from 5f7e600 to 70a8e2d

[sagetrac-git]

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

96fe111	Test
70a8e2d	Added code for dense implementation without lazy lists. However, the dense implementation has some issues with list indices.

[sagetrac-git]

Changed commit from 70a8e2d to 995e7fb

[sagetrac-git]

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

995e7fb

First iteration of the dense implementation of Lazy Laurent Series without lists is completed.

[sagetrac-git]

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

bd0071b

First iteration of the dense implementation of Lazy Laurent Series without lists is completed. Fixed a small bug.

[sagetrac-git]

Changed commit from 995e7fb to bd0071b

[sagetrac-git]

Changed commit from bd0071b to 271672c

[sagetrac-git]

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

271672c

Second version of the dense implementation of the lazy Laurent Series without lazy lists. Fixed the issues with the cache.

[sagetrac-git]

Changed commit from 271672c to a012fbc

[sagetrac-git]

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

a012fbc

Fixed the error in valuation code and also shortened the coefficient code to three lines.

[sagetrac-git]

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

5011d44

Fixed the recursion bug in the dense implementation. Added a doctest for the dense version of the coefficient code.

[sagetrac-git]

Changed commit from a012fbc to 5011d44

[mantepse]

Changed branch from u/gh-tejasvicsr1/a_dense_implementation_for_the_lazy_laurent_series to u/mantepse/a_dense_implementation_for_the_lazy_laurent_series

[tejasvicsr1]

Changed branch from u/mantepse/a_dense_implementation_for_the_lazy_laurent_series to u/gh-tejasvicsr1/a_dense_implementation_for_the_lazy_laurent_series

[sagetrac-git]

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

79eaf4a

Added the file for the new design.

[sagetrac-git]

Changed commit from 5011d44 to 79eaf4a

[sagetrac-git]

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

cbbc75b

Implemented generation and multiplication in the new design.

[sagetrac-git]

Changed commit from 79eaf4a to cbbc75b

[sagetrac-git]

Changed commit from cbbc75b to 15ef8f1

[sagetrac-git]

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

27755ec	Implemented addition for the new design.
15ef8f1	Implemented representation for the new design.

[sagetrac-git]

Changed commit from 15ef8f1 to daaad21

[sagetrac-git]

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

b0b438c	Implemented scalar multiplication for the new implementation.
daaad21	Implemented scalar multiplication for the new implementation and fixed the formatting.

[mantepse]

comment:127

One further thought:

I'm not quite sure we should really insist in the doctests on a difference between Stream_exact and Stream_zero. It looks like an implementation detail to me. I think that from the user's perspective, there should be absolutely no difference in behaviour between the two - in contrast to any Stream_inexact.

In case you do not agree, did you have a test as follows in mind:

            sage: from sage.data_structures.stream import Stream_zero
            sage: L.<z> = LazyLaurentSeriesRing(ZZ)
            sage: s = L(0).map_coefficients(lambda c: c + 1); s
            0
            sage: isinstance(s._coeff_stream, Stream_zero)
            True

[tscrim]

comment:128

Replying to @mantepse:

One further thought:

I'm not quite sure we should really insist in the doctests on a difference between Stream_exact and Stream_zero. It looks like an implementation detail to me. I think that from the user's perspective, there should be absolutely no difference in behaviour between the two - in contrast to any Stream_inexact.

Running that argument further, Stream_exact and Stream_inexact could be seen as an implementation detail. All the user sees is the element of the lazy Laurent series. It is the developers that see more (as they need to).

Here we are actually wanting to test something about the implementation. Plus Stream_zero is a very special object because it is the only thing that will have a non-integer (approximate) order.

I don't think we should test foo(L(0)) is L.zero() as we cannot (nor should) presume there is a unique zero instance. Although this would be highly desirable.

In case you do not agree, did you have a test as follows in mind:

            sage: from sage.data_structures.stream import Stream_zero
            sage: L.<z> = LazyLaurentSeriesRing(ZZ)
            sage: s = L(0).map_coefficients(lambda c: c + 1); s
            0
            sage: isinstance(s._coeff_stream, Stream_zero)
            True

Yes, that would be the test I would want to run here.

[sagetrac-git]

Changed commit from dea0e2f to 359a91e

[sagetrac-git]

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

359a91e

insist on Stream_zero in map_coefficients doctest

[mantepse]

comment:130

Replying to @tscrim:

Replying to @mantepse:

One further thought:

I'm not quite sure we should really insist in the doctests on a difference between Stream_exact and Stream_zero. It looks like an implementation detail to me. I think that from the user's perspective, there should be absolutely no difference in behaviour between the two - in contrast to any Stream_inexact.

Running that argument further, Stream_exact and Stream_inexact could be seen as an implementation detail. All the user sees is the element of the lazy Laurent series. It is the developers that see more (as they need to).

Here we are actually wanting to test something about the implementation. Plus Stream_zero is a very special object because it is the only thing that will have a non-integer (approximate) order.

I have done the requested change. The remainder of this comment is only for our personal enjoyment:

I think that there is quite a fundamental - and in fact user-visible - difference between Stream_exact and Stream_inexact. It is user visible, since the big-O term is missing from the output. It is fundamental, because we can decide equality.

I agree with your argument that Stream_zero is a very special object because of its infinite order.

[sagetrac-git]

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

6eefb03

always be explicit about the arguments to the element constructor in examples

[sagetrac-git]

Changed commit from 359a91e to 6eefb03

[mantepse]

comment:132

I'm not sure whether you will hate me for this :-)

I think we should change the order of the optional arguments. Currently, we have:

    def _element_constructor_(self, x=None, valuation=None, constant=None, degree=None):

I think

    def _element_constructor_(self, x=None, valuation=None, degree=None, constant=None):

would be more logical. As I mentioned on #32309, we should also give the user the possibility to be explicit whether the argument is supposed to be interpreted as a polynomial or a function that yields the coefficients. It appears to me, that the least disruptive way is

    def _element_constructor_(self, x=None, valuation=None, degree=None, constant=None, coefficients=None):

Note that the original code does only allows a single value as argument to the element constructor, which then returns a constant series.

[mantepse]

comment:133

Ping?

[sagetrac-git]

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

4c43b1a

fix doctest

[sagetrac-git]

Changed commit from 6eefb03 to 4c43b1a

[sagetrac-git]

Changed commit from 4c43b1a to 51b812f

[sagetrac-git]

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

51b812f

remove ellipsis from doctests

[mantepse]

comment:136

Should we insist that valuation is an integer?

We currently test that it is not None, but I think it would be better to test in ZZ. Of course, that won't help with silliness of True, but isinstance(valuation, Integer) seems a bit strict to me.

[tscrim]

comment:137

Sorry, busy with teaching at the start of the week.

comment:132:

I don't think we should have a separate coefficients input; it is too problematic for a user to input things. We probably want to change the logic order to handle the case when the input is a callable before we check if we can convert to the Laurent polynomial ring.

Putting degree before constant is a good idea. We just have to tweak the logic for parsing the old input format.

comment:136:

I don't think we really need to make sure all input is valid. So we could trust the user with good input (and the result will fail at some point). However, I am not opposed to adding this in ZZ test, but it should be within the is not None check as it should raise an error if that extra check fails.

[mantepse]

comment:138

Sorry to put extra burden on you.

Concerning coefficients: there is no way to distinguish between coefficients and polynomials, since polynomials are callable.

[sagetrac-git]

Changed commit from 51b812f to b6c179c

[sagetrac-git]

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

b6c179c

put degree next to valuation in element constructor

[mantepse]

comment:140

I'm afraid we should also do something about series. The old signature was:

 series(coefficient, valuation, constant=None)

    Return a lazy Laurent series.

    INPUT:

        coefficient – Python function that computes coefficients

        valuation – integer; approximate valuation of the series

        constant – either None or pair of an element of the base ring and an integer

Currently, the signature is

    def series(self, coefficient, valuation, constant=None, degree=None):

which is confusing.

Should we make it

    def series(self, coefficient, valuation, degree=None, constant=None):

and allow degree to be a pair (constant, degree) or

    def series(self, coefficient, valuation, constant=None):

?

(perhaps it would be better to deprecate this method anyway)

[tscrim]

Changed branch from u/mantepse/dense_lls-31897 to u/tscrim/dense_lls-31897

[tscrim]

Changed commit from b6c179c to 1ff0cac

[tscrim]

comment:141

Don't worry about it; I just might not be able to always push changes so quickly this week.

We still don't have a good replacement for what the series method does. However, I agree with changing the signature and allowing the pair input. I also did the same if someone does constant=(a,b).

I thought a bit more about the coefficients attributes for the _element_constructor_. I think you're right that there is not really a better solution. I implemented something that is more minimal of a change to avoid duplication and to minimize the impact. Although on this ticket, it is likely not necessary as we cannot (easily) demonstrate a case where we must use the option.

I also added the checks for valuation in ZZ.

---

New commits:

acb0c5b	Merge branch 'u/mantepse/dense_lls-31897' of git://trac.sagemath.org/sage into u/tscrim/dense_lls-31897
61a32f6	Merge branch 'u/tscrim/dense_lls-31897' of git://trac.sagemath.org/sage into u/tscrim/dense_lls-31897
00bdf44	Merge branch 'u/mantepse/dense_lls-31897' of git://trac.sagemath.org/sage into u/tscrim/dense_lls-31897
df58693	Merge branch 'u/mantepse/dense_lls-31897' of git://trac.sagemath.org/sage into u/tscrim/dense_lls-31897
5324fc9	Better handling of degree and constant. Adding coefficients option.
1ff0cac	Add check for valuation in ZZ.

[mantepse]

comment:142

Thank you! Looks OK, if you agree, please set it back to 'positive review'!

[tscrim]

comment:143

Thank you. Now back to work on Dirichlet series.

[vbraun]

Changed branch from u/tscrim/dense_lls-31897 to 1ff0cac