make sparsity a decision of the user

[mantepse]

The decision whether a Stream_XXX class uses a dense or a sparse cache should not depend on the input streams.

For example, for Stream_add it is actually irrelevant whether the input streams left and right are dense or sparse.

For Stream_zero and Stream_exact, a separate cache never makes sense.

This also makes the need to implement a conversion between sparse and dense less important.

Depends on #34552
Depends on #34653

CC: @tscrim @fchapoton

Component: combinatorics

Keywords: LazyPowerSeries

Author: Martin Rubey

Branch/Commit: de424bd

Reviewer: Travis Scrimshaw

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

[mantepse]

Branch: u/mantepse/make_sparsity_a_decision_of_the_user

[mantepse]

Changed keywords from none to LazyPowerSeries

[mantepse]

Author: Martin Rubey

[mantepse]

Commit: bd3e3eb

[mantepse]

Last 10 new commits:

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
855d2bf	remove unused variable
75c275c	add documentation and doctests for _approximate_order
5393242	fixes for pycodestyle and pyflakes
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
bd3e3eb	make sparsity a decision of the user

[mantepse]

Dependencies: #34552

[mantepse]

comment:4

A sparse representation does not make sense also for Cauchy_invert: get_coefficient accesses all previously computed values.

[sagetrac-git]

Changed commit from bd3e3eb to 814aa7c

[sagetrac-git]

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

814aa7c

remove Stream_cauchy_invert.get_coefficient, make sparse a mandatory argument, move _is_sparse an attribute of Stream_inexact

[sagetrac-git]

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

7043d1c

remove redundant `__init__` methods, remove finished TODOs

[sagetrac-git]

Changed commit from 814aa7c to 7043d1c

[mantepse]

comment:8

From #34611: it may make sense to make Stream_uninitialized always dense, and doctest that the following then works:

sage: L.<z> = LazyPowerSeriesRing(ZZ); C = L.undefined(); C.define(1 + z*C^2)
sage: C[500]

Another question: it may make sense to make Stream_XXX always sparse, if the computation of s[n] obviously does not benefit from the values of s[n-1], s[n-2], .... This is the case, for example, with Stream_add.

The benefit of a dense representation of Stream_add may be in storage and access: if we have a sparse representation and have to compute most values, the list representation uses (much) less memory, and access will be faster. For example, storing the first 600 values of a stream of integers as a list uses no more memory than storing 200 values in a dict. Lookup in a list of about 1000 elements seems to take about 60%-70% of the time lookup in a dictionary takes.

In cases when we apply a very simple function to each coefficient, as in Stream_neg, we may not want to create a separate cache at all. For Stream_map_coefficients, we currently only apply very costly functions.

[tscrim]

comment:9

I am wondering how much we even want the sparsity in the streams. We want it for the exact series in some cases (sparse versus dense for the (Laurent) polynomial ring), but it seems more like extra weight we are carrying around for the streams, which should instead simply be as dense or sparse as is most effective for them. Or maybe just for multiplication, which might be the only one that could matter? Do you remember if in any place we take advantage of the dense or sparse implementation currently?

[mantepse]

comment:10

I don't think we can decide for the user. For multiplication it makes a big difference, whether you are only interested in (f*g)[10000] or in (f*g)[:10000]. The former may be relevant, if you want to compute a few random coefficients, e.g., to quickly see how much they grow. But I admit that I do not know any serious application.

Exact series are neither sparse nor dense in the sense of Stream, they implement their own (mixed) cache: an index and a list for the initial coefficients, and an index and a constant for the rest.

I am not completely sure whether I understand your question. I think that Stream_mul, Stream_cauchy_compose and the like should have sparse and dense versions. Stream_uninitialized probably only a dense version, Stream_add, Stream_sub, etc. possibly only a sparse version.

The only two reasons for Stream_add etc. to have a dense version is, if the speedup in access and the memory overhead matter. There is no additional code. So I guess it is better to keep the option. We currently only use subtraction, implicitly in LazySymmetricFunction.revert:

        g = P.undefined(valuation=1)
        g.define(b_inv * (X - (self - b * X)(g)))

I am guessing (but I am not sure) that it makes sense to use either only the sparse versions or only the dense versions of the operations here.

[tscrim]

comment:11

You’re right; for multiplication, we should have both a sparse and dense version.

Ah, right, we don’t store the polynomials themselves in the Stream_exact, although there can be uses for passing the sparsity to that. I don’t remember if we implement both types of exact storage. Perhaps we should, in case someone wants to create x¹⁰⁰⁰⁰.

I am mostly wondering how much we should drop within the streams to carry around the _sparse parameter altogether. The multiplication will likely be split into 2 classes (with not being too lazy with the dense multiplication); the rest, except possibly the exact, are all naturally either dense (e.g., inverse) or sparse (e.g., addition).

I will have to look at the code we currently have more closely I think to get a more clear picture. I don’t remember some of the details regarding this. Perhaps you already have a clear picture about this though.

[mantepse]

comment:12

Creating z¹⁰⁰⁰⁰ is not a problem:

sage: L.<z> = LazyPowerSeriesRing(ZZ)
sage: f = z^100000
sage: f._coeff_stream.__dict__
{'_constant': 0,
 '_degree': 100001,
 '_initial_coefficients': (1,),
 '_true_order': True,
 '_approximate_order': 100000}

however, z¹⁰⁰⁰⁰⁰-1 is:

sage: f = z^10 - 1
sage: f._coeff_stream.__dict__
{'_constant': 0,
 '_degree': 11,
 '_initial_coefficients': (-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1),
 '_true_order': True,
 '_approximate_order': 0}

Curiously, it takes a very long time to create, all of which is spent in the polynomial exponentiation - this is, because the underlying polynomial ring, for some reason is always dense:

class LazyLaurentSeriesRing(LazySeriesRing):
    def __init__(self, base_ring, names, sparse=True, category=None):
        self._sparse = sparse
        # We always use the dense because our CS_exact is implemented densely
        self._laurent_poly_ring = LaurentPolynomialRing(base_ring, names)
        self._internal_poly_ring = self._laurent_poly_ring

There are actually two easy improvements:

• a sparse version, so we can create 1 + x^100000000
• I think that the polynomial ring should be dense or sparse depending on our input

and, orthogonal to this,

• a lazy version of Stream_exact, with coefficients provided by a function, might also help with the problem of computing large powers or large compositions of exact series.

I can imagine that having only sparse addition is bad. I can try to create an example if you want.

What I'd be interested in is some help with van der Hoeven's algorithm in #34616.

[sagetrac-git]

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

e6c4cae

make Stream_uninitialized always dense to avoid maximal recursion error

[sagetrac-git]

Changed commit from 7043d1c to e6c4cae

[sagetrac-git]

Changed commit from e6c4cae to de424bd

[sagetrac-git]

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

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

[mantepse]

comment:15

I made the internal polynomial rings sparse or dense according to the lazy series ring, although this really is of very little consequence.

Essentially, creating z¹⁰⁰⁰⁰⁰ is now fast in the sparse case, and some computations for exact series (powers, compositions) are now carried out with sparse polynomials. I did not check, however, whether this makes sense. We actually do not use the polynomial rings so much, not even for multiplication.

A completely sparse version of Stream_exact should be easy, I think - in the non-lazy setting we would simply have a dictionary of non-zero coefficients.

[mantepse]

comment:16

Although having a sparse version of Stream_exact should be easy, taking advantage of it may be much more work, because currently we always compute a list of initial coefficients in lazy_ring.py.

I very much doubt that it is worth the effort right now.

[tscrim]

comment:17

The dense Laurent polynomials might be a bit better at creating z¹⁰⁰⁰⁰ than the usual polynomials as they factor out the valuation portion.

It might not be so prudent to spend time implementing a sparse version of Stream_exact right now actually. There will be some additional changes needed throughout the code (this might indicate that we need to refactor so the stream can handle more things in its construction method). There are plenty of other things that we can do to improve the speed and efficiency that are likely to be more useful to people.

[mantepse]

Changed dependencies from #34552 to #34552, #34653

[tscrim]

comment:19

Let us move along. This is definitely an improvement, and we can do further work on subsequent tickets.

[tscrim]

Reviewer: Travis Scrimshaw

[vbraun]

Changed branch from u/mantepse/make_sparsity_a_decision_of_the_user to de424bd