Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

k-recursive sequences with inhomogeneities #32921

Closed
galipnik opened this issue Nov 22, 2021 · 53 comments
Closed

k-recursive sequences with inhomogeneities #32921

galipnik opened this issue Nov 22, 2021 · 53 comments
Labels
c: combinatorics p: major / 3 t: enhancement
Milestone
sage-9.8

Comments

@galipnik
Copy link

Implement k-recursive sequences with inhomogeneities as described in Corollary D of the paper "Asymptotic Analysis of q-Recursive Sequences".

See also meta ticket #21202.

Depends on #21319
Depends on #21325
Depends on #31787

CC: @cheuberg @dkrenn

Component: combinatorics

Author: Gabriel F. Lipnik

Branch/Commit: e2d8f1d

Reviewer: Clemens Heuberger

Issue created by migration from https://trac.sagemath.org/ticket/32921
@galipnik galipnik added this to the sage-9.5 milestone Nov 22, 2021
@mkoeppe mkoeppe modified the milestones: sage-9.5, sage-9.6 Dec 18, 2021
@galipnik
Copy link
Author

Branch: u/galipnik/k-regular-from-recurrence-inhomogeneities

@galipnik
Copy link
Author

Commit: 0eff52e

@galipnik
Copy link
Author

Changed dependencies from #31787 to #21325, #31787

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jan 11, 2022

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

2dd7c48Trac #31787: reformulate one example with keyword arguments only
13e3c81Merge remote-tracking branch 'origin/u/galipnik/k-regular-from-recurrence-alternative-args' into u/galipnik/k-regular-from-recurrence-inhomogeneities
3ba04e7Trac 32921: add optional keyword-only argument inhomogeneities
976ac29Trac 32921: add inhomogeneities to values-method
6837137Trac #32921: add inhomogeneities to left-method
22c5f0bTrac #32921: add inhomogeneities to right-method
53c6b58Trac #32921: first draft for matrices
9a39964Trac #32921: add examples/tests
cee66a6Trac #32921: add keywords to old test
b1f2b71Trac #32921: use is_trivial_zero in old example

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jan 11, 2022

Changed commit from 0eff52e to b1f2b71

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jan 11, 2022

Changed commit from b1f2b71 to 7e4ac44

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jan 11, 2022

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

7e4ac44Trac #32921: add random example with imhomogeneities only

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jan 12, 2022

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

59479e5Trac #32921: add some tests
6bc9c11Trac #32921: minor modifications in tests
60f7602Trac #32921: fix issue for left vector
49363c7Trac #32921: deactivate minimization for now
a65412eTrac #32921: shift parts from right to v_eval_n
e10abb3Trac #32921: fix offset correction
268fe7cTrac #32921: add further example
54bc5dbTrac #32921: simplify construction of matrix
25d5398Trac #32921: add inhomogeneities to docstring

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jan 12, 2022

Changed commit from 7e4ac44 to 25d5398

@cheuberg
Copy link
Contributor

comment:7

I had a look at this branch and have some comments.

  1. line 1042: would (S - T).is_trivial_zero() work if kRegularSequence: minimization wrong #33158 is merged?

  2. from_recurrence: parameter inhomogeneities: please mention default value {} in docstring.

  3. RecurrenceParser.parameters: parameter inhomogeneities: I do not think that the last sentence "All inhomogeneities have to be regular sequences from self." is appropriate here. Also mentioning the default seems to be unusual in an output section.

  4. RecurrenceParser.values: parameter inhomogeneities: I do not think that the last sentence "All inhomogeneities have to be regular sequences from self." is appropriate here.

  5. RecurrenceParser.v_eval_n: In the new code at the end, I am surprised that n does not occur in shifted_inhomogeneities at all.

  6. RecurrenceParser.v_eval_n: In the new code at the end, I am not convinced that upper + 1 is the correct second argument for srange: The paper contains an additional +1 in what translates to upper here.

  7. RecurrenceParser.matrix: Is minimize=False a tribute to kRegularSequence: minimization wrong #33158?

  8. RecurrenceParser.matrix: Same comment as 6.

  9. RecurrenceParser.matrix: for the second case, there is twice rem_d - k whereas the paper has rem_d - k^M

  10. RecurrenceParser.matrix: setting 1 into the matrix silently assumes that the left vector of the shifted inhomogeneity is (1, 0, ... ,0). This may not be the case (subsequence will copy the left vector of the inhomogeneity to the shifted version). So at least we have to check that this assumption holds, at best we would transform the linear representation of the inhomogeneity such that the condition holds. (choose a matrix T such that right multiplication of the existing left vector by T leads to the desired left vector, replace all matrices by T^{-1} times the matrix times T and multiply the right vector by T^{-1} from the left; all that should probably be a separate method of regular sequences). Alternatively, simply copying the left vector into the correct position might do the job.

  11. RecurrenceParser.matrix: this code might be rather inefficient: The vector constructed by subsequence(1, b) will consist of several shifted versions of the inhomogeneity. So when calling subsequence(1, b) for adjacent values of b, chances are very high that there will be a noticeable overlap in the vectors constructed, which results in substantial redundancy. The method subsequence has provisions for computing several shifts at the same time (for linear combinations). So it would be advantageous to modify subsequence to also allow b to be a list (not only a scalar or a dictionary); it is currently unclear what the best return value would be in that case. Or one might simply take the existing version of subsequence with some dummy coefficients and throw away the left vector because it will be zero in this application, anyways.

  12. Overall, all the parameters of the shifted inhomogeneities are computed thrice: in v_eval_n, in matrix, in left (see comments 6 and 8). This seems to be repetitive, error-prone and inefficient (because subsequence is called repeatedly). Therefore, I suggest to factor out these computations to a new method.

  13. I have the impression that the code in RecurrenceParser.matrix could be somewhat simplified by not computing exact indices for the entries, but by constructing block matrices in a suitable way, see also #21325 comment:29 for a related discussion.

  14. from_recurrence: in the example where one is constructed explicitly for the sum of digits function (currently line 910): I think that https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/recognizable_series.html#sage.combinat.recognizable_series.RecognizableSeriesSpace.one_hadamard would do the job out of the box.

@cheuberg
Copy link
Contributor

Reviewer: Clemens Heuberger

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jan 18, 2022

Changed commit from 25d5398 to 48ebcc4

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jan 18, 2022

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

daaf4d6Trac #33158: doctest fix and original issued posted on ticket
4002436Merge branch 'u/dkrenn/coeffs-in-from-recurrence' into u/galipnik/k-regular-from-recurrence-inhomogeneities
997c5ccTrac #32921, review item 2: mention default value
dd4f2f6Trac #32921, review item 3: adapt descrition of output
87a3cfbTrac #32921, review item 4: adapt description of input
f4356b2Trac #32921, review item 9: fix index
03cc1b4Trac #32921, review item 14: use one_hadamard
97fbbddTrac #32921, review item 5: fix missing n
f480738Trac #32921, review item 12: write new method
48ebcc4Trac #32921, review item 12: modify method for matrix-construction (could be reverted)

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jan 19, 2022

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

b674000Trac #32921, review item 10: add minimize=True

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jan 19, 2022

Changed commit from 48ebcc4 to b674000

@galipnik
Copy link
Author

comment:10

Replying to @cheuberg:

I had a look at this branch and have some comments.

Thank you very much for your review!

  1. from_recurrence: parameter inhomogeneities: please mention default value {} in docstring.

Done.

  1. RecurrenceParser.parameters: parameter inhomogeneities: I do not think that the last sentence "All inhomogeneities have to be regular sequences from self." is appropriate here. Also mentioning the default seems to be unusual in an output section.

Removed.

  1. RecurrenceParser.values: parameter inhomogeneities: I do not think that the last sentence "All inhomogeneities have to be regular sequences from self." is appropriate here.

Removed.

  1. RecurrenceParser.v_eval_n: In the new code at the end, I am surprised that n does not occur in shifted_inhomogeneities at all.

Fixed.

  1. RecurrenceParser.v_eval_n: In the new code at the end, I am not convinced that upper + 1 is the correct second argument for srange: The paper contains an additional +1 in what translates to upper here.

I am not really convinced by your argument: In the first case in the paper, there is no additional +1, which should lead to upper + 1 here. Am I missing something? (Or have you checked that upper cannot be reached in the first case? I have not, but maybe I should...)

  1. RecurrenceParser.matrix: Is minimize=False a tribute to kRegularSequence: minimization wrong #33158?

Yes, removed.

  1. RecurrenceParser.matrix: Same comment as 6.

  2. RecurrenceParser.matrix: for the second case, there is twice rem_d - k whereas the paper has rem_d - k^M

Fixed.

  1. RecurrenceParser.matrix: setting 1 into the matrix silently assumes that the left vector of the shifted inhomogeneity is (1, 0, ... ,0). This may not be the case (subsequence will copy the left vector of the inhomogeneity to the shifted version). So at least we have to check that this assumption holds, at best we would transform the linear representation of the inhomogeneity such that the condition holds. ...

The method RecognizableSeries.minimized should guarantee this (by line 1076 in recognizable_series.py). So if we use kRegularSequence.subsequence with minimize=True, we are on the safe side, right? I have included an assert to check this now.

  1. Overall, all the parameters of the shifted inhomogeneities are computed thrice: in v_eval_n, in matrix, in left (see comments 6 and 8). This seems to be repetitive, error-prone and inefficient (because subsequence is called repeatedly). Therefore, I suggest to factor out these computations to a new method.

Done. (I am not sure what the best output of the new method is; see after commit 48ebcc4 and before.)

  1. from_recurrence: in the example where one is constructed explicitly for the sum of digits function (currently line 910): I think that https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/recognizable_series.html#sage.combinat.recognizable_series.RecognizableSeriesSpace.one_hadamard would do the job out of the box.

Done.

One test still fails, I have to fix this.

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jan 19, 2022

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

df04b44Trac #32921: use assert really as statement...

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jan 19, 2022

Changed commit from b674000 to df04b44

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jan 19, 2022

Changed commit from df04b44 to f5b81af

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jan 19, 2022

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

8d1721dTrac #32921, review item 10: simplify assert
1f73dfeTrac #32921, review item 10: mention standard unit vector in documentation
e505a43Trac #32921, review item 6: fix upper bound
0f2f415Trac #32921: fix copy/paste error in test...
f5b81afTrac #32921: simplify construction of matrix and right vector

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jan 19, 2022

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

6294eb1Trac #32921: allow constants as inhomogeneities, add tests for input

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Feb 1, 2022

Changed commit from fdb70b7 to 7e3cc70

@galipnik
Copy link
Author

galipnik commented Feb 1, 2022

Changed dependencies from #21325, #31787 to #21319, #21325, #31787

@galipnik
Copy link
Author

galipnik commented Feb 1, 2022

comment:23

Replying to @cheuberg:

  1. The new sequence avoids this problem, thank you. It seems that the old sequence was invalid because mu[0] * right was not equal to right. This should be checked (and there is deal with bad chosen representations of k-regular sequences #21343 to do so). It seems that minimization does not perform as advertised in such a case because it yields a minimal linear representation for the recognizable series instead of the regular sequence. In fact, the recognizable series given by the old linear representation had non-zero coefficients for some words with trailing zeros.

For the sake of completeness: More details in https://arxiv.org/abs/2201.13446.

  1. I think that the docstring should contain a short description on how the dictionary works (what are the keys, what are the values)

Draft in commit 8210a2b0.

  1. RecurrenceParser.shifted_inhomogeneities does some non-trivial operations (minimization is turned off, but still). Therefore, caching seems to be worthwhile. My understanding (see https://doc.sagemath.org/html/en/reference/misc/sage/misc/cachefunc.html#sage.misc.cachefunc.CachedMethod) is that the key parameter of cached_method would be useful, probably as a lambda which generates a tuple consisting of those parts of recurrence_rules which are actually used, transforming the dictionary inhomogeneities to tuple(rules.inhomogeneities.items()) or so.

    Unfortunately, this induces a dependency on recognizable series: hash, comparison, TestSuite #21319.

Thank you for the hint! Code added in commit 98d2719a, new dependency #21319 merged.

@mkoeppe mkoeppe modified the milestones: sage-9.6, sage-9.7 Apr 2, 2022
@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented May 24, 2022

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

f213959Merge branch 'public/ticket/21319' into u/galipnik/k-regular-from-recurrence-inhomogeneities

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented May 24, 2022

Changed commit from 7e3cc70 to f213959

@galipnik
Copy link
Author

comment:26

Dependency merged and conflict in L2829 and L2918/L2919 resolved.

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented May 25, 2022

Changed commit from f213959 to 3bcf072

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented May 25, 2022

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

9e8b899pyflakes: remove unused imports
3bcf072fix some error from resolving the merge conflict

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented May 30, 2022

Changed commit from 3bcf072 to 5695619

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented May 30, 2022

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

1954babuse zero sequence instead of Seq3.some_elements()[0] in some test
5695619add subdivide=False two times

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Aug 23, 2022

Changed commit from 5695619 to dccf4ac

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Aug 23, 2022

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

dccf4acMerge tag '9.7.beta7' into u/galipnik/k-regular-from-recurrence-inhomogeneities

@cheuberg
Copy link
Contributor

Changed branch from u/galipnik/k-regular-from-recurrence-inhomogeneities to u/cheuberg/k-regular-from-recurrence-inhomogeneities

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Sep 19, 2022

Changed commit from dccf4ac to e2d8f1d

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Sep 19, 2022

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

bac7eb4Trac #32921: Show full output in example for shifted_inhomogeneities
e2d8f1dTrac #32921: `shifted_inhomogeneities`: doctest demonstrating blocks

@cheuberg
Copy link
Contributor

comment:32

  1. I think that the sentence in the description of the output is hard to understand, but I have no idea for improvement.

    Therefore I propose to explain it via a doctest, see e2d8f1d.

@mkoeppe mkoeppe modified the milestones: sage-9.7, sage-9.8 Sep 19, 2022
@galipnik
Copy link
Author

comment:34

The two new commits LGTM, thank you!

@cheuberg
Copy link
Contributor

comment:35

The build failures detected by the github action seem to be completely unrelated to this branch; the patchbot, on the other hand, is happy.

So, time to set it to positive.

@vbraun
Copy link
Member

vbraun commented Sep 25, 2022

Changed branch from u/cheuberg/k-regular-from-recurrence-inhomogeneities to e2d8f1d

@vbraun vbraun closed this as completed in cb6cda6 Sep 25, 2022
@dkrenn dkrenn mentioned this issue Dec 29, 2022
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
c: combinatorics p: major / 3 t: enhancement
Projects
None yet
Milestone
sage-9.8
Development

No branches or pull requests
4 participants
@vbraun @mkoeppe @cheuberg @galipnik