Implementation of streams as backend for LazyLaurentSeries

tejasvicsr1 commented 3 years ago

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 2e15677 to 86c97cb

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

86c97cb Small correction to the ABC code.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

`b7fbf4f`	`Fixed the equality, and the comparisions.`
`3970194`	`Added checks to ensure that the coefficients are in the base ring in the apply_coeff method.`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 86c97cb to 3970194

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 3970194 to deb4e6c

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

`45f0bc4`	`Created new files.`
`6f135ec`	`Re-created old design.`
`deb4e6c`	`Fixed the issue in the binary comparsion and added the binary commutative class.`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

14a2447 New design.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from deb4e6c to 14a2447

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 14a2447 to dbeedf4

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

dbeedf4 Not working.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

9d3d790 Fixed infinite loop.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from dbeedf4 to 9d3d790

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

`0b5e216`	`Fixed truncate.`
`e473bcf`	`Fixed truncate(sparse implementation).`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 9d3d790 to e473bcf

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

ac538db Fixed truncate(empty cache).

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from e473bcf to ac538db

tscrim commented 3 years ago

Changed author from Tejasvi Chebrolu to Tejasvi Chebrolu, Travis Scrimshaw

tscrim commented 3 years ago

Changed commit from ac538db to 6d0d963

tscrim commented 3 years ago

Changed branch from u/gh-tejasvicsr1/a_dense_implementation_for_the_lazy_laurent_series to u/tscrim/dense_lls-31897

tscrim commented 3 years ago

New commits:

`38d87e9`	`Merge branch 'u/gh-tejasvicsr1/a_dense_implementation_for_the_lazy_laurent_series' of git://trac.sagemath.org/sage into u/gh-tejasvicsr1/a_dense_implementation_for_the_lazy_laurent_series`
`17d5257`	`Merge branch 'u/gh-tejasvicsr1/a_dense_implementation_for_the_lazy_laurent_series' of git://trac.sagemath.org/sage into u/gh-tejasvicsr1/a_dense_implementation_for_the_lazy_laurent_series`
`78d805d`	`Merge branch 'u/gh-tejasvicsr1/a_dense_implementation_for_the_lazy_laurent_series' of git://trac.sagemath.org/sage into u/gh-tejasvicsr1/a_dense_implementation_for_the_lazy_laurent_series`
`217c3ea`	`Removing unnecessary operator_new file.`
`075a9ac`	`Cleaning up all of the aux classes and getting most things working.`
`03fd8d0`	`Adding NotImplementedError for non-trivial p input for sparse polynomials.`
`6d0d963`	`Implementing uninitialized series and some other fixes.`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 6d0d963 to 944b10e

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

944b10e Fixing some bugs and making sure output of coeff_func are better.

mantepse commented 3 years ago

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

tscrim commented 3 years ago

comment:40

I have fixed the pickling issue, some bugs I found in _element_constructor_ in addition to what Martin pointed out, implemented slices (for LLS only to keep the LLS_aux classes fast with __getitem__), and ported over the doctests for define. We just need composition implemented in order to check the last test there.

New commits:

`49586f5`	`remove trailing whitespace`
`7114a49`	`Fix bug in valuation of LLS_eventually_geometric and better checking for define().`
`337b040`	`Implementing slices. Fixing bugs in _element_constructor_. Addine define() doctests.`

tscrim commented 3 years ago

Changed commit from 944b10e to 337b040

tscrim commented 3 years ago

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

tscrim commented 3 years ago

comment:41

Accidental double post...

tejasvicsr1 commented 3 years ago

Changed branch from u/tscrim/dense_lls-31897 to u/gh-tejasvicsr1/dense_lls-31897

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 337b040 to 09a1a55

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

09a1a55 Removed recursive tests.

mantepse commented 3 years ago

Changed branch from u/gh-tejasvicsr1/dense_lls-31897 to u/mantepse/dense_lls-31897

tejasvicsr1 commented 3 years ago

Changed branch from u/mantepse/dense_lls-31897 to u/gh-tejasvicsr1/dense_lls-31897

mantepse commented 3 years ago

Changed branch from u/gh-tejasvicsr1/dense_lls-31897 to u/mantepse/dense_lls-31897

tejasvicsr1 commented 3 years ago

Changed branch from u/mantepse/dense_lls-31897 to u/gh-tejasvicsr1/dense_lls-31897

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

`544e58d`	`remove modifications from original files`
`254578b`	`Merge branch 'u/gh-tejasvicsr1/dense_lls-31897' of git://trac.sagemath.org/sage into t/31897/dense_lls-31897`
`de489d8`	`Merge remote-tracking branch 'trac/u/mantepse/dense_lls-31897' into t/31897/a_dense_implementation_for_the_lazy_laurent_series`
`2eee97d`	`Composition done, minor edit left.`
`a4c8b74`	`Composition done, minor edit left.`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 09a1a55 to a4c8b74

tscrim commented 3 years ago

Changed branch from u/gh-tejasvicsr1/dense_lls-31897 to u/tscrim/dense_lls-31897

tscrim commented 3 years ago

New commits:

`cd665b8`	`Merge branch 'u/mantepse/dense_lls-31897' of git://trac.sagemath.org/sage into u/tscrim/dense_lls-31897`
`96beb66`	`Merge branch 'u/gh-tejasvicsr1/dense_lls-31897' of git://trac.sagemath.org/sage into u/tscrim/dense_lls-31897`
`7b6f953`	`Overhauling LLS composition.`
`3a8ff9e`	`Fix little bug in polynomial().`

tscrim commented 3 years ago

Changed commit from a4c8b74 to 3a8ff9e

tejasvicsr1 commented 3 years ago

Changed branch from u/tscrim/dense_lls-31897 to u/gh-tejasvicsr1/dense_lls-31897

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 3a8ff9e to 0e056f5

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

`1c213b9`	`Created a new file coefficient_stream.py and sorted the imports.`
`c702801`	`Chanded aux to coeff_stream.`
`18c443f`	`Moved the coefficients stream file into the data structures file.`
`8d3e45f`	`PEP 8 done again.`
`76ee5b7`	`Basic documentation done for the rings and series files.`
`efe5a53`	`Deleted .vscode`
`0e056f5`	`Started the documentation for the coefficient stream file.`

tscrim commented 3 years ago

Changed commit from 0e056f5 to b136d70

tscrim commented 3 years ago

Changed branch from u/gh-tejasvicsr1/dense_lls-31897 to u/tscrim/dense_lls-31897

tscrim commented 3 years ago

New commits:

b136d70 Improve speed of inv by using the cache.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from b136d70 to 5cd5b4d

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

5cd5b4d Fix bug with inverse.

tejasvicsr1 commented 3 years ago

Changed branch from u/tscrim/dense_lls-31897 to u/gh-tejasvicsr1/dense_lls-31897

tscrim commented 3 years ago

New commits:

`937fc6d`	`Basic documentation for coefficient stream code.`
`4b4c3aa`	`Merge branch 'u/tscrim/dense_lls-31897' of trac.sagemath.org:sage into t/31897/a_dense_implementation_for_the_lazy_laurent_series`
`e27da4b`	`Corrected coefficient stream file.`
`525409b`	`Added documentation for the coefficient_stream file.`
`fd6549a`	`Removing json file that should not be there.`
`4b7efa3`	`Fixing up some documentation and doctests.`

tscrim commented 3 years ago

Changed commit from 5cd5b4d to 4b7efa3

sagemath / sage

Implementation of streams as backend for LazyLaurentSeries #31897