refactor multiple zeta values

[fchapoton]

This ticket mainly aims to separate the auxiliary F-algebra in another file.

This file implements a better custom-made F-algebra, with additional useful methods.

CC: @videlec @tscrim

Component: number theory

Author: Frédéric Chapoton

Branch/Commit: 8a8cdf3

Reviewer: Travis Scrimshaw

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

[fchapoton]

New commits:

f8a5eea

refactor MZV using a new file for a better auxiliary F_algebra

[fchapoton]

Commit: f8a5eea

[fchapoton]

Branch: u/chapoton/34562

[tscrim]

comment:2

Some quick comments about the F_algebra:

• The element's coefficients should return the nonzero coefficients, but the current implementation has different behavior.
• There should be a from_vector method on the parent. This is useful for the linear algebra methods.
• The NN can be a little funky when it comes to lazy imports not resolving correctly (lazy_import doesn't resolve properly when indirectly imported #16522). It would be better to use NonNegativeIntegers() unless you specifically are looking for the algebraic aspects.
• Is there a reason why you are nailing Indices in the module level memory? It seems like the str_to_index is better as a method of the F_algebra and then you could access it by self._indices there (or self.parent()._indices).
• Instead of the recursive basis_f_odd_iterator, is it faster to use the iterators from WeightedIntegerVectors and Permutations_mset (which operate on lists)? It is a slightly more involved implementation, but I don't know how important speed is here.
• For the product_on_basis, it might be faster to do self.sum() since it works with the elements directly and has less transient elements.

[sagetrac-git]

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

3b06406

using NonNegativeIntegers instead of NN

[sagetrac-git]

Changed commit from f8a5eea to 3b06406

[sagetrac-git]

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

c447fc2	Merge branch 'u/chapoton/34562' in 9.7
c7b3fee	remove wrong alias for coefficients

[sagetrac-git]

Changed commit from 3b06406 to c7b3fee

[fchapoton]

comment:5

Hello,

thanks a lot for the suggestions !

• The element's coefficients should return the nonzero coefficients, but the current implementation has different behavior.

ok, done by removing the wrong alias that I had added.

• There should be a from_vector method on the parent. This is useful for the linear algebra methods.

well, the difficulty is that it only makes sense for homogeneous elements, and the usual "from_vector" methods does not take the degree as input

• The NN can be a little funky when it comes to lazy imports not resolving correctly (lazy_import doesn't resolve properly when indirectly imported #16522). It would be better to use NonNegativeIntegers() unless you specifically are looking for the algebraic aspects.

I substituted that for NN and it works fine.

• Is there a reason why you are nailing Indices in the module level memory? It seems like the str_to_index is better as a method of the F_algebra and then you could access it by self._indices there (or self.parent()._indices).

I would rather keep "str_to_index" as an independant auxiliary function. Why is it problematic to have Indices at the module level ? oh, I guess it will have to be initiated when the module is loaded..

• Instead of the recursive basis_f_odd_iterator, is it faster to use the iterators from WeightedIntegerVectors and Permutations_mset (which operate on lists)? It is a slightly more involved implementation, but I don't know how important speed is here.

Not sure how to achieve "words of any length in odd integers at least 3 with sum n" using the existing tools. And speed generally matters in this file, indeed.

• For the product_on_basis, it might be faster to do self.sum() since it works with the elements directly and has less transient elements.

I have not yet checked that last suggestion.

[sagetrac-git]

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

0a56256

implement and use attribute _indices in F-algebra

[sagetrac-git]

Changed commit from c7b3fee to 0a56256

[sagetrac-git]

Changed commit from 0a56256 to 6f11059

[sagetrac-git]

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

6f11059

using sum_of_monomials

[tscrim]

comment:8

Replying to Frédéric Chapoton:

thanks a lot for the suggestions !

Thank you for all your work on Sage.

• There should be a from_vector method on the parent. This is useful for the linear algebra methods.

well, the difficulty is that it only makes sense for homogeneous elements, and the usual "from_vector" methods does not take the degree as input

I see. This breaks the CFM.from_vector(v.to_vector()) == v loop though (although that is more for finite dimensional modules). Perhaps we could rename this here to homogeneous_to_vector() to make it more future-proof (if we implement a generic infinite dimensional version someday)?

• Is there a reason why you are nailing Indices in the module level memory? It seems like the str_to_index is better as a method of the F_algebra and then you could access it by self._indices there (or self.parent()._indices).

I would rather keep "str_to_index" as an independant auxiliary function. Why is it problematic to have Indices at the module level ? oh, I guess it will have to be initiated when the module is loaded..

Subsequently it effectively gets nailed in memory. It's fairly lightweight (and only one of them), so its not a problem, but it still is something that gets carried around.

Also, you shouldn't need to set self._indices = Indices; that should be done by the CFM.__init__().

• Instead of the recursive basis_f_odd_iterator, is it faster to use the iterators from WeightedIntegerVectors and Permutations_mset (which operate on lists)? It is a slightly more involved implementation, but I don't know how important speed is here.

Not sure how to achieve "words of any length in odd integers at least 3 with sum n" using the existing tools. And speed generally matters in this file, indeed.

If speed matters, then perhaps we should just Cythonize the file. It would allow you to replace the self.parent() with self._parent, which is faster.

Perhaps iterating over the indices is not such an important operation for speed. Although it might be best to use lightweight classes (e.g., tuple) and implement shuffling without using the heavy ShuffleProduct_w1w2 parent class. This becomes something like

    def shuffle(t1, t2):
        n1 = len(t1)
        n2 = len(t2)
        for iv in IntegerVectors(n1, n1 + n2, max_part=1): # can probably even make this iterator smarter
            it1 = iter(t1)
            it2 = iter(t2)
            yield tuple([next(it1) if v else next(it2) for v in iv])

• For the product_on_basis, it might be faster to do self.sum() since it works with the elements directly and has less transient elements.

I have not yet checked that last suggestion.

Your changes look like they should be faster. Even more so if we can make the indices involve less transient objects and/or checks.

[sagetrac-git]

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

d5ee67d

using homogeneous_to_vector and homogeneous_from_vector

[sagetrac-git]

Changed commit from 6f11059 to d5ee67d

[sagetrac-git]

Changed commit from d5ee67d to 5df08cb

[sagetrac-git]

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

7d395b5	remove duplicate code
5df08cb	simplify code a little bit in MZV

[sagetrac-git]

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

4bdced9

small detail in MZV

[sagetrac-git]

Changed commit from 5df08cb to 4bdced9

[sagetrac-git]

Changed commit from 4bdced9 to 7661288

[sagetrac-git]

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

7661288

a few more details in MZV

[sagetrac-git]

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

63695d7

more fine-tuning details in MZV

[sagetrac-git]

Changed commit from 7661288 to 63695d7

[fchapoton]

comment:14

I guess it is now ready for review again.

[fchapoton]

comment:15

maybe one should simplify (in F_algebra) the double method "gen" versus "custom_gen" ?

[tscrim]

comment:16

It does look a bit weird to have both gen and custom_gen. Is there a reason to have both? Perhaps it could be a little better with a different name than custom_gen? I am not sure what a good name might be though.

[sagetrac-git]

Changed commit from 63695d7 to 6b80c50

[sagetrac-git]

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

6b80c50

get rid of custom_gen, now gen

[fchapoton]

comment:18

So I have removed the previous method "gen" (rather useless and not natural) and renamed "custom_gen" to "gen".

[sagetrac-git]

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

cac2291

using IntegerRange in MZV itself

[sagetrac-git]

Changed commit from 6b80c50 to cac2291

[tscrim]

comment:20

Thank you.

Do we want to use IntegerRange rather than the more specific NonNegativeIntegers()? This would also make it different than F_algebra (not that they need to be the same).

I think other than that, I would be happy to set a positive review (unless there are other changes you want to make).

[fchapoton]

comment:21

Well, I want to exclude 0. No idea what nonnegative means, as always.

[tscrim]

comment:22

Ah, right. Duh. Then how about PositiveIntegers()?

[sagetrac-git]

Changed commit from cac2291 to 8a8cdf3

[sagetrac-git]

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

8a8cdf3

using PositiveIntegers

[fchapoton]

comment:24

Indeed, now using PositiveIntegers.

I think I have no further changes to make.

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:25

Thanks. LGTM.

[vbraun]

Changed branch from u/chapoton/34562 to 8a8cdf3