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

[sagetrac-araichev]

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.

CC: @sagetrac-cyril-banderier @zafeirakopoulos @sagetrac-tmonteil @dkrenn @behackl

Component: combinatorics

Keywords: analytic combinatorics, multivariate generating functions

Author: Daniel Krenn, Alex Raichev

Branch/Commit: a951f08

Reviewer: Daniel Krenn, David Loeffler, Travis Scrimshaw

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

[sagetrac-araichev]

Attachment: mgf.sage.gz

[rbeezer]

comment:2

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.

2. 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.

3. 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

[sagetrac-araichev]

comment:3

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?

[seblabbe]

comment:4

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)

[sagetrac-araichev]

comment:6

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

[sagetrac-araichev]

Attachment: amgf_alpha_0_5.sage.gz

New object oriented version