GSoC 2014 Application Deepak Goel: Asymptotic Expansion

deepak7514 edited this page Mar 21, 2014 · 5 revisions
Clone this wiki locally

GSoC 2014 Application Deepak Goel: Asymptotic Expansion

TITLE

SymPy: Support for Asymptotic Expansion

Abstract

SymPy is a computer algebra system (CAS) written in the Python programming language. The model of nested expansion and multiseries allows computing series of a more general class of functions than with ordinary asymptotic series. This is hence an extension of the definition of asymptotic expansions and not only another form of representation. Better support for piecewise and oscillating functions can be seen as an extension to above.

Personal Details

Hi. My name is Deepak Goel, a second year undergrad at Netaji Subhash Institute Of Technology, India. I am pursuing a degree in Computer Science.

Username/Contact information:

Email: deepakgoel7514@gmail.com

Google Code: deepakgoel7514@gmail.com

Github: deepak7514 (also available on gitter)

Deliverables

For my project, I plan on implementing the following:

• Nested Expansions

The idea behind nested expansions is to use iterated logarithms of the variable x, as base elements and to regard exponentiation as an operator on a par with addition. Once an exponential exp only appears if and when the expansion terminates. So expansion typically takes place inside exponentials, and the exponentials nest inside one another. The algorithm to convert a function into its nested form is a bottom-up algorithm. Operations- Add, subtract, multiplication and division, exponential, logarithm, functional inverse. This is well explained in [1], [2] and [7].

• Asymptotic scales and multiseries

All previous implementations rely on a heuristic zero-test for constants and functions. Our aim is to implement a relatively simple algorithm for asymptotic expansions of exp-log functions. The essential idea is to make use of a special type of asymptotic scale called asymptotic basis and to use multiseries with respect to such a basis. Such a series can be used for expansion of exp-log functions, sum, product, inverse functions and for substituting one multiseries into another multiseries or power series. And this is well explained in [1] and [5].

• ASYMPTOTIC ESTIMATION OF OSCILLATING FUNCTIONS USING AN INTERVAL CALCULUS

To date the omission of trigonometric and other oscillating functions from series expansion represents a major gap since asymptotic expansions associated with the differential equations of mathematical physics very typically involve sines and cosines. If we admit the sine function but with arguments restricted to expressions with finite limits then our objects of study lie within a Hardy field, i.e. a field of functions defined on deleted neighbourhoods of infinity in R which is closed under the operation of differentiation. The main idea is to replace functions such as sine and cosine by the intervals in which their values oscillate and then to push these intervals down into the coefficients. Functions such as the tangent have singularities and this has to be reflected in the intervals that replace them. We use the techniques of interval analysis to handle the intervals. Interval Arithmetic is already under progress in pull request #2723 and mpmath module. And if I need more operations on intervals, I would implement them before starting date for coding. This is well explained in [1], [8] and [9].

• Piecewise function

Currently, SymPy supports Piecewise functions and some operations like sorting expr-cond pairs, evaluating nseries, substitution, integration, differentiation but most of these just operate upon only their expression part and leave the rest. For example, series expansion around given point and limit especially at point of discontinuity gives NotImplementedError or some other error. Issue #1216 and #3072 explains my point. So, my work includes fix for these issues and linking Piecewise functions with Interval Arithmetic.

Timeline

I have already been following the SymPy discussion group for some time and have looked at some of the code base, and this will be a great time for me to even better familiarize myself with it so that I can write code that is consistent with the rest of SymPy. I would have no problems starting with the project early and I have already started with basics so that I can jump to coding in a little time.

Beginning of the program

• Week 1-5 Start working with first giving attention to zero equivalence i.e. checking whether given expression is zero. Suppose that we have a tower of set of functions, with an expression f € Fn for which we want to determine a nested expansion, for example. By induction, we may assume that we can do this for elements of Fn-l• Then if fn is given by a simple differential equation over Fn-l, say f n is an exponential or an integral, it is not too difficult to obtain an expansion for fn• The trouble is that fn may partially cancel with elements of Fn-1 in the expression f. This is problem of zero equivalence. Then, according to algorithm in [1], [2]and [7], implement nested expansion and support for various operations.

• Week 6-8 Implement mutiseries according to algorithm in [1] and [5]. Add test cases for asymptotic expansion and documentation. And fix any issues

• Week 9-10 Implement algorithm for asymptotic estimation for oscillating functions using interval calculus with help of [1], [8] and [9]. Basic structure is already available in form nested expansion and mutiseries, so it wouldn't take any much time.

• Week 11-12 Piecewise functions are already in sympy.functions.elementary.piecewise.py. Just requires some additional support and little work with series and limit evaluation. ****• Week 13 ****(fake grace period) Add test cases, documentation, and check any inconsistencies

Related work

Nested Expansion is already supported in MAPLE package. The implementation follows the description in [10]. L(n) denotes the n times iterated logarithm, i.e. L(0) = x, and NF(0,c,£ ) denotes c + £.

e := exp(1/x)-(exp(1/x)-1)/(exp(1/x)): JSnestformInput;

NF( 0,1,-1/L(0)+zinv0(zexp0(1/L(0)))/L(0) – zexp1(1/L(0))/L(0) + zexp1(1/L(0))*zinv0(zexp0(1/L(0)))/L(0) + zexp0(1/L(0)) )

Contribution

https://github.com/sympy/sympy/pull/7316

https://github.com/sympy/sympy/pull/7317

Sources

  1. "Symbolic Asymptotics" – John R. Shackell
  2. "On computing limits in a symbolic manipulation world" – Dominik Gruntz
  3. "Algorithms for Asymptotics I" – Van der Hoeven
  4. "A New Algorithm Computing for Asymptotic Series" – Dominik Gruntz
  5. "Asymptotic expansion of exp–log functions" – Richardson
  6. "Growth estimates for exp-log functions" – J. Shackell
  7. "Nested Expansions and Hardy Fields" – J. Shackell
  8. "Asymptotic estimation of oscillating functions using interval calculus" – J. Shackell
  9. "Asymptotic Expansions with Oscillating Coefficients" – Bruno Salvy and J. Shackell
  10. "Growth Estimates for Exp-Log Functions" – J. Shackell

NOTE:

I want to implement nested expansion and multiseries because calculating mrv (most-rapidly-varying) set involves too much comparison. Whereas multiseries employs asymptotic basis which is comparatively less computational intensive. However if time permits, MrvAsympt algorithm as given in [2] can be implemented by extending code in gruntz.py which is just a matter of some time. I don't even think it would be needed after multiseries and nested expansion but still can be preserved for future use. Even limit computation would benefit from this.