Opened 6 years ago

Closed 13 months ago

#10519 closed enhancement (fixed)

analytic combinatorics: new code for computing asymptotics for multivariate generating functions

Reported by: araichev Owned by: sage-combinat
Priority: major Milestone: sage-7.1
Component: combinatorics Keywords: analytic combinatorics, multivariate generating functions, asymptotics
Cc: cyril.banderier, zaf, tmonteil, dkrenn, behackl Merged in:
Authors: Daniel Krenn, Alex Raichev Reviewers: Daniel Krenn, David Loeffler, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: a951f08 (Commits) Commit: a951f08123d038f97b809095208bb04c22671a5e
Dependencies: Stopgaps:

Description (last modified by cheuberg)

This code is a collection of functions designed to compute asymptotics of Maclaurin coefficients of certain classes of multivariate generating functions.

The main function asymptotics() returns the first N terms of the asymptotic expansion of the Maclaurin coefficients F_{n\alpha} of the multivariate meromorphic function F=G/H as n\to\infty. It assumes that F is holomorphic in a neighborhood of the origin, that H is a polynomial, and that asymptotics in the direction of \alpha (a tuple of positive integers) are controlled by smooth or multiple points.

Attachments (12)

mgf.sage (89.3 KB) - added by araichev 6 years ago.
amgf_alpha_0_5.sage (104.5 KB) - added by araichev 6 years ago.
New object oriented version
amgf.sage (105.5 KB) - added by araichev 6 years ago.
Fixed a bug in cohomologous_integrand()
amgf.py (111.3 KB) - added by araichev 6 years ago.
Pythonified amgf.sage
trac_10519.patch (111.5 KB) - added by araichev 6 years ago.
trac_10519-fixed.patch (114.0 KB) - added by davidloeffler 5 years ago.
Patch against 5.0
trac_10519.2.patch (137.6 KB) - added by araichev 5 years ago.
Major rewrite.
trac_10519-asymptotic_multiple-v3.patch (136.0 KB) - added by chapoton 5 years ago.
trac_10519v4.patch (144.9 KB) - added by araichev 4 years ago.
trac_10519-v5.patch (144.6 KB) - added by chapoton 4 years ago.
trac_10519-v6.patch (144.5 KB) - added by araichev 4 years ago.
trac_10519-v7.patch (144.0 KB) - added by araichev 4 years ago.

Download all attachments as: .zip

Change History (153)

Changed 6 years ago by araichev

comment:1 Changed 6 years ago by araichev

  • Milestone changed from sage-4.6.2 to sage-4.6.1

comment:2 Changed 6 years ago by rbeezer

Hi Alex,

I can't address the mathematics on this one, but can give some hints about getting this reviewed.

  1. You'll want to submit this as a patch - then folks can run the doctests, check the documentation formatting. There is a lot of checking that can't happen easily with a *.sage file. (See below.) Read the "Walk Through" section of the developer guide for help.
  1. Your examples need slightly different formatting, like
    EXAMPLES::

        sage: input 1
        output-1

    Something nice to say. ::

        sage: input-2
        output-2

Double-colons start verbatim blocks and sometimes print as colons.

Sage code samples needs indentation.

  1. Sage is mostly object-oriented. "Internal" method names should begin with an underscore, then they won't show in tab-completion etc (Python convention).

All your functions won't be available in teh global namespace (where they could conflict with other). You should find an object (like maybe some kind of polynomial, especially if it is already int eh combinatorial library?) and make your functions be methods on that object.

Thanks for your contribution - I hope the above is helpful for you.

Rob

comment:3 Changed 6 years ago by araichev

  • Status changed from new to needs_work

Question for you experienced Sage developers: how can i better package my code?

I think it makes sense to move the major functions such as 'asymptotics' to methods in the class /Applications/sage/devel/sage/sage/rings/polynomial/multi_polynomial.pyx, but what about the subsidiary functions that don't concern polynomials in particular such as 'diff_prod' which calculates derivatives of products and solves equations?

comment:4 Changed 6 years ago by slabbe

Question for you experienced Sage developers: how can i better package my code?

Hi, I am currently at Sage Days 28. Right now, there is a discussion about Analytic combinatorics in Sage and your code was mentionned in the discussion. I am not an expert of the domain, but I am coding oriented object Python since some time now. So below are just some of my thoughts to, I hope, help you turn your set of functions into an oriented object structure.

How to structure a bunch of functions into classes? How to find which objects (python classes) you need? Here is the trick I personaly use. Consider each of your functions as a question you ask. Then, ask yourself to who are you asking each of your questions? Answers often gives you a good hint about the objects you need to implement. EXAMPLE. Suppose I code the function determinant. Question : To who do I ask the determinant?. Answer: To a matrix. Hence, matrix might be a good object (a python class) to implement.

You are the best person to answer to these questions. You might have 30 functions in you file, but only two or three different answers to the above question. Regroup the similar functions together: they will become the methods of a same class.

The sage file you uploaded starts with :

> This code relates to analytic combinatorics.
> More specifically, it is a collection of functions designed
> to compute asymptotics of Maclaurin coefficients of certain classes of
> multivariate generating functions.

> The main function asymptotics() returns the first `N` terms of
> the asymptotic expansion of the Maclaurin coefficients `F_{n\alpha}`
> of the multivariate meromorphic function `F=G/H` as `n\to\infty`.
> It assumes that `F` is holomorphic in a neighborhood of the origin,
> that `H` is a polynomial, and that asymptotics in the direction of
> `\alpha` (a tuple of positive integers) are controlled by smooth
> or multiple points.

Reading only these lines, I imagine the following structure:

class HolomorphicMultivariateMeromorphicFunction(object):

    # Constructor of the object
    def __init__(self, F, G):
        #stores important information on the object as attributes of self
        self._F = F
        self._G = G

    def maclaurin_coefficients(self, n, alpha):
        r"""
        Return the maclaurin coefficients of self.

        INPUT:

        - ``alpha`` - tuple of positive integers

        OUTPUT:

        a python list of the first terms 
        
        OR 
        
        maybe an object of a class you implement if there exists pertinent
        questions to ask to it.
        """
        #Do some computations based (I guess) on self._F and self._G
        intermediate_result1 = self.some_intermediate_computations_1()
        #Do more computations
        return something

    def asymptotics(self, N, alpha):
        r"""
        Returns the asymptotics of Maclaurin coefficients.
        """
        #Do some computations based (I guess) on self._F and self._G
        intermediate_result2 = self.some_intermediate_computations_2()
        intermediate_result3 = self.some_intermediate_computations_3()
        return something

    #put here all the others functions needed to compute the asymptotics
    def some_intermediate_computations_1(self):
        pass
    def some_intermediate_computations_2(self):
        pass
    def some_intermediate_computations_3(self):
        pass

    ...

It also looks like you need some robustness somehow. But I need to know more information about what means

that asymptotics in the direction of \alpha (a tuple of positive integers) are controlled by smooth or multiple points.

to decide whether this is checked at the creation of the object or before returning the asymptotics. But these hypothesis should be checked somewhere.

Hope this helps.

Cheers,

Sébastien Labbé, Montréal, (but currently at Sage Days 28, Orsay, France)

comment:5 Changed 6 years ago by cyril.banderier

  • Cc cyril.banderier added

comment:6 follow-up: Changed 6 years ago by araichev

Hi Sebastien:

Thanks very much for your helpful comments. I've been working on rewriting my code in an object-oriented way and will incorporate your suggestions. Some functions in mgf.sage, such as deciding whether a list of polynomials is algebraically dependent, are general purpose, and so i'm trying to put them into existing Sage classes. The others are more specific to asymptotics and deserve their own class similar to the one you outlined above. Robustness is also something i need to improve upon.

I'll post my modifications here after i write and test them more.

Thanks again.

Alex

Changed 6 years ago by araichev

New object oriented version

Changed 6 years ago by araichev

Fixed a bug in cohomologous_integrand()

comment:7 in reply to: ↑ 6 Changed 6 years ago by araichev

Hi Sebastien et al:

I rewrote my code in object-oriented style. Please have a look if you have the time. Do i need to make the file into a patch, or is it useable as is?

Thanks for your help. Alex

comment:8 Changed 6 years ago by araichev

  • Status changed from needs_work to needs_review

comment:9 follow-up: Changed 6 years ago by slabbe

  • Status changed from needs_review to needs_work

Cool. I now see that a lot of the functions are now inside a class, which looks better. So, as I said earlier, this is not really my field of study, so I don't know how far I can go on that review. But, I can suggest at least two things:

  1. It would be better if you post a Mercurial patch instead of a Sage file so that people can apply it and test it. Are you able to do this? Take a look at the Sage Developper's Guide, where it should be explain how to create a patch.

To add your file to the documentation, you might want to look here.

This winter, I gave a presentation on How to Contribute to Sage. This may helps you to start with Mercurial for instance.

Also, right now, I am working on #11379 where I am adding a new file to Sage. You might find it helpfull to see how I proceed.

  1. Some the Python convention are not always followed. See also pep-0008. Especially for spaces :
      Yes:

          i = i + 1

      No:

          i= i+1

comment:10 in reply to: ↑ 9 Changed 6 years ago by slabbe

To add a file to a patch, you must do:

sage -hg add your_file.py

I was not able to find this information anywhere which is strange...

Tell me if you have questions.

Sébastien

comment:11 follow-ups: Changed 6 years ago by araichev

Thanks for your help, Se'bastien. I'm trying to put my Sage file into a patch by following your presentation slides, but am running into difficulties. I cloned Sage and copied my Sage file as 'amgf.sage' into

/Applications/sage/devel/sage-araichev/sage/combinat/

I rebuilt Sage etc. and made it to step 10 "Test the changes" of your slides. But when i run Sage and test a few commands, Sage doesn't seem to see the QuasiRationalExpression? class i created in /Applications/sage/devel/sage-araichev/sage/combinat/amgf.sage.

I thought this might be because amgf.sage is a Sage file and not a Python file. So i renamed it amgf.py instead and got syntax errors. What's up with that? Do i have to rewrite all my code in Python instead of Sage?

Thanks for your attention. Alex

comment:12 in reply to: ↑ 11 Changed 6 years ago by hivert

Hi Alex,

I thought this might be because amgf.sage is a Sage file and not a Python file. So i renamed it amgf.py instead and got syntax errors. What's up with that? Do i have to rewrite all my code in Python instead of Sage?

The basic answer is yes, but Rewriting is a big word for what is really needed. There is little work to do since Sage mostly follows Python syntax. The two main difference are handling of integer (see http://www.sagemath.org/doc/tutorial/afterword.html), and the necessity to import what you need.

Handling of integer

  • Notation for exponentiation: In Python ** means exponentiation and ^ means “xor”.
  • If you need to return an integer for the user, write it return Integer(1) instead of return 1. In Python 1 is a machine integer int (32 or 64 bits depending on your machine) and Integer(1) is a Sage/Gmp? arbitrary precision integer. Also Integer are much more powerful than int, for example they know about prime and factorization.

Importing stuff

The second big change is the necessity to import all what you need. More precisely, each time you use some Sage function, you need to import it at the beginning of the file. for example if you want to you PolynomialRing, you need to write

from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing

You can ask Sage where to find PolynomialRing? using:

sage: PolynomialRing.__module__
'sage.rings.polynomial.polynomial_ring_constructor'

This also correspond to the path starting after site-packages given when you are asking Sage for PolynomialRing help:

sage: PolynomialRing?
Type:           function
[...]
File:           /home/florent/src/Sage/sage/local/lib/python2.6/site-packages/sage/rings/polynomial/polynomial_ring_constructor.py
[...]

I hope this helps,

Florent

comment:13 in reply to: ↑ 11 Changed 6 years ago by slabbe

Just answering as a complement to Florent's answer.

But when i run Sage and test a few commands, Sage doesn't seem to see the QuasiRationalExpression? class i created in /Applications/sage/devel/sage-araichev/sage/combinat/amgf.sage.

To test your code in a Sage session, you will first need to import the good class (or function). For instance :

sage: from sage.combinat.amgf import QuasiRationalExpression

If you would like QuasiRationalExpression to be already imported once Sage is started, you must add the line from sage.combinat.amgf import QuasiRationalExpression to the file sage/combinat/all.py. Note that it is not "à la mode" to add new stuff to all.py files because Sage is very slow to start because of all the things that are imported. If you think a lot of people will use the code, then it might be defendable.

Sébastien

comment:14 Changed 6 years ago by araichev

Thanks for the tips, Florent and Se'bastien. I'll get to work on converting amgf.sage to amgf.py.

Alex

comment:15 Changed 6 years ago by araichev

Hang on, can i somehow use the Sage pre-parser to automatically convert amgf.sage to amgf.py?

Alex

comment:16 Changed 6 years ago by araichev

Aha! The command 'sage amgf.sage' pre-parses amgf.sage and saves it as amgf.py. Thank you ask.sagemath.org!

Alex

Changed 6 years ago by araichev

Pythonified amgf.sage

comment:17 Changed 6 years ago by araichev

  • Status changed from needs_work to needs_review

comment:18 Changed 6 years ago by slabbe

The patch is empty. I hope you did not lose anything?

Sébastien

Changed 6 years ago by araichev

comment:19 Changed 6 years ago by araichev

Hmm, i couldn't figure out how to add the code to the patch. I tried 'sage -hg add amgf.py' as you suggested, Se'bastien, but that didn't work. So i finally copied and pasted it in. I hope that works. Let me know the proper way, yo.

Sorry for the delay.

Alex

comment:20 Changed 6 years ago by zaf

  • Cc zaf added

comment:21 Changed 5 years ago by tmonteil

  • Cc tmonteil added

Changed 5 years ago by davidloeffler

Patch against 5.0

comment:22 Changed 5 years ago by davidloeffler

  • Reviewers set to David Loeffler
  • Status changed from needs_review to needs_work

Apply trac_10519-fixed.patch

(for the patchbot).

Alex's last "patch" wasn't a patch at all, just a Mercurial header with some Python code arbitrarily pasted into it. I've just uploaded a non-broken version of the patch. I also added the necessary import statements -- a file that's supposed to be part of the Sage library can't import the Sage library (with from all_cmdline import *), since that would lead to an infinite loop, so the necessary imports have to be done one-by-one.

The patch now passes doctests on my machine, but there are some worrying errors that came up when I ran a syntax checker on the new file: {{{amgf.py:908: local variable 'R' is assigned to but never used amgf.py:909: local variable 'd' is assigned to but never used amgf.py:1070: local variable 'Ht' is assigned to but never used amgf.py:1251: local variable 'Ht' is assigned to but never used amgf.py:1591: undefined name 'n' amgf.py:2199: local variable 'H' is assigned to but never used amgf.py:2242: undefined name 'verdict' }}} The "undefined name" errors tend to suggest that some cases have bugs in them, *and* those cases are not checked in any doctest, which is a double whammy. Hence "needs work".

comment:23 Changed 5 years ago by davidloeffler

Sorry, that list got mangled. It should be

amgf.py:908: local variable 'R' is assigned to but never used
amgf.py:909: local variable 'd' is assigned to but never used
amgf.py:1070: local variable 'Ht' is assigned to but never used
amgf.py:1251: local variable 'Ht' is assigned to but never used
amgf.py:1591: undefined name 'n'
amgf.py:2199: local variable 'H' is assigned to but never used
amgf.py:2242: undefined name 'verdict'

comment:24 Changed 5 years ago by araichev

Thanks for your review, David. This patch was my first on Sage Trac and i've since learned a lot, thanks to the constructive feedback of fellow Sagers such as yourself.

Since amgf.py was somewhat of a code bomb, i decided to split it up into simpler pieces, submit those pieces, and, once they get accepted, recombine them. If you or anyone else would like to help me in this endeavor, check out the latest amgf piece at http://trac.sagemath.org/sage_trac/ticket/12417.

Thanks!

I'll keep you all updated on the progress of amgf with these comments.

Changed 5 years ago by araichev

Major rewrite.

comment:25 Changed 5 years ago by araichev

  • Status changed from needs_work to needs_review

comment:26 Changed 5 years ago by chapoton

Apply only trac_10519.2.patch

comment:27 Changed 5 years ago by chapoton

  • Status changed from needs_review to needs_work
  • Work issues set to coverage, trailing whitespace
  • Please ensure that every function is doctested
  • Please remove all trailing whitespaces

Changed 5 years ago by chapoton

comment:28 Changed 5 years ago by chapoton

  • Description modified (diff)

I have removed all whitespaces in the new patch. All test pass.

BUT there remains 6 procedures with no doctest. Remember that it is neccesary to have 100% doctesting.

Also the name amgf is not good. It should be changed to something more descriptive.

comment:29 Changed 5 years ago by chapoton

  • Work issues changed from coverage, trailing whitespace to coverage

comment:30 Changed 4 years ago by araichev

Thanks, folks. I'll document those outstanding 6 procedures within a week.

comment:31 Changed 4 years ago by araichev

Hmm, i might take longer, because now that i've upgraded to Sage 5.3, i can't create a Sage clone :-( See http://ask.sagemath.org/question/1821/cant-create-sage-clone-again.

comment:32 Changed 4 years ago by araichev

Still can't create a Sage clone. In the meantime, here's my patch as a Python file (which i tested on Sage 5.3 with sage -t --long) for anyone who wants to review it: https://www.dropbox.com/s/fcxsbuw119qclxt/trac_10519v4.py.

Changed 4 years ago by araichev

comment:33 Changed 4 years ago by araichev

  • Status changed from needs_work to needs_review

comment:34 Changed 4 years ago by chapoton

  • Description modified (diff)

apply only trac_10519v4.patch

comment:35 Changed 4 years ago by chapoton

  • Status changed from needs_review to needs_work
  • Work issues changed from coverage to failing tests, trailing whitespaces

please remove all trailing whitespaces

please correct the failing doctests

comment:36 Changed 4 years ago by chapoton

  • Description modified (diff)
  • Status changed from needs_work to needs_review

apply trac_10519-v5.patch

Last edited 4 years ago by chapoton (previous) (diff)

Changed 4 years ago by chapoton

comment:37 Changed 4 years ago by chapoton

apply trac_10519-v5.patch

Changed 4 years ago by araichev

comment:38 Changed 4 years ago by araichev

Hmm, i don't understand why i didn't get any test errors when i submitted v4. Anyway, fixed the errors.

comment:39 Changed 4 years ago by araichev

  • Work issues failing tests, trailing whitespaces deleted

comment:40 Changed 4 years ago by chapoton

  • Description modified (diff)

Apply trac_10519-v6.patch

comment:41 Changed 4 years ago by chapoton

well, now version V5 works and version V6 does not pass the tests.

I had already made all the necessary corrections in version V5.

Can we just forget version V6 ?

comment:42 Changed 4 years ago by araichev

OK, let's forget V6. I bet the problem is one or two docstring lines that output a dictionary. The random order of the keys is causing a test failure when it doesn't match up with the docstring key order. We can fix that by sorting the keys before printing them.

comment:43 Changed 4 years ago by chapoton

  • Description modified (diff)

apply trac_10519-v5.patch

comment:44 Changed 4 years ago by dkrenn

  • Cc dkrenn added

comment:45 Changed 4 years ago by araichev

Hi folks, is this patch ready to be added to Sage? If not, what's the next step?

comment:46 Changed 4 years ago by chapoton

The next step would be that somebody interested does a real review of this patch. This means looking seriously at the code, using the functions, trying to find bugs, and so on. I am not candidate, sorry.

comment:47 Changed 4 years ago by chapoton

Here is the report of pyflakes : some things that need to be corrected

sage/combinat/asymptotics_multivariate_generating_functions.py:147: 'UniqueFactorizationDomains' imported but unused
sage/combinat/asymptotics_multivariate_generating_functions.py:156: 'CartesianProduct' imported but unused
sage/combinat/asymptotics_multivariate_generating_functions.py:171: 'ZZ' imported but unused
sage/combinat/asymptotics_multivariate_generating_functions.py:172: redefinition of unused 'PolynomialRing' from line 148
sage/combinat/asymptotics_multivariate_generating_functions.py:175: 'SageObject' imported but unused
sage/combinat/asymptotics_multivariate_generating_functions.py:1719: local variable 'Ht' is assigned to but never used
sage/combinat/asymptotics_multivariate_generating_functions.py:2097: local variable 'Ht' is assigned to but never used
sage/combinat/asymptotics_multivariate_generating_functions.py:2992: local variable 'X' is assigned to but never used
sage/combinat/asymptotics_multivariate_generating_functions.py:3083: undefined name 'Subsets'
Last edited 4 years ago by chapoton (previous) (diff)

comment:48 Changed 4 years ago by chapoton

  • Status changed from needs_review to needs_work
  • Work issues set to pyflakes report

Changed 4 years ago by araichev

comment:49 Changed 4 years ago by araichev

Thanks. Fixed.

comment:50 Changed 4 years ago by araichev

  • Status changed from needs_work to needs_review

comment:51 Changed 4 years ago by chapoton

  • Description modified (diff)
  • Work issues pyflakes report deleted

for the bot

Apply trac_10519-v7.patch

comment:52 Changed 4 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:53 follow-up: Changed 3 years ago by dimpase

It does not seems to be properly integrated into sage:

sage: from sage.combinat.asymptotics_multivariate_generating_functions import *
---------------------------------------------------------------------------
ImportError                               Traceback (most recent call last)
<ipython-input-1-3a279f9ff0e0> in <module>()
----> 1 from sage.combinat.asymptotics_multivariate_generating_functions import *

ImportError: No module named asymptotics_multivariate_generating_functions
sage: 

and indeed, you can see that the patch should be for 'sage/combinat' directory, not for './'. Unless this is meant to go to the "combinat queue" - and I have no clue how such reviews are meant to happen and how the corresponding code "admin" should look like.

Question: how much of this is dependent upon the "combinat queue"?

comment:54 in reply to: ↑ 53 ; follow-up: Changed 3 years ago by araichev

Replying to dimpase:

Yes, the patch should be for sage/combinat. Feel free to change that, if you'd like to review the patch now. Otherwise, i'll change it when i get some time in the next week.

It does not seems to be properly integrated into sage:

sage: from sage.combinat.asymptotics_multivariate_generating_functions import *
---------------------------------------------------------------------------
ImportError                               Traceback (most recent call last)
<ipython-input-1-3a279f9ff0e0> in <module>()
----> 1 from sage.combinat.asymptotics_multivariate_generating_functions import *

ImportError: No module named asymptotics_multivariate_generating_functions
sage: 

and indeed, you can see that the patch should be for 'sage/combinat' directory, not for './'. Unless this is meant to go to the "combinat queue" - and I have no clue how such reviews are meant to happen and how the corresponding code "admin" should look like.

Question: how much of this is dependent upon the "combinat queue"?

comment:55 in reply to: ↑ 54 Changed 3 years ago by dimpase

Replying to araichev:

Replying to dimpase:

Yes, the patch should be for sage/combinat. Feel free to change that, if you'd like to review the patch now. Otherwise, i'll change it when i get some time in the next week.

One should use lazy_import in sage/combinat/all.py to import the stuff in this patch, rather than forcing the user to do the explicit import

Question: how much of this is dependent upon the "combinat queue"?

So, how much, if anything at all?

comment:56 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:57 follow-ups: Changed 3 years ago by tscrim

  • Branch set to public/combinat/analytic-10519
  • Commit set to 60b93376cbb072a1aab99646806555830799468f

Here's a git branch version along with some extensive review changes to the documentation. I made some internal methods private to cleanup the namespace (i.e. what you get with tab completion). I also made stuff python 3 compatible. Unfortunately I also cannot really give a good review to the mathematics behind this.

@Dima, I think you've misunderstood what the combinat queue is. However it's moot because we are no longer using hg.


New commits:

b01625d10519: Removed unused modules and variables
443ab74Work on cleaning up documentation.
7f9b89eMerge branch 'develop' into public/combinat/analytic-10519
40dacc9Review changes and added new file to documentation.
60b9337Tweaked print statements and list().

comment:58 in reply to: ↑ 57 Changed 3 years ago by araichev

Hooray! Thanks heaps, @tscrim.

Replying to tscrim:

Here's a git branch version along with some extensive review changes to the documentation. I made some internal methods private to cleanup the namespace (i.e. what you get with tab completion). I also made stuff python 3 compatible. Unfortunately I also cannot really give a good review to the mathematics behind this.

@Dima, I think you've misunderstood what the combinat queue is. However it's moot because we are no longer using hg.


New commits:

b01625d10519: Removed unused modules and variables
443ab74Work on cleaning up documentation.
7f9b89eMerge branch 'develop' into public/combinat/analytic-10519
40dacc9Review changes and added new file to documentation.
60b9337Tweaked print statements and list().

comment:59 Changed 3 years ago by dimpase

Why does one need these FFPD and FFPDSum classes? Are Sage's multivariate rational functions not good enough? One should have an interface between these FFPD and FFPDSum and "normal" Sage's rational functions, anyway.

Also, I think that the part that computes decomposition(s) of rational functions must be factored out (and put on another ticket, and they should not be in combinat/, as this has noting to do with combinatorics). It has independent uses, which need not have anything to do with the stated purpose of this ticket.

comment:60 in reply to: ↑ 57 ; follow-up: Changed 3 years ago by dimpase

Replying to tscrim:

@Dima, I think you've misunderstood what the combinat queue is. However it's moot because we are no longer using hg.

Travis, I think already in 2010 I knew what the combinat queue is ;-)

Somehow, when reading the code, something made me wonder if this code depends on some features from (what was formerly known as?) combinat queue. I'm happy to know that it's not the case.

comment:61 in reply to: ↑ 60 Changed 3 years ago by tscrim

Replying to dimpase:

Replying to tscrim:

@Dima, I think you've misunderstood what the combinat queue is. However it's moot because we are no longer using hg.

Travis, I think already in 2010 I knew what the combinat queue is ;-)

Somehow, when reading the code, something made me wonder if this code depends on some features from (what was formerly known as?) combinat queue. I'm happy to know that it's not the case.

Ah sorry, it seemed to me from comment:53 like there was a misunderstanding. I'm also happy there's no dependence on any patches that are in the (now unused) queue that we might have to untangle.

Last edited 3 years ago by tscrim (previous) (diff)

comment:62 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:63 Changed 3 years ago by rws

  • Status changed from needs_review to needs_work
  • Work issues set to rebase

comment:64 Changed 3 years ago by git

  • Commit changed from 60b93376cbb072a1aab99646806555830799468f to 7511d1454940e11462bf07452c745638fd48d95a

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

7511d14Merge branch 'public/combinat/analytic-10519' of ssh://trac.sagemath.org:22/sage into 10519

comment:65 Changed 3 years ago by chapoton

  • Status changed from needs_work to needs_review

comment:66 follow-up: Changed 3 years ago by vdelecroix

Hi,

Just read the code and glance some remarks. The code looks very interesting but I have some advices/questions.

  • as a matter of uniformization class name are better expanded (FractionWithFactoredPolynomialDenominator instead of FFPD)
  • cartesian_product_iterator will be very soonly deprecated, so use product from the Python itertools module instead.
  • it is generally bad practice to have such a big import list at the begining of the file (because of potential circular import). Moreover some of them can be completely avoided: L = FractionField(PolynomialRing(K, indets)) can be PolynomialRing(K, indets).fraction_field().

More seriously:

  • I do not understand the specifications. It is said that the numerator must be an element p of a 0 or 1 variate factorial polynomial ring R but you have examples involving cos(x). What is the underlying polynomial ring in that case?
  • repeating comment:59, Why there is a need for the class FFDP? Why isn't it directly implemented as the level of fractions of polynomials? It would makes sense to cache the factorization of the denominator if it is required in several places, but I do not see the point of the FFDP class.
  • Some of the method needs definition: critical_cone, is_convenient_multiple_point, ...
  • Some of the method would better be hidden: combine_like_terms, ...

Best Vincent

comment:67 follow-up: Changed 3 years ago by araichev

Hi folks, because of my new work and responsibilities outside the realm of analytic combinatorics and Sage, i've needed to put this project on hold indefinitely. Please feel free to change the code as you like. I hope i've documented it well enough with comments and references so that others can carry it to fruition.

comment:68 in reply to: ↑ 67 ; follow-up: Changed 3 years ago by vdelecroix

Replying to araichev:

Hi folks, because of my new work and responsibilities outside the realm of analytic combinatorics and Sage, i've needed to put this project on hold indefinitely. Please feel free to change the code as you like. I hope i've documented it well enough with comments and references so that others can carry it to fruition.

Hey Alexei,

Good luck with your new work. I will read it carefully and see what I can do. It is definitely a good piece of work.

Vincent

comment:69 in reply to: ↑ 68 ; follow-up: Changed 3 years ago by tscrim

Replying to vdelecroix:

Replying to araichev:

Hi folks, because of my new work and responsibilities outside the realm of analytic combinatorics and Sage, i've needed to put this project on hold indefinitely. Please feel free to change the code as you like. I hope i've documented it well enough with comments and references so that others can carry it to fruition.

Hey Alexei,

Good luck with your new work.

Yes, good luck with your new work.

I will read it carefully and see what I can do. It is definitely a good piece of work.

Vincent (or Dima), will you be able to check the math for this ticket? If not, I think I could go through it math-wise.

On the code front:

  • Since there are only two classes, I agree with you that we should spell it out.
  • Similar for changing to the built-in python tools.
  • However I think the big import statement is okay since this is going to be a leaf (or at least on a short branch) of the import tree/poset/digraph.
  • What methods do you think should be private?
  • What can I do code-wise to help get this in?

comment:70 in reply to: ↑ 69 ; follow-up: Changed 3 years ago by dimpase

Replying to tscrim:

Replying to vdelecroix:

Replying to araichev:

Hi folks, because of my new work and responsibilities outside the realm of analytic combinatorics and Sage, i've needed to put this project on hold indefinitely. Please feel free to change the code as you like. I hope i've documented it well enough with comments and references so that others can carry it to fruition.

Hey Alexei,

Good luck with your new work.

Yes, good luck with your new work.

I will read it carefully and see what I can do. It is definitely a good piece of work.

Vincent (or Dima), will you be able to check the math for this ticket? If not, I think I could go through it math-wise.

please see my #comment:59

IMHO refactoring and interfacing with Sage's facilities for rational functions is due, before this can be merged.

comment:71 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:72 Changed 3 years ago by dkrenn

  • Branch changed from public/combinat/analytic-10519 to public/combinat/analytic-10519-on-6.3

comment:73 Changed 3 years ago by dkrenn

  • Commit changed from 7511d1454940e11462bf07452c745638fd48d95a to 28057320fe66a23041b55a7769e4607ca4d8abbd

rebased to 6.3


New commits:

761ea5210519: Removed unused modules and variables
6701fb4Work on cleaning up documentation.
46ad958Review changes and added new file to documentation.
2805732Tweaked print statements and list().

comment:74 follow-up: Changed 3 years ago by dkrenn

  • Dependencies set to #16848

There is a doctest (and the doctest using the result below) failing:

sage -t src/sage/combinat/asymptotics_multivariate_generating_functions.py
**********************************************************************
File "src/sage/combinat/asymptotics_multivariate_generating_functions.py", line 90, in sage.combinat.asymptotics_multivariate_generating_functions
Failed example:
    s
Expected:
    [{x: 1, y: 1}]
Got:
    []

This is now #16848.

comment:75 Changed 3 years ago by dkrenn

  • Reviewers changed from David Loeffler to Daniel Krenn, David Loeffler

comment:76 in reply to: ↑ 70 Changed 3 years ago by dkrenn

Replying to dimpase:

Replying to tscrim:

Vincent (or Dima), will you be able to check the math for this ticket? If not, I think I could go through it math-wise.

At least, I started checking the math.

IMHO refactoring and interfacing with Sage's facilities for rational functions is due, before this can be merged.

Yes, this should be definitely done.

comment:77 Changed 3 years ago by dkrenn

  • Work issues rebase deleted

comment:78 Changed 3 years ago by git

  • Commit changed from 28057320fe66a23041b55a7769e4607ca4d8abbd to 8bc997179b09a47eb0b23fc3c623ec8b92391e8f

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

8bc9971fixed broken doctest

comment:79 in reply to: ↑ 74 Changed 3 years ago by dkrenn

Replying to dkrenn:

There is a doctest (and the doctest using the result below) failing:

sage -t src/sage/combinat/asymptotics_multivariate_generating_functions.py
**********************************************************************
File "src/sage/combinat/asymptotics_multivariate_generating_functions.py", line 90, in sage.combinat.asymptotics_multivariate_generating_functions
Failed example:
    s
Expected:
    [{x: 1, y: 1}]
Got:
    []

This is now #16848.

This works now (by a workaround).

Last edited 3 years ago by dkrenn (previous) (diff)

comment:80 Changed 3 years ago by dkrenn

  • Dependencies #16848 deleted
  • Status changed from needs_review to needs_work

comment:81 Changed 2 years ago by git

  • Commit changed from 8bc997179b09a47eb0b23fc3c623ec8b92391e8f to 4a71e9c6c447323c20b7b0904e62084abad15c98

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

4a71e9cMerge branch 'public/combinat/analytic-10519-on-6.3' of ssh://trac.sagemath.org:22/sage into 6.5.b4

comment:82 Changed 2 years ago by dkrenn

I'm currently porting the code to Sage's parent/element framework.

comment:83 follow-up: Changed 2 years ago by chapoton

My pep8 compliant branch is now available at "u/chapoton/10519".

I am not sure it will be easy to merge it with your other changes. Maybe it is not worth the trouble.

comment:84 Changed 2 years ago by dkrenn

  • Branch changed from public/combinat/analytic-10519-on-6.3 to public/combinat/10519

comment:85 Changed 2 years ago by dkrenn

  • Authors changed from Alex Raichev to Daniel Krenn, Alex Raichev
  • Commit changed from 4a71e9c6c447323c20b7b0904e62084abad15c98 to a54855dfb4c9855d2facb682542c5058534a276c

Last 10 new commits:

94d860dimplement equality testing (using coercion model)
38b0f7ecoercion from other FFPD rings implemented
c37adddtrac #10519 pep8 fully compliant
79e88d1moved code like in "9914678 - moved static methods to parent" to allow merging
53d60eaMerge branch 'u/chapoton/10519' into t/10519-on-6.5.beta4
6a326a2fixed doctests (ordering of dicts has changed)
494cd16fixed doctests (x and y are ordered as y, x)
8dc6311clauses for "R is None" removed
9654c94restructure import of libraries
a54855dupdate authors, copyright; new reference; some empty lines inserted

comment:86 in reply to: ↑ 83 ; follow-up: Changed 2 years ago by dkrenn

I've uploaded what I have up to now. There are a couple of minor issues to fix left and some doctests are still failing (this is due to using a wrong base ring...)

Replying to chapoton:

My pep8 compliant branch is now available at "u/chapoton/10519". I am not sure it will be easy to merge it with your other changes. Maybe it is not worth the trouble.

I've merged your changes/branch (most of them manually; I think I've got all but please check if in doubt).

In "u/chapoton/10519" Sage 6.5.beta4 was merged, which made some doctests failing. I've created a commit fixing most of them, but there is one annoying issue: The doctest in line 3672

DD = FFDR._diff_op(A, B, AB_derivs, T, M, 1, 2)

takes now forever (over 45 seconds compared to 1.78 seconds before). Does someone has an idea what between 6.3 and 6.5.beta4 could trigger this?

Version 0, edited 2 years ago by dkrenn (next)

comment:87 Changed 2 years ago by git

  • Commit changed from a54855dfb4c9855d2facb682542c5058534a276c to 301843b542aa2a6d326e394853ea3b1de0af2e6e

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

301843bfixed long doctest (introduced in c37addd - trac #10519 pep8 fully compliant)

comment:88 in reply to: ↑ 86 Changed 2 years ago by dkrenn

Replying to dkrenn:

Replying to chapoton:

My pep8 compliant branch is now available at "u/chapoton/10519".

In "u/chapoton/10519" [...] The doctest in line 3672

DD = FFDR._diff_op(A, B, AB_derivs, T, M, 1, 2)

takes now forever (over 45 seconds compared to 1.78 seconds before). Does someone has an idea what between 6.3 and 6.5.beta4 could trigger this?

Finally found the problem; wasn't the Sage upgrade, but commit c37addd "trac #10519 pep8 fully compliant", which simplified

if something != Integer(0):

to

if something:

which made this test slow (don't know why...). Anyhow, pushed a commit which fixes this.

comment:89 Changed 2 years ago by chapoton

Oops, sorry for this. I thought it was simpler. I do not understand why is is much slower. Anyway, sorry again for the trouble.

comment:90 Changed 2 years ago by git

  • Commit changed from 301843b542aa2a6d326e394853ea3b1de0af2e6e to 898a1c63ed95aa3c1250727c1c4c9e637f71f26a

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

61946d3rename reduce_ to reduce
84d797cfixed univariate_decomposition when numerator is not a polynomial
898a1c6fix remaining failing doctests and code cleanup

comment:91 Changed 2 years ago by git

  • Commit changed from 898a1c63ed95aa3c1250727c1c4c9e637f71f26a to b0b5c3f303c913687a26f6cacd9c1691b0135f96

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

5e77b11short code simplification (FractionField) (comment:66 of #10519)
438bd66make combine_like_terms private (comment:66 of #10519)
c2b0daballow coercion from fraction field of polynomial rings
41e9956rename FFPDElement and FFPDSum
b0b5c3frepr of FractionWithFactoredDenominatorSum returns + between terms

comment:92 Changed 2 years ago by git

  • Commit changed from b0b5c3f303c913687a26f6cacd9c1691b0135f96 to 974d997af25eb9239d016da2667e38d47b7baa8c

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

a7da403remove .list, since not needed any may lead to confusion
a3bc051some small changes in code during review
edd992fadd doc (so that it is built automatically)
605e62dchanges in docstrings during review
974d997make coerce_point private

comment:93 in reply to: ↑ 66 Changed 2 years ago by dkrenn

During review I've worked over the code and ported it to Sage's parent/element framework.

Here are comments to the comments above:

Replying to vdelecroix:

  • as a matter of uniformization class name are better expanded (FractionWithFactoredPolynomialDenominator instead of FFPD)

Renaming done.

  • cartesian_product_iterator will be very soonly deprecated, so use product from the Python itertools module instead.

itertools are now used here.

  • it is generally bad practice to have such a big import list at the begining of the file (because of potential circular import). Moreover some of them can be completely avoided: L = FractionField(PolynomialRing(K, indets)) can be PolynomialRing(K, indets).fraction_field().

Moved imports to functions. Only a very few global (in the module) imports are left.

More seriously:

  • I do not understand the specifications. It is said that the numerator must be an element p of a 0 or 1 variate factorial polynomial ring R but you have examples involving cos(x). What is the underlying polynomial ring in that case?
  • repeating comment:59, Why there is a need for the class FFDP? Why isn't it directly implemented as the level of fractions of polynomials? It would makes sense to cache the factorization of the denominator if it is required in several places, but I do not see the point of the FFDP class.

The numerator can be any element from a ring into which the denominator coerces in. E.g. the denominator is a polynomial ring, but numerator is allowed to be out of the symbolic ring.

  • Some of the method needs definition: critical_cone, is_convenient_multiple_point, ...

Tried a bit of rephrasing, but they are defined in the cited works.

  • Some of the method would better be hidden: combine_like_terms, ...

Done. (also some other functions/methods were made private).

Concerning the review:

  • I've did a basic check on the mathematics: seems to be ok.
  • I've read the docstrings and modified some of them either to make them clearer or to fit the guidelines in the developer guide (e.g. INPUT/OUTPUT blocks and so on). This is fine for me here (but documentation can, of course, always be improved ;) ).
  • Documentation builds.
  • All doctests pass.
  • I'm towards a positive review, but, of course, someone has to cross review my transition of the code to parent/element framework.

Therefore: needs cross-review '''

comment:94 Changed 2 years ago by dkrenn

  • Status changed from needs_work to needs_review

comment:95 follow-ups: Changed 2 years ago by mmezzarobba

Just two minor comments:

  • If FractionWithFactoredDenominatorRing is intended to actually be a ring, shouldn't the numerators also be restricted to some given parent? (i.e., shouldn't there be a numerator_ring and a denominator_ring, or something like that, instead of just a ring?)
  • Isn't at least some of the code general-purpose enough that it could live in rings/ or symbolic/ rather than combinat/? If not, perhaps it would be worth at least linking to it from the documentation of related objects.

comment:96 in reply to: ↑ 95 ; follow-up: Changed 2 years ago by dimpase

Replying to mmezzarobba:

  • Isn't at least some of the code general-purpose enough that it could live in rings/ or symbolic/ rather than combinat/? If not, perhaps it would be worth at least linking to it from the documentation of related objects.

I have mentioned that in an old comment; IMHO the code must be refactored: the code to decompose a rational function into a sum must not live in combinat/.

comment:97 Changed 2 years ago by mmezzarobba

  • Status changed from needs_review to needs_work

comment:98 follow-up: Changed 2 years ago by rws

Moreover, I could reproduce the results from the four doctests of univariate_decomposition using the existing QuotientFields.element_class.partial_fraction_decomposition and Expression.partial_fraction functionality. So, why not use these?

comment:99 Changed 20 months ago by git

  • Commit changed from 974d997af25eb9239d016da2667e38d47b7baa8c to 1c995c5f965e6218f4e1f47082106d616be027ac

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

137f3c7Worked in bugs reported by Mark Wilson
1a7d977Merge tag '6.6' into t/10519-on-6.6
1c995c5Merge tag '6.8' into t/10519-on-6.8

comment:100 Changed 20 months ago by dkrenn

Merged in current stable SageMath 6.8

Last edited 20 months ago by dkrenn (previous) (diff)

comment:101 Changed 14 months ago by git

  • Commit changed from 1c995c5f965e6218f4e1f47082106d616be027ac to a62ed348cc2fe2c9eafee35d7fcab42ee90f7000

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

0afbbdfMerge tag '7.0' into t/10519/public/combinat/10519
d6f58ceTrac #10519: fix doctests
564d8bdTrac #10519: move to sage.rings.asymptotic
a62ed34Trac #10519: fix doctests (new location)

comment:102 Changed 14 months ago by dkrenn

Merged in current stable SageMath 7.0

comment:103 in reply to: ↑ 95 Changed 14 months ago by dkrenn

Replying to mmezzarobba:

  • Isn't at least some of the code general-purpose enough that it could live in rings/ or symbolic/ rather than combinat/? If not, perhaps it would be worth at least linking to it from the documentation of related objects.

Moved to sage.rings.asymptotic (which was created last summer for asymptotic expansions #17601) as this seems very suitable.

comment:104 Changed 14 months ago by git

  • Commit changed from a62ed348cc2fe2c9eafee35d7fcab42ee90f7000 to 6a44c8c436f7227a0bf1bb0dccc0ba94886d5801

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

6a44c8cTrac #10519: update index in doc tree

comment:105 Changed 14 months ago by git

  • Commit changed from 6a44c8c436f7227a0bf1bb0dccc0ba94886d5801 to 1f21184f37244dbdf0395c75f474e4ca9429557f

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

b99c64aTrac #10519: introduce numerator_ring and denominator_ring
328a75dTrac #10519: fix doctests
34845ffTrac #10519: speed up for univariate_decomposition
9699c67Trac #10519: fix ReST documentation
340c34dTrac #10519: mark class as experimental
874b4c3Trac #10519: update authors and copyright
1f21184Trac #10519: fix indention in ReST

comment:106 in reply to: ↑ 96 Changed 14 months ago by dkrenn

Replying to dimpase:

Replying to mmezzarobba:

  • Isn't at least some of the code general-purpose enough that it could live in rings/ or symbolic/ rather than combinat/? If not, perhaps it would be worth at least linking to it from the documentation of related objects.

I have mentioned that in an old comment; IMHO the code must be refactored: the code to decompose a rational function into a sum must not live in combinat/.

Changed; now sage.rings.asymptotic, see comment:103.

comment:107 in reply to: ↑ 95 Changed 14 months ago by dkrenn

Replying to mmezzarobba:

Just two minor comments:

  • If FractionWithFactoredDenominatorRing is intended to actually be a ring, shouldn't the numerators also be restricted to some given parent? (i.e., shouldn't there be a numerator_ring and a denominator_ring, or something like that, instead of just a ring?)

I agree; now there is.

comment:108 in reply to: ↑ 98 Changed 14 months ago by dkrenn

Replying to rws:

Moreover, I could reproduce the results from the four doctests of univariate_decomposition using the existing QuotientFields.element_class.partial_fraction_decomposition and Expression.partial_fraction functionality. So, why not use these?

In univariate_decomposition the already-known factorization of the denominator is used. This gives a speed-up for not too small instances. Below the timings,

  • No speedup for the first (small) example in the doctest:
    sage: sage: from sage.rings.asymptotic.asymptotics_multivariate_generating_functions import FractionWithFactoredDenominatorRing
    sage: sage: R.<x> = PolynomialRing(QQ)
    sage: sage: FFPD = FractionWithFactoredDenominatorRing(R)
    /local/dakrenn/sage/7.0/local/lib/python2.7/site-packages/sage/structure/unique_representation.py:1021: FutureWarning: This class/method/function is marked as experimental. It, its functionality or its interface might change without a formal deprecation.
    See http://trac.sagemath.org/10519 for details.
      instance = typecall(cls, *args, **options)
    sage: sage: f = 5*x^3 + 1/x + 1/(x-1) + 1/(3*x^2 + 1)
    sage: sage: ff = FFPD(f)
    sage: sage: %timeit -n 1 -r 1 ff.univariate_decomposition()
    1 loops, best of 1: 2.24 ms per loop
    sage: sage: %timeit -n 1 -r 1 f.partial_fraction_decomposition()
    1 loops, best of 1: 1.02 ms per loop
    
  • But adding some more terms, we have a speedup:
    sage: sage: from sage.rings.asymptotic.asymptotics_multivariate_generating_functions import FractionWithFactoredDenominatorRing
    sage: sage: R.<x> = PolynomialRing(QQ)
    sage: sage: FFPD = FractionWithFactoredDenominatorRing(R)
    /local/dakrenn/sage/7.0/local/lib/python2.7/site-packages/sage/structure/unique_representation.py:1021: FutureWarning: This class/method/function is marked as experimental. It, its functionality or its interface might change without a formal deprecation.
    See http://trac.sagemath.org/10519 for details.
      instance = typecall(cls, *args, **options)
    sage: sage: f = 5*x^3 + 1/x + 1/(x-1) + 1/(3*x^2 + 1) + 1/(x-2) + 1/(x-3) + 1/(x-4) + 1/(x-5) + 1/(x-6) + 1/(x-7)  # + 1/(x-8) + 1/(x-9) + 1/(x-10) + 1/(x-11) + 1/(x-12) + 1/(x-13)
    sage: sage: ff = FFPD(f)
    sage: sage: %timeit -n 1 -r 1 ff.univariate_decomposition()
    1 loops, best of 1: 1.53 ms per loop
    sage: sage: %timeit -n 1 -r 1 f.partial_fraction_decomposition()
    1 loops, best of 1: 3.3 ms per loop
    
  • The second example of the doctest is already faster with univariate_decomposition as it is:
    sage: sage: from sage.rings.asymptotic.asymptotics_multivariate_generating_functions import FractionWithFactoredDenominatorRing
    sage: sage: R.<x> = PolynomialRing(QQ)
    sage: sage: FFPD = FractionWithFactoredDenominatorRing(R, SR)
    /local/dakrenn/sage/7.0/local/lib/python2.7/site-packages/sage/structure/unique_representation.py:1021: FutureWarning: This class/method/function is marked as experimental. It, its functionality or its interface might change without a formal deprecation.
    See http://trac.sagemath.org/10519 for details.
      instance = typecall(cls, *args, **options)
    sage: sage: f = 5*x^3 + 1/x + 1/(x-1) + exp(x)/(3*x^2 + 1)
    sage: sage: ff = FFPD(f)
    sage: sage: %timeit -n 1 -r 1 ff.univariate_decomposition()
    1 loops, best of 1: 6.07 ms per loop
    sage: sage: %timeit -n 1 -r 1 f.partial_fraction()
    1 loops, best of 1: 9.7 ms per loop
    

I've added a not in the docstring of the method, where this is pointed out.

comment:109 follow-up: Changed 14 months ago by git

  • Commit changed from 1f21184f37244dbdf0395c75f474e4ca9429557f to ae42ad6539aaf99a7986a2bb1c2f018262296d5b

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

cc616fbTrac #10519: fix doctest (simplify symbolic coefficients)
ae42ad6Trac #10519: partial revert of commit 137f3c and follow-up ticket

comment:110 in reply to: ↑ 109 Changed 14 months ago by dkrenn

Replying to git:

ae42ad6Trac #10519: partial revert of commit 137f3c and follow-up ticket

See #19989 for this issue.

comment:111 Changed 14 months ago by dkrenn

  • Cc behackl added
  • Status changed from needs_work to needs_review

Ticket is again at needs_review. I've incorporated the comments above; please cross-review these changes.

A short summary (since the ticket is open for over 5 years now): The original code was posted by Alex Raichev. I've reviewed this code about two years ago. Mathematically it is fine, but it had to be included into SageMath better (see comments above). This is now done and from my part a positive review. However, since I made quite a lot of changes, these changes need a cross-review. Note that I've now marked the code as experimental.

comment:112 follow-up: Changed 14 months ago by tscrim

A few very quick thoughts from a very quick glance:

  • Remove input/output blocks that have nothing. IMO this adds clutter to the docstrings.
  • How experimental/unstable do you think this code really is?

comment:113 Changed 14 months ago by git

  • Commit changed from ae42ad6539aaf99a7986a2bb1c2f018262296d5b to 2056884ccadd2eee615c612cb137b5dd7d7a94f2

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

2056884Trac #10519: remove "Nothing" input/output blocks

comment:114 in reply to: ↑ 112 ; follow-up: Changed 14 months ago by dkrenn

Replying to tscrim:

  • Remove input/output blocks that have nothing. IMO this adds clutter to the docstrings.

Done.

  • How experimental/unstable do you think this code really is?

I think the code is quite stable; AFAIK, Mark Wilson (one of the authors of the corresponding theory behind this) uses basically this code (not from the ticket, but a fork) for his research now for some years. I've marked it "experimental" since it is a new module and the interplay of the code with the whole SageMath-infrastructure was changed on this ticket. This is the part, where there is not that much experience, but this will change once it is in SageMath. If you feel that "experimental" should be remove...I'm fine with any choice.

comment:115 in reply to: ↑ 114 ; follow-ups: Changed 14 months ago by tscrim

Replying to dkrenn:

Replying to tscrim:

  • How experimental/unstable do you think this code really is?

I think the code is quite stable; AFAIK, Mark Wilson (one of the authors of the corresponding theory behind this) uses basically this code (not from the ticket, but a fork) for his research now for some years. I've marked it "experimental" since it is a new module and the interplay of the code with the whole SageMath-infrastructure was changed on this ticket. This is the part, where there is not that much experience, but this will change once it is in SageMath. If you feel that "experimental" should be remove...I'm fine with any choice.

I would be surprised if the (public) API changed much, the current version of the code fits in with the category framework, and it has been/will be (well) reviewed. So I feel that it should not be considered experimental.

We should also update the references (I can do this on my review changes).

comment:116 Changed 14 months ago by git

  • Commit changed from 2056884ccadd2eee615c612cb137b5dd7d7a94f2 to e3668f46714d262e20b7ab7adc514ac6f8e09cd8

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

e3668f4Trac #10519: Revert "mark class as experimental"

comment:117 in reply to: ↑ 115 Changed 14 months ago by dkrenn

Replying to tscrim:

Replying to dkrenn:

Replying to tscrim:

  • How experimental/unstable do you think this code really is?

[...]

I would be surprised if the (public) API changed much, the current version of the code fits in with the category framework, and it has been/will be (well) reviewed. So I feel that it should not be considered experimental.

Good; I did git revert on the corresponding commit.

comment:118 in reply to: ↑ 115 Changed 14 months ago by dkrenn

Replying to tscrim:

We should also update the references (I can do this on my review changes).

Yes, we should. Thanks for doing.

comment:119 Changed 13 months ago by cheuberg

  • Description modified (diff)
  • Milestone changed from sage-6.4 to sage-7.1

comment:120 Changed 13 months ago by git

  • Commit changed from e3668f46714d262e20b7ab7adc514ac6f8e09cd8 to badafce7372353c16c1b6ca658c183957ac2021b

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

64c081aMerge branch 'public/combinat/10519' of trac.sagemath.org:sage into public/combinat/10519
badafceReviewer code and documentation changes.

comment:121 follow-up: Changed 13 months ago by tscrim

  • Reviewers changed from Daniel Krenn, David Loeffler to Daniel Krenn, David Loeffler, Travis Scrimshaw

So I made my pass through the code (finally). I think it looks good with my changes:

  • I added a __classcall_private__ to parse the input for UniqueRepresentation.
  • I moved the (other) static methods to separate functions within the module since (IMO) they were not strongly associated with the FractionWithFactoredDenominatorRing class. It also allows their doc to be included by default (since they do not have to be _hidden) and allows them to potentially be used outside of the class.
  • I moved around some of the documentation within methods as I feel the descriptive information should come before the INPUT/OUTPUT blocks. The input signature of the method is the first set of information given by ? and the documentation.
  • I moved more common imports to the start. There is no danger of circular imports when the file in question is not imported into the global namespace (it is also faster, easier to maintain in the long term, and I'm not as paranoid about these thing).
  • Replaced some Sage implementations with there standard python equivalents.
  • Other misc changes.

If you're happy with my changes, then you can set a positive review.

Perhaps for a followup, we should figure out what the best way is to expose this functionality into the global namespace. Should we just do a lazy import of FractionWithFactoredDenominatorRing?

comment:122 Changed 13 months ago by git

  • Commit changed from badafce7372353c16c1b6ca658c183957ac2021b to a30a18a230a1f77fac00e636b779df8f571eda62

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

a30a18aTrac #10519: two small cross-reviewing changes

comment:123 in reply to: ↑ 121 ; follow-up: Changed 13 months ago by dkrenn

  • Status changed from needs_review to positive_review

Replying to tscrim:

So I made my pass through the code (finally).

Thank you very much.

  • I added a __classcall_private__ to parse the input for UniqueRepresentation.

Good; checked.

  • I moved the (other) static methods to separate functions within the module since (IMO) they were not strongly associated with the FractionWithFactoredDenominatorRing class. It also allows their doc to be included by default (since they do not have to be _hidden) and allows them to potentially be used outside of the class.

I agree that this is a good idea.

  • I moved around some of the documentation within methods as I feel the descriptive information should come before the INPUT/OUTPUT blocks. The input signature of the method is the first set of information given by ? and the documentation.

Ok, looks good.

  • I moved more common imports to the start. There is no danger of circular imports when the file in question is not imported into the global namespace (it is also faster, easier to maintain in the long term, and I'm not as paranoid about these thing).

I'm fine with it. Just out of curiosity, why is this faster?

  • Replaced some Sage implementations with there standard python equivalents.

Ok.

  • Other misc changes.

I've checked the diffs (all 200 hunks); LGTM

If you're happy with my changes, then you can set a positive review.

I've added one doctest to make sage-coverage happier and removed one full-stop.

Perhaps for a followup, we should figure out what the best way is to expose this functionality into the global namespace. Should we just do a lazy import of FractionWithFactoredDenominatorRing?

Maybe. (A lazy import is indeed suitable.)

I set this to positive; all tests pass, doc builds and looks good.

comment:124 in reply to: ↑ 123 ; follow-up: Changed 13 months ago by tscrim

Replying to dkrenn:

Replying to tscrim:

  • I moved more common imports to the start. There is no danger of circular imports when the file in question is not imported into the global namespace (it is also faster, easier to maintain in the long term, and I'm not as paranoid about these thing).

I'm fine with it. Just out of curiosity, why is this faster?

Every time the function gets called, Python needs to check to see if it has imported the object. While this is more on the level of micro-optimization, it can matter in those methods used in a tight loop.

I've added one doctest to make sage-coverage happier and removed one full-stop.

Whoops. Good catch.

Perhaps for a followup, we should figure out what the best way is to expose this functionality into the global namespace. Should we just do a lazy import of FractionWithFactoredDenominatorRing?

Maybe. (A lazy import is indeed suitable.)

I set this to positive; all tests pass, doc builds and looks good.

We also should remove the deprecation warnings in _element_constructor_ on said followup as I forgot to remove them here.

comment:125 in reply to: ↑ 124 ; follow-up: Changed 13 months ago by dkrenn

Replying to tscrim:

Replying to dkrenn:

Replying to tscrim:

  • I moved more common imports to the start. There is no danger of circular imports when the file in question is not imported into the global namespace (it is also faster, easier to maintain in the long term, and I'm not as paranoid about these thing).

I'm fine with it. Just out of curiosity, why is this faster?

Every time the function gets called, Python needs to check to see if it has imported the object. While this is more on the level of micro-optimization, it can matter in those methods used in a tight loop.

Ok, thank you for your explanation.

We also should remove the deprecation warnings in _element_constructor_ on said followup as I forgot to remove them here.

Not a strong preference, but actually, I am for keeping the deprecation for some time. The code of this ticket has been around for about 5 years outside of SageMath (more or less as https://github.com/araichev/amgf), and there the deprecated parameters were used. People who are using this package will transition to the one soon to be included in SageMath, but I think some hints on what to change could be very helpful.

Last edited 13 months ago by dkrenn (previous) (diff)

comment:126 in reply to: ↑ 125 Changed 13 months ago by tscrim

Replying to dkrenn:

Replying to tscrim:

We also should remove the deprecation warnings in _element_constructor_ on said followup as I forgot to remove them here.

Not a strong preference, but actually, I am for keeping the deprecation for some time. The code of this ticket has been around for about 5 years outside of SageMath (more or less as https://github.com/araichev/amgf), and there the deprecated parameters were used. People who are using this package will transition to the one soon to be included in SageMath, but I think some hints on what to change could be very helpful.

Fair enough. Although I think because it had not been reviewed and included in Sage, it is fair game to change the API. However, I don't have a stake in this, but it is something we will eventually want to remove.

comment:127 follow-up: Changed 13 months ago by vbraun

  • Status changed from positive_review to needs_work

There are some tests that depend on ordering of symbolic variables:

sage -t --long src/sage/rings/asymptotic/asymptotics_multivariate_generating_functions.py
**********************************************************************
File "src/sage/rings/asymptotic/asymptotics_multivariate_generating_functions.py", line 98, in sage.rings.asymptotic.asymptotics_multivariate_generating_functions
Failed example:
    s
Expected:
    [{y: 1, x: 1}]
Got:
    [{x: 1, y: 1}]
**********************************************************************
File "src/sage/rings/asymptotic/asymptotics_multivariate_generating_functions.py", line 2828, in sage.rings.asymptotic.asymptotics_multivariate_generating_functions.FractionWithFactoredDenominator.smooth_critical_ideal
Failed example:
    F.smooth_critical_ideal(alpha)
Expected:
    Ideal (y^2 + 2*a1/a2*y - 1, x + ((-a2)/a1)*y + (-a1 + a2)/a1) of
     Multivariate Polynomial Ring in x, y over Fraction Field of
     Multivariate Polynomial Ring in a1, a2 over Rational Field
Got:
    Ideal (y^2 + 2*a1/a2*y - 1, x + ((-a2)/a1)*y + (a2 - a1)/a1) of Multivariate Polynomial Ring in x, y over Fraction Field of Multivariate Polynomial Ring in a2, a1 over Rational Field
**********************************************************************
File "src/sage/rings/asymptotic/asymptotics_multivariate_generating_functions.py", line 4373, in sage.rings.asymptotic.asymptotics_multivariate_generating_functions.coerce_point
Failed example:
    p
Expected:
    {y: 7/8, x: 1}
Got:
    {x: 1, y: 7/8}
**********************************************************************
File "src/sage/rings/asymptotic/asymptotics_multivariate_generating_functions.py", line 4375, in sage.rings.asymptotic.asymptotics_multivariate_generating_functions.coerce_point
Failed example:
    for k in sorted(p.keys()):
        print k, k.parent()
Expected:
    y Symbolic Ring
    x Symbolic Ring
Got:
    x Symbolic Ring
    y Symbolic Ring
**********************************************************************
3 items had failures:
   1 of  77 in sage.rings.asymptotic.asymptotics_multivariate_generating_functions
   1 of  16 in sage.rings.asymptotic.asymptotics_multivariate_generating_functions.FractionWithFactoredDenominator.smooth_critical_ideal
   2 of  11 in sage.rings.asymptotic.asymptotics_multivariate_generating_functions.coerce_point
    [809 tests, 4 failures, 74.86 s]

comment:128 in reply to: ↑ 127 Changed 13 months ago by dkrenn

Replying to vbraun:

sage -t --long src/sage/rings/asymptotic/asymptotics_multivariate_generating_functions.py
**********************************************************************
File "src/sage/rings/asymptotic/asymptotics_multivariate_generating_functions.py", line 98, in sage.rings.asymptotic.asymptotics_multivariate_generating_functions
Failed example:
    s
Expected:
    [{y: 1, x: 1}]
Got:
    [{x: 1, y: 1}]

Hmmm...I thought there is something like a display-hook, which catches such things (orderings in dicts and sets).

**********************************************************************
File "src/sage/rings/asymptotic/asymptotics_multivariate_generating_functions.py", line 4373, in sage.rings.asymptotic.asymptotics_multivariate_generating_functions.coerce_point
Failed example:
    p
Expected:
    {y: 7/8, x: 1}
Got:
    {x: 1, y: 7/8}

The same here...

For the other issues: I am confident to fix.

comment:129 Changed 13 months ago by git

  • Commit changed from a30a18a230a1f77fac00e636b779df8f571eda62 to f58efc98ea4a1781e64250af5fe08339eaab47c8

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

f58efc9Trac #10519: fix sorting of variables (make it platform independent)

comment:130 Changed 13 months ago by git

  • Commit changed from f58efc98ea4a1781e64250af5fe08339eaab47c8 to 85c1f3793979b44878c9e729d2e97b29258f2a7c

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

c37497fTrac #10519: more fixes to make platform-independent
85c1f37Trac #10519: another fix; not really nice... :(

comment:131 follow-up: Changed 13 months ago by vbraun

The displayhook sorts but x, y have no particular order


New commits:

c37497fTrac #10519: more fixes to make platform-independent
85c1f37Trac #10519: another fix; not really nice... :(

comment:132 follow-up: Changed 13 months ago by dkrenn

I've now fixed all (at least I hope I got all) platform-dependent. Can someone please check with other platform than Linux, x86_64 on Intel i5-4690?

comment:133 in reply to: ↑ 131 Changed 13 months ago by dkrenn

Replying to vbraun:

The displayhook sorts but x, y have no particular order

Oh, I see (I thought, that display hooks sort by str in such a case). Thanks.

comment:134 in reply to: ↑ 132 ; follow-up: Changed 13 months ago by tscrim

Replying to dkrenn:

I've now fixed all (at least I hope I got all) platform-dependent. Can someone please check with other platform than Linux, x86_64 on Intel i5-4690?

I didn't see a difference from the original doctests on my laptop, so I can't give an explicit check. However, from looking over the doctestvs and Volker's failures, this seems to do the trick. Although I don't like the changes on ​85c1f37. Instead, I think you should just explicitly check that the dictionary of solutions is the correct one:

sage: s == [{SR(x): 1, SR(y): 1}]
True
Last edited 13 months ago by tscrim (previous) (diff)

comment:135 Changed 13 months ago by git

  • Commit changed from 85c1f3793979b44878c9e729d2e97b29258f2a7c to 3182c5b134f527de94a3728e7394e7fc27014c3e

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

59792e2Revert "Trac #10519: another fix; not really nice... :("
3182c5bTrac #10519: better fix for previous issue

comment:136 in reply to: ↑ 134 Changed 13 months ago by dkrenn

Replying to tscrim: Although I don't like the changes on ​85c1f37. Instead, I think you should just explicitly check that the dictionary of solutions is the correct one:

sage: s == [{SR(x): 1, SR(y): 1}]
True

Reverted and changed; indeed much nicer.

comment:137 Changed 13 months ago by dkrenn

  • Status changed from needs_work to needs_review

comment:138 Changed 13 months ago by tscrim

  • Status changed from needs_review to positive_review

Thanks!

comment:139 Changed 13 months ago by git

  • Commit changed from 3182c5b134f527de94a3728e7394e7fc27014c3e to a951f08123d038f97b809095208bb04c22671a5e
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

a951f08Trac #10519: trivial ReST error

comment:140 Changed 13 months ago by tscrim

  • Status changed from needs_review to positive_review

comment:141 Changed 13 months ago by vbraun

  • Branch changed from public/combinat/10519 to a951f08123d038f97b809095208bb04c22671a5e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.