GSoC 2019 Application Nabanita Dash:Series:Improving ring_series,fps and limits - sympy/sympy GitHub Wiki
Improving ring_series,fps and limits
About Me:
The Student:
Name: Nabanita Dash
Email: [email protected],
[email protected]
Phone: +91 8249665459
GitHub profile: @Naba7
Other username : chad7
Time-zone : IST / (UTC + 5:30)
The Institute:
Institute:International Institute of Information and Technology,Bhubaneswar,India
Department: Computer Science and Engineering
Year: Sophomore
Degree : BTech
Programming Background
I have been programming from the past two years in different languages like C,C++,Java,and Python. Out of all I love programming in Python more. Not only I contribute to open source software,but also ardently use it. I have been using Ubuntu as my primary development environment and Git and Github(and sometimes Gerrit) for managing my projects while working in a team. My favourite text-editor is Nano/vim because of its efficiency and easy to use . I also use Sublime text Editor and Jupyter Notebook for my personal projects in python.
Coming to expressing my love for Python(and SymPy in specific),I would like to take this opportunity to explain what certain features of Python I really loved working on.I like python Dictionaries because you can store large data which are related to each other like any other data-structure and extract values with their corresponding keys and values.Till now,I have used python decorator like @XFAIL which I think is an advanced feature for me. I have used it while writing some tests for rs_atan as in #16551
@XFAIL
def test_atan2():
R, x = ring('x', EX)
assert rs_atan(I,x,5) == EX(atan(I))
assert rs_atan(I + a,x,3) == EX(atan(I +a))
assert rs_atan(I*a,x,3) == EX(atan(I*a))
I like that SymPy has set up all its small tasks such as as_numer_denom , as_independent and larger modules such as series,integrate in an ordered fashion. It is so huge that it has covered almost everything. Symbolic integration and series expansion are my favourite. My favourite feature is SymPy is rational_independent which returns a list of all the rationally independent terms.
eg.
>>> rational_independent([x**2, sin(x), x*sin(x), x**3], x)
[x3+x2,xsin(x)+sin(x)]
As a college project I have used LaTeX as in @here
I am interested in Machine learning,Deep learning especially Natural Language Processing. Below are the links to my projects:
My mathematical background is sufficient for the project as I have taken courses on Discrete Mathematics,Ordinary Differential Equations and Partial Differential Equations,Computational Number Theory,Linear Algebra.I am familiar with real and complex analysis.
My Contributions
I am a contributor of Coala organisation. I had participated in Coala winter of code in last year and I got introduced to open source for the first time.
1)SymPy
I have contributed to evalf, sets, subs,rs_series in SymPy. I have read almost the whole of series module as well as polys module.I really want to continue that streak with Google Summer of Code contributing to ring_series as well as series module.
Merged Pull Request
#16198 : I resolved this while I had created an issue #16193 ,git:// don’t do server notifications but https:// do.
#16402 : Changed mpf(0) to None in S.Zero
Other Pull request
#16377 : changed mpf(0) to None (closed)
#16551 : Added tests for rs_atan(open)
#16403 : Calling EmptySet using singleton(open)
#16479 : Created a function for iterable objects called as
_subs_args(open)
#16525 : Added a new function rs_acos(open)
Issue Raised
#16193 (closed) : git:// don’t do server notifications,but https:// does
As a college project I have used LaTeX as in Algorithm_questions
2)Jupyterhub
I had participated in Outreachy last year during October,I contributed here. I had to write some code for an authenticator to read names and passwords from a csvfile and check against a list and authenticating the actual users. The open pull request is : @here
3)
I successfully completed the Hactoberfest @here which boosted up my contributions to open source.
My GitHub profile is @Naba7
4)Gensim
I have contributed to Gensim finding it the best place for first-timers who get introduced to NLP. Some of my contributions are :
Issues raised:
#2337 : module object was not callable
#2338 : Documentation issue;mistyping of matrices
#2348 : Sign of lsi_vector gets reversed
#2352 : veclen documentation
Pull-requests:
#2247 : fixed typo in KeyedVectors.wmdistance
#2250 : tried fixing a bug which appeared
5)Yellowbrick
I actually started to know git and contributed to yellowbrick.
Issues Raised:
#701 : Matplotlib version(>=3.0.0) don’t support Yellowbrick
#702 : Broken links on quickstart documentation
#703 : Update fit to fit_transform in Jointplot plot
#709 : Update prediction error plot in docs
#716 : JointPlot visualiser was not poofing
#722 : data folder is not created
#723 : Parallel coordinates have different index
Merged Pull requests:
#715 : Repairs broken links in documentation for rank2d and jointplot
#755 : changed labels to y vector,passed labels as list
Code-base Blog
I had written a code-base blog using yellowbrick in one of my personal projects on detecting crimes at a particular place. The link to repository is NYPD_Hunchlab
6)Haiku
Tickets involved with:
#1131 : Added my name to contributors list
#1195 : TranslationErrors.h has been moved to a different location
#86 : Typo in file attachment as well as added hi.catkeys to translate document to hindi
My Project:
Series expansions:Improving rs_series,Formal Power Series(series.formal),limits(series.limits)
Abstract:
The present series function in SymPy is very slow and full of issues and errors.In 2015 rs_series was implemented as GSoC project and now Taylor series is completely defined though not all ring_series functions have been implemented.I want to implement Laurent series and Fourier series so that negative powers can be handled using rs_series. I want to add more ring_series functions to make it more efficient to handle. As a sum of this rs_series will then be ready to get merged as main series function in SymPy. I plan to improve formal power series by adding hyperbolic arc trigonometric functions and improve limits code by adding more special functions.
Introduction:
In mathematics, a series expansion is a method for calculating a function that cannot be expressed by just elementary operators such as addition,subtraction,multiplication or division.The resulting series is often limited to a finite number of terms,resulting to an approximation.SymPy uses more number of terms to get the most accurate answer.Still,the accuracy is not reached.The omitted terms lead to define Big O notation.Big O notation describes the limiting behaviour of a function when it tends towards a particular value.The series expansion on an open interval is an approximation for non-analytic functions.Use of Asymptotic expansion will make SymPy strengthen its series module.Several kinds of series expansions used in SymPy are Fourier Series and Formal Power Series.Mostly we need to use limits of certain functions to see and get a hold of its graph and its slope from a certain value to a certain another value.SymPy has its own module to calculate limits of functions using Gruntz Algorithm.So,it is important to introduce all different defined series and their transforms in SymPy.As well improving the limits will increase the efficiency of Big O notation in SymPy as well as for asymptotic expansions.
Series in SymPy include only Fourier Series and Formal Power Series.They have a clear-cut structure and functions that accomplishes small tasks as well as their transforms.The issues with labels series expects to resolves all the problems and shortcomings of present series module.
I am working on those issues as well as checking into XFAIL tests.
As discussed with mentor Sartaj Singh,he has suggested to look into rs_series as well as into ring_series to add more functions and improve the present functions . He has asked me to check XFAIL tests of formal power series as well as look into limits code for improving it.
Phase 1
Improve rs_series
Almost all the different series like Fourier,Taylor,Laurent,Stirling,Dirichlet,Puiseux,etc expand upto infinity in the domain of the function.Since,it is not possible to calculate the series upto infinity,we calculate it upto a certain point defined in its domain. So,we approximate it to be as for example:
Sum(1/1-x)= 1 + x + x**2 + x**3 + x**4 + x**5 + ..... for -1<x<1
Series when calculated upto a certain degree such as n gives an approximate but not an accurate solution. The finite series converts into a polynomial such as Sum(1/1-x) = 1 + x + x2 + x3 + x4 + x5 + ..... + x**n. Calculating the series-expansion turns to calculate the polynomial. SymPy makes efficient use of sparse polynomials for calculating the series-expansions. Manipulating series as multivariate polynomials is faster and more efficient rather than using SymPy series method which uses Gruntz algorithm or like formal power series which uses rational algorithm or DE.All the functions expand on any given series on some particularly specified ring. The coefficients of the calculated series depend on the ring being used.
>>> R, x, y = ring('x, y', RR)
>>> rs_sin(x*y, x, 5)
-0.166666666666667*x**3*y**3 + x*y
rs_series is a function thats takes an expr and returns its expansion by using ring series functions.Basically,it returns a polynomial over the simplest possible ring and recursively builds the ring.
>>> rs_series(sin(a + b)*cos(a + c)*tan(a**2 + b), a, 2)
cos(b)*cos(c)*tan(b)*a - sin(b)*sin(c)*tan(b)*a + sin(b)*cos(c)*tan(b)
It takes very less time to manipulate and return values.
>>> %timeit ((sin(a) + cos(a))**10).series(a, 0, 5)
1 loops, best of 3: 1.33 s per loop
>>> %timeit rs_series((sin(a) + cos(a))**10, a, 5)
100 loops, best of 3: 4.13 ms per loop
In order to know which ring is used for the given expression,rs_series uses sring and other functions of polys.
rs_series is not so developed,so I want to develop and create some functions that it can be completely replaced by series in SymPy.
Expressions involving fractional powers and constant fractional powers will never simplify which leads to similar issues as manipulating with Laurent series and Puiseux series.Then we will isolate polys and series behaviour from one another and introduce a boolean flag series in the list of allowed Options for polynomials in sympy.polys.polyoptions.Options. Thus, when we want sring to allow rational exponents we supply a series=True flag to sring.
Since Taylor Series has already been well defined as in rs_series.I plan to implement rs_laurent,rs_fourier,rs_fourier_transform,rs_maclaurian using polys module only .I want to improve it so that laurent series can be used by PolyRing element rather than switching between options.
Below,I have tried a non-working example of Laurent Series as rs_laurent
class LaurentSeries(obj):
def __init__(cls, data):
pass
class rs_laurent(LaurentSeries):
def __init__(self,data):
x = (data.atoms(Symbol)).pop()
lead = data.extract_leading_order(x)
if lead < 0:
self.ring, self.series = sring(data * (x**(-lead)), domain=QQ)
elif isinstance(data, PolyElement):
self.series = data
self.ring = data.ring
else:
self.ring, self.series = sring(data, domain=QQ)
def __check_analytic__(self):
if self.is_analytic:
return analytic_points
else:
return False
def __sum__(self,analytic_points):
while i < analytic_points:
PolyRing(self,data)
while i > analytic_points && i < analytic_points:
PolyRing(self,data)
while i > analytic_points:
PolyRing(self,data)
def __analytic_points__(self,data):
return analytic_points
def __constant_integrate__(An):
An= 0.5*pi*i * rs_integrate(self/(expr)**(n+1),x)
return An
def __add__(self,other):
return rs_laurent(self.series + other.series)
def __mul__(self, other):
if(self.ring.ngens == 1 and other.ring.ngens ==1):
x = ((self.ring).gens)[0]
prec = min((self.series).degree(), (other.series).degree()) + 1
return rs_laurent(rs_mul(self.series, other.series, x, prec))
def __pow__(self, n):
if(self.ring.ngens == 1):
x = ((self.ring).gens)[0]
prec = (self.series).degree() + 1
return rs_laurent(rs_pow(self.series, n, x, prec))
def __div__(self, other):
if(self.ring.ngens == 1 and other.ring.ngens == 1):
x = ((self.ring).gens)[0]
return self * other**(-1)
For rs_fourier,we can use
def __fourier_cos__(func,limits,n):
x,L=limits[0],limits[2]-limits[1]
cos_term = 2 * cos(2*n*pi*x/L)* rs_integrate(func * cos(2*n*pi*x/L,limits),n)/L
a0 = cos_term.subs(n,S.Zero)/2
return a0,cos_term
def __fourier_sin__(func,limits,n):
x,L=limits[0],limits[2]-limits[1]
sin_term = 2 * sin(2*n*pi*x/L)* rs_integrate(func * sin(2*n*pi*x/L,limits),n)/L
return sin_term
b)The present ring_series needs to be improved by adding more functions to it.I want to implement new ring_series functions for making it easier to handle. Like there isn't any ring series for rs_csc for cosecx series or for secx series. I want to add it to ring_series to make the implementation of other functions using these will be smooth and efficient.
csc x = x**(-1) + x/6 + 7*x**3/360 + 31*x**5/15120 + ... , for 0<|x|<pi
sec x = 1 + x**2/2 + 5*x**4/24 + 61*x**6/720 + ... , for |x|<pi/2
In ring_series there is already rs_exp. Negative exponential index is required to most of the times for calculating any series. It can be calculated as rs_negative_exp = rs_cos*2 - rs_exp.
I plan to implement inverse trigonometric functions as rs_acos, rs_asec, rs_acsc, rs_acot, rs_asinh, rs_acosh.
I have submitted a patch for rs_acos as in #16525. I will add more features to it.
Phase 2
Improve Formal Power Series
1)The limits applied to check fps and calculate logarithmic singularity needs improvement as it creates XFAIL tests.I want to create an API that accepts the singularities points and revise it to give positive results.
>>>f = asech(x)
>>>fps(f, x)
log(2) - log(x) - x**2/4 - 3*x**4/64 + O(x**6)
A logarithmic singularity is a singularity of an analytic function whose main z-dependent term is of order O(lnz). An example is the singularity of the Bessel function of the second kind
Y_0(z)∼(2gamma)/pi+2/pi ln(1/2z)+... at z=0
,Green function and some trigonometric functions.
Singularities with leading term consisting of nested logarithms, e.g., lnlnlnz, are also considered logarithmic.
The reference and example is from mathworld.wolfram
hyperbolic arc sine
Function ASinH(value As Double) As Double
ASinH = Log(value + Sqr(value * value + 1))
End Function
hyperbolic arc cosine
error if NUMBER is inside the range [-1,1]
Function ACosH(value As Double) As Double
ACosH = Log(value + Sqr(value * value - 1))
End Function
hyperbolic arc tangent
error if value is zero
Function ATanH(value As Double) As Double
ATanH = Log((1 / value + 1) / (1 / value - 1)) / 2
End Function
hyperbolic arc cotangent
Function ACotH(value As Double) As Double
ACotH = Log((value + 1) / (value - 1)) / 2
End Function
hyperbolic arc secant
error if value is outside the range [-1,1]
Function ASecH(value As Double) As Double
ASecH = Log((Sqr(1 - value * value) + 1) / value)
End Function
hyperbolic arc cosecant
Function ACscH(value As Double) As Double
ACscH = Log((Sgn(value) * Sqr(1 + value * value) + 1) / value)
End Function
the reference is from devx
I want to add these series to improve and check logarithmic singularities in formal power series.
2)Some symbolic summation series also don't work because of non-linear terms in series.
f = x**n*sin(x**2)
print(fps(f, x).truncate(8))
output:ValueError:
(n**2 + 2*n)/x**2 contains non-linear terms in the variables to be evaluated
f = x**(n - 2)*cos(x)
print(fps(f, x).truncate())
output:ValueError:
(n**2 - 3*n + 2)/x**2 contains non-linear terms in the variables to be evaluated
f = x**n*log(1 + x)
fp = fps(f, x)
k = fp.ak.variables[0]
output:ValueError:
_k*(_k + 1) + n**2 - 2*n*(_k + 1) + n contains non-linear terms in the variables to be evaluated
So,I checked the error is in formal.py as well as in solveset. I will modify the truncate() as well as fps code to make it work with non-linear terms of the variable.
Phase 3
Improving Limits
I would like to add special functions for calculating limits at oo.
According to, #14590 and #15055 some special functions have been used in limits code,are not implemented till now. As the below example shows:
def test_exponential2():
n = Symbol('n')
assert limit((1 + x/(n + sin(n)))**n, n, oo) == exp(x)
gives Limit((x/(n + sin(n)) + 1)**n, n, oo, dir='-')
while
limit((1+x/n)**n,n,oo) gives exp(x).
limit(sin(n),n,oo) gives AccumBounds(-1, 1) and limit(n+sin(n),n,oo) gives ``oo`.
These limits use numer_denom and after that the special functions of limits is not used,so this results to wrong outputs.
As,well these are some of the limits which have not been implemented yet.
1) limit(1 + 1/2 + 1/3 + 1/4 + 1/5 + ..... + 1/n ,n,oo) = oo
NotImplementedError
2) limit(n/(n!)**(1/n),n,oo) = exp(n)
Wrong Result is printed as 0
3) limit(sin(a*x)/b*x,x,0) = a/b , for b!=0
Wrong Result is printed as 0
4) limit(N**x,x,oo) = 1*sign(1/(N-1))
NotImplementedError
5) limit(N**(1/x),x,oo) = 1, for N>0;0, for N=0;doesn't exist, N<0
NotImplementedError
6) limit(x**(1/N),x,oo) = oo, for N>0
NotImplementedError
I plan to implement above mentioned limits and improve limits code.
TimeLine:
I have made a tentative timeline to follow.I will stick to my timeline and be as much efficient as it requires.I am available for 35 to 40 hours a week from May 6,2019 to September 3,2019.
Pre-GSoC
I am planning to get a hold of SymPy during April-May.I will resolve as many issues as possible and read the complete documentation of polys and series modules. I have already started implementing one of the function rs_acos of ring_series and will try to merge all the pull-requests that I have opened.
Community Bonding Period(May7-May26)
During this time I will discuss with my mentors and come up with a proper design document and implementation details covering the asks. Since I have already worked on the codebase extensively, I can focus more on the implementation challenges.
Week 1,2
I will start off working on Phase 1,as it will take more time than other phases.First I will implement rs_laurent with a rough class-structure creating a new module. I will be adding more new functions after discussing with my mentor.I will write tests for them.I will document my work too.
Week 3,4
I will add those ring_series functions as mentioned above in Phase-1 part b and c . I will clear all the tasks of week 1,2 if there will be anything left out.I will write tests for them.
Week 5
I will complete and wrap up everything of Phase-1 and start working on phase-2 as well as discuss ideas and implement them.I will document my work too.
Week 6,7
I will start working on Phase-2.I will implement singularity_check method as well as improve truncate() method of formal power series as mentioned above and write tests for them.
Week 8,9
I will wrap up everything in phase-2 .I will document my work too.
Week 10,11
I will work on phase-3 ideas and discuss with my mentor. I will write tests for them as well as complete the whole work.I will document my work too.
Week 12
I will complete the left-out work and plan to write a blog on the work-done,my experience with SymPy as well as with the mentors.
Post-GSoC
I plan to work and understand the complete code-base as SymPy has fascinated me.I will continue helping new-comers and continue contributing to SymPy.
Commitments:
-
As I started resolving issues in SymPy,I liked the ring_series module and concept used in SymPy. It fascinated me as only polynomials were used to represent series and manipulate them using other ring_series functions.As I started exploring I got a hold of it and now I plan to improve it. I’m confident that I can finish this project in time and meet all the objectives .I will be constantly contributing to SymPy,resolving issues ,improving ring_series functions and continue learning with SymPy.
-
I can give 35-40 hours per week for 3 months to SymPy.I can give more time if required to clear backlogs.
-
I am participating in Outreachy this summer in Haiku organisation.I have talked with my mentor and he has given his consent to my participation in GSoC-19. If selected, I will give 30-35 hours to Haiku.
-
SymPy will be my first priority during the summers. With the help of my mentor Christopher Smith,Sartaj Singh,Kalevi Suominen I will be able to accomplish whatever I have planned.
References:
-
https://groups.google.com/forum/#!searchin/sympy/series/sympy/hiRuIHa8ImA/JLOBsMr9yUcJ
-
https://github.com/sympy/sympy/wiki/GSoC-2019-Ideas#series-expansions
-
"Formal Power Series" by Dominik Gruntz and Wolfram Koepf
-
"Computing limits of Sequences" by Manuel Kauers
-
https://www.coursera.org/lecture/complex-analysis/laurent-series-BRQHO
-
http://sites.millersville.edu/bikenaga/abstract-algebra-1/polynomial-rings/polynomial-rings.html