more testsuites for lazy series rings #34552

mantepse · 2022-09-18T10:57:28Z

In this ticket we implement systematic tests for operations on lazy series.

Depends on #34470

CC: @tscrim

Component: combinatorics

Keywords: LazyPowerSeries

Author: Martin Rubey

Branch/Commit: 3e84c90

Reviewer: Travis Scrimshaw, Frédéric Chapoton

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

The text was updated successfully, but these errors were encountered:

mantepse · 2022-09-18T10:58:48Z

Branch: u/mantepse/more_testsuites_for_lazy_series_rings

mantepse · 2022-09-18T11:01:43Z

Author: Martin Rubey

mantepse · 2022-09-18T11:01:43Z

Last 10 new commits:

`e3e331c`	`add and correct some_elements for all rings, run all tests in the TestSuite (many fail)`
`00aaca0`	`introduce halting precision`
`f9dd62e`	`fix equality of exact series, do not produce coefficients of polynomials by iterating over them`
`b9a66be`	`implement missing required method lift_to_precision`
`88109cc`	`fix precision also in species directory, do not forget to switch it off after doctest`
`08baf9a`	`fix punctuation in docstrings`
`5bd0331`	`correct an_element and some_elements, implement is_unit, _test_invert`
`1722eca`	`fix is_unit`
`cdf821a`	`improve equality, raise errors when trying to invert series which are known not to be invertible, be more careful not to compute terms`
`cc48d4e`	`Merge branch 'u/mantepse/categories_of_lazy_series' of trac.sagemath.org:sage into t/34552/more_testsuites_for_lazy_series_rings`

mantepse · 2022-09-18T11:01:43Z

Changed keywords from none to LazyPowerSeries

mantepse · 2022-09-18T11:01:43Z

Dependencies: #34470

mantepse · 2022-09-18T11:01:43Z

Commit: cc48d4e

sagetrac-git · 2022-09-18T11:34:52Z

Changed commit from cc48d4e to 54bb1d8

sagetrac-git · 2022-09-18T11:34:52Z

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

`54bb1d8`	`add _test_revert and add more rings to test`

sagetrac-git · 2022-09-18T12:21:42Z

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

`60f0664`	`fix more _an_element and some_element with incorrect coefficients`

sagetrac-git · 2022-09-18T12:21:42Z

Changed commit from 54bb1d8 to 60f0664

mantepse · 2022-09-18T15:53:35Z

comment:5

Apparently, reversion of symmetric functions with linear coefficient different from 1 is completely broken:

sage: g = L(2*s[1]+s[2])
sage: g
2*p[1] + (1/2*p[1,1]+1/2*p[2])
sage: g.revert()(g)
p[1] + (-1/4*p[1,1]-1/4*p[2]) + (1/4*p[1,1,1]+1/4*p[2,1]) + (-9/32*p[1,1,1,1]-5/16*p[2,1,1]+3/32*p[2,2]+1/8*p[4]) + (11/32*p[1,1,1,1,1]+7/16*p[2,1,1,1]-1/32*p[2,2,1]-1/8*p[4,1]) + (-57/128*p[1,1,1,1,1,1]-83/128*p[2,1,1,1,1]-7/128*p[2,2,1,1]-13/128*p[2,2,2]+5/32*p[4,1,1]-3/32*p[4,2]) + (77/128*p[1,1,1,1,1,1,1]+127/128*p[2,1,1,1,1,1]+27/128*p[2,2,1,1,1]+9/128*p[2,2,2,1]-7/32*p[4,1,1,1]+1/32*p[4,2,1]) + O^8

mantepse · 2022-09-18T16:16:15Z

comment:6

Obviously, there was a parenthesis missing. I thought I changed that already once.

sagetrac-git · 2022-09-18T16:31:48Z

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

`fbccb39`	`normalize degree in Stream_exact for correct equality`
`b20eabf`	`Merge branch 'u/mantepse/categories_of_lazy_series' of trac.sagemath.org:sage into t/34552/more_testsuites_for_lazy_series_rings`
`7cbde49`	`fix reversion of symmetric functions, improve some_elements and tests`

sagetrac-git · 2022-09-18T16:31:48Z

Changed commit from 60f0664 to 7cbde49

sagetrac-git · 2022-09-18T23:37:07Z

Changed commit from 7cbde49 to 6a46183

sagetrac-git · 2022-09-18T23:37:07Z

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

`3d5b8cf`	`Last little things from the patchbot.`
`aa593b5`	`Merge branch 'u/mantepse/categories_of_lazy_series' of https://github.com/sagemath/sagetrac-mirror into u/tscrim/categories_lazy_series-34470`
`840539d`	`More tests, more bugs fixed.`
`b930f58`	`Merge branch 'u/mantepse/categories_of_lazy_series' of https://github.com/sagemath/sagetrac-mirror into u/tscrim/categories_lazy_series-34470`
`6a46183`	`Merge branch 'u/tscrim/categories_lazy_series-34470' of trac.sagemath.org:sage into t/34552/more_testsuites_for_lazy_series_rings`

sagetrac-git · 2022-09-18T23:38:48Z

Changed commit from 6a46183 to b15e36d

sagetrac-git · 2022-09-18T23:38:48Z

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

`b15e36d`	`skip test_revert when base ring is not a field`

sagetrac-git · 2022-09-18T23:46:35Z

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

`8e7b76d`	`fix and simplify wrong doctest`

sagetrac-git · 2022-09-18T23:46:35Z

Changed commit from b15e36d to 8e7b76d

sagetrac-git · 2022-09-19T10:45:55Z

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

`b47407b`	Implementing `_floordiv_`, Stream._true_order to boolean, first fraction field, more tests, marking long tests.
`e077b66`	`Using dynamic classes for FPS gcd.`
`f8ea81b`	`Merge branch 'u/tscrim/categories_lazy_series-34470' of trac.sagemath.org:sage into t/34552/more_testsuites_for_lazy_series_rings`

sagetrac-git · 2022-09-19T10:45:55Z

Changed commit from 8e7b76d to f8ea81b

mantepse · 2022-09-19T13:06:16Z

comment:13

The following should work, but doesn't, because reversion is not lazy enough:

sage: L.<t> = LazyPowerSeriesRing(QQ)
sage: f = L.undefined()
sage: f.define(1+(t*f).revert())

In this case, f should have the coefficients of https://oeis.org/A067145.

tscrim · 2022-09-20T05:53:47Z

comment:14

Replying to Martin Rubey:

The following should work, but doesn't, because reversion is not lazy enough:
sage: L.<t> = LazyPowerSeriesRing(QQ)
sage: f = L.undefined()
sage: f.define(1+(t*f).revert())
In this case, f should have the coefficients of https://oeis.org/A067145.

This one is harder because of the nature of the tests being done. Nothing can be promised about the coefficients of the undefined series. It comes down to how much we want to promise that the code will not break on bad input. I am thinking we can change

-        if not coeff_stream[1]:
+        if coeff_stream._approximate_order > 1:
             raise ValueError("compositional inverse does not exist")
-
-        if coeff_stream[0]:
-            raise ValueError("cannot determine whether the compositional inverse exists")

Then we run into an issue with computing the exact order in Stream_cauchy_invert. So we are doing too many things not lazily enough. (For the invert, we can make _ainv a @lazy_attribute to fix this easily.)

mantepse · 2022-09-20T13:09:45Z

comment:15

In principle, I think it is more important that define works reliably when the input is valid than having helpful error messages. However, silently wrong output is probably equally bad as failures on good input.

For the issue at hand, I think we can rewrite

-        # TODO: shift instead of (self / z) should be more efficient
-        g.define(z / ((self / z)(g)))
+        # the following is mathematically equivalent to
+        # z / ((self / z)(g))
+        # but more efficient and more lazy
+        g.define((~self.shift(-1)(g)).shift(1))

Here is my thinking:

in __invert__, and shift(-1) it is correct to fail on LazyPowerSeries with positive valuation (in contrast to _div_). In particular, f * ~ z is actually bad input for LazyPowerSeries
I don't see how we can (without great effor) avoid the order computation in Stream_cauchy_invert.__init__, when we have no upper bound on the valuation of the input, because it's negative is passed to super().__init__. In our Aldor implementation, Ralf and I created a new domain which allowed computation with "unknowns". I am not sure whether we want this.

sagetrac-git · 2022-09-26T13:49:51Z

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

`1388b8a`	`Merge branch 'u/chapoton/34494' of https://github.com/sagemath/sagetrac-mirror into public/rings/lazy_series_revert-34383`
`7bfe5f7`	`Merge branch 'public/rings/lazy_series_revert-34383' of https://github.com/sagemath/sagetrac-mirror into public/rings/lazy_series_revert-34383`
`2039990`	`Updating doctest due to changes from #34494.`
`cdea820`	`Merge branch 'public/rings/lazy_series_revert-34383' of https://github.com/sagemath/sagetrac-mirror into u/tscrim/derivatives_lazy_series-34413`
`b7f04ed`	`Merge branch 'develop' of trac.sagemath.org:sage into t/34413/derivatives_lazy_series-34413`
`2325826`	`Merge branch 'u/mantepse/derivatives_lazy_series-34413' of trac.sagemath.org:sage into t/34422/implement_functorial_composition_of_lazy_symmetric_functiosn`
`ebcf5c3`	`Merge branch 'u/mantepse/implement_functorial_composition_of_lazy_symmetric_functiosn' of trac.sagemath.org:sage into t/34423/implement_arithmetic_product_of_lazy_symmetric_functions`
`4172688`	`Merge branch 'u/mantepse/implement_arithmetic_product_of_lazy_symmetric_functions' of trac.sagemath.org:sage into t/32367/replace_lazy_power_series-32367`
`41ca99b`	`Merge branch 'u/mantepse/replace_lazy_power_series-32367' of trac.sagemath.org:sage into t/34470/categories_lazy_series-34470`
`fb3a5cd`	`Merge branch 'u/mantepse/categories_lazy_series-34470' of trac.sagemath.org:sage into t/34552/lazy_series_test_suite-34552`

sagetrac-git · 2022-09-26T16:59:01Z

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

`855d2bf`	`remove unused variable`

sagetrac-git · 2022-09-26T16:59:01Z

Changed commit from fb3a5cd to 855d2bf

sagetrac-git · 2022-09-26T17:31:57Z

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

`75c275c`	`add documentation and doctests for _approximate_order`

sagetrac-git · 2022-09-26T17:31:57Z

Changed commit from 855d2bf to 75c275c

mantepse · 2022-09-27T08:46:07Z

comment:58

Essentially green bot.

The pyflakes warnings local variable 'res' is assigned to but never used are from #34345. Should I fix them here or elsewhere?

mantepse · 2022-09-27T08:56:47Z

comment:59

The codestylecheck warnings are as follows:

sage/rings/lazy_series.py:843:21: E711 comparison to None should be 'if cond is None:'
sage/rings/lazy_series.py:961:17: E711 comparison to None should be 'if cond is None:'
sage/rings/lazy_series.py:5452:9: E306 expected 1 blank line before a nested definition, found 0

The first two wouldn't work with is, because an option only compares equal to None:

            prec = self.parent().options.halting_precision
            if prec == None:
                raise ValueError("undecidable")

The E306 I disagree with, I am setting the "local" variables for the local function definition. (X is used later, but looks best at this spot)

        la = Partition([1])
        X = R(la)
        def coefficient(n):
            if n:
                return 0
            c = coeff_stream[1][la]
            if c.is_unit():
                return ~c
            raise ValueError("compositional inverse does not exist")

mantepse · 2022-09-27T08:57:49Z

comment:60

It is interesting that the github bots will not detect the unused variables.

fchapoton · 2022-09-29T10:09:19Z

comment:61

Sorry, but the linter must pass, no choice. Even if E306 is in some sense a matter of taste, it is currently required. Your def without empty line before would be the only one in the whole sage code base.

About the comparison to None, this is very strange. Could you use "if not prec" instead ? or some isinstance ? What is the type of "prec" that is equal but not None ?

mantepse · 2022-09-29T10:21:45Z

comment:62

Hi Frédéric!

Concerning the second question:

sage: L.<z> = LazyLaurentSeriesRing(QQ)
sage: L.options.halting_precision
None
sage: type(L.options.halting_precision)
<class 'sage.structure.global_options.Option'>
sage: L.options.halting_precision == None
True
sage: L.options.halting_precision is None
False

mantepse · 2022-09-29T10:24:01Z

comment:63

I'll add the missing line.

Could you please also respond to comment:58?

(these pyflakes warnings were missed in a completely unrelated ticket)

fchapoton · 2022-09-29T11:56:40Z

comment:64

the pyflakes warning are not your responsability, but you can fix them if you want

For the comparison to None, maybe this could fixed using the complicated syntax

sage: op = L.options.constant_length
sage: op._options[op._name]
3
sage: type(_)
<class 'int'>

or by adding in general a way to extract the bare value of an option somehow.

fchapoton · 2022-09-29T12:02:55Z

comment:65

simpler:

sage: Q=L.options
sage: type(Q['constant_length'])
<class 'int'>

sagetrac-git · 2022-09-29T13:13:56Z

Changed commit from 75c275c to 5393242

sagetrac-git · 2022-09-29T13:13:56Z

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

`5393242`	`fixes for pycodestyle and pyflakes`

mantepse · 2022-09-29T13:14:27Z

comment:67

Cool, thank you!

sagetrac-git · 2022-10-05T15:34:46Z

Changed commit from 5393242 to 3e84c90

sagetrac-git · 2022-10-05T15:34:46Z

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

`67dff95`	`Merge branch 'develop' of trac.sagemath.org:sage into t/32367/replace_lazy_power_series-32367`
`4fc981b`	`fix for pyflakes and blocks`
`56cef07`	`Merge branch 'u/mantepse/replace_lazy_power_series-32367' of trac.sagemath.org:sage into t/34470/categories_lazy_series-34470`
`3e84c90`	`Merge branch 'u/mantepse/categories_lazy_series-34470' of trac.sagemath.org:sage into t/34552/lazy_series_test_suite-34552`

tscrim · 2022-10-11T00:03:04Z

Reviewer: Travis Scrimshaw, Frédéric Chapoton

tscrim · 2022-10-11T00:03:04Z

comment:69

I am assuming Frédéric is now happy. LGTM. We can do more on further tickets.

vbraun · 2022-10-16T22:15:51Z

Changed branch from u/mantepse/lazy_series_test_suite-34552 to 3e84c90

mantepse added this to the sage-9.8 milestone Sep 18, 2022

mantepse added the p: major / 3 label Sep 18, 2022

This comment has been minimized.

Sign in to view

mantepse added t: enhancement labels Sep 18, 2022

tscrim added s: positive review and removed s: needs review labels Oct 11, 2022

vbraun removed the s: positive review label Oct 16, 2022

vbraun closed this as completed in 321f970 Oct 16, 2022

This was referenced Jan 29, 2023

improve performance of Stream_cauchy_invert #34553

Closed

improve approximate order on __getitem__ calls #34556

Closed

fast implementation of exp #34611

Closed

make sparsity a decision of the user #34636

Closed

vbraun mentioned this issue Oct 11, 2022

fix more W605 in rings #34645

Closed

more testsuites for lazy series rings #34552

more testsuites for lazy series rings #34552

Comments

mantepse commented Sep 18, 2022

mantepse commented Sep 18, 2022

This comment has been minimized.

mantepse commented Sep 18, 2022

mantepse commented Sep 18, 2022

mantepse commented Sep 18, 2022

mantepse commented Sep 18, 2022

mantepse commented Sep 18, 2022

sagetrac-git mannequin commented Sep 18, 2022

sagetrac-git mannequin commented Sep 18, 2022

sagetrac-git mannequin commented Sep 18, 2022

sagetrac-git mannequin commented Sep 18, 2022

mantepse commented Sep 18, 2022

mantepse commented Sep 18, 2022

sagetrac-git mannequin commented Sep 18, 2022

sagetrac-git mannequin commented Sep 18, 2022

sagetrac-git mannequin commented Sep 18, 2022

sagetrac-git mannequin commented Sep 18, 2022

sagetrac-git mannequin commented Sep 18, 2022

sagetrac-git mannequin commented Sep 18, 2022

sagetrac-git mannequin commented Sep 18, 2022

sagetrac-git mannequin commented Sep 18, 2022

sagetrac-git mannequin commented Sep 19, 2022

sagetrac-git mannequin commented Sep 19, 2022

mantepse commented Sep 19, 2022

tscrim commented Sep 20, 2022

mantepse commented Sep 20, 2022

sagetrac-git mannequin commented Sep 26, 2022

sagetrac-git mannequin commented Sep 26, 2022

sagetrac-git mannequin commented Sep 26, 2022

sagetrac-git mannequin commented Sep 26, 2022

sagetrac-git mannequin commented Sep 26, 2022

mantepse commented Sep 27, 2022

mantepse commented Sep 27, 2022

mantepse commented Sep 27, 2022

fchapoton commented Sep 29, 2022

mantepse commented Sep 29, 2022

mantepse commented Sep 29, 2022

fchapoton commented Sep 29, 2022

fchapoton commented Sep 29, 2022

sagetrac-git mannequin commented Sep 29, 2022

sagetrac-git mannequin commented Sep 29, 2022

mantepse commented Sep 29, 2022

sagetrac-git mannequin commented Oct 5, 2022

sagetrac-git mannequin commented Oct 5, 2022

tscrim commented Oct 11, 2022

tscrim commented Oct 11, 2022

vbraun commented Oct 16, 2022