#10519: analytic combinatorics: new code for computing asymptotics for
multivariate
generating functions
-------------------------------------+-------------------------------------
Reporter: araichev | Owner: sage-combinat
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.4
Component: combinatorics | Resolution:
Keywords: analytic | Merged in:
combinatorics, multivariate | Reviewers: Daniel Krenn, David
generating functions, asymptotics | Loeffler
Authors: Daniel Krenn, | Work issues:
Alex Raichev | Commit:
Report Upstream: N/A | 1f21184f37244dbdf0395c75f474e4ca9429557f
Branch: | Stopgaps:
public/combinat/10519 |
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by dkrenn):
Replying to [comment:98 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.
--
Ticket URL: <http://trac.sagemath.org/ticket/10519#comment:108>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
