GSoc 2017 @ GAGAN ARORA : Rule Based Integration - sympy/sympy GitHub Wiki
Rubi Integrator
About Me
Basic Information
NAME : Gagan Arora UNIVERSITY : Kurukshetra University,India Course Enrolled : Bachelor of Technology in Computer Science Engineering E-mail : [email protected] / [email protected] GitHub Username : clavoirr Blog : www.clavoir.com Time Zone : IST (UTC +5:30)
Personal Background
I am a 3rd year undergraduate pursuing Bachelor of Technology in Computer Science Engineering at Kurukshetra University, India. I have been consistently exposed to the field of Mathematics since my high school, and have taken courses in Higher Mathematics including Algebra(linear,vector), Calculus(Differntial ,integral calculus,Multiple integral beta,gamma functions), Differntial equations,series and transformation(z , Fourier , Laplace) Discrete Mathematics,from B.S Garewal Advanced Engineering Mathematics - I,II & III as well as in Computer Science including Data Structures and Algorithm Design & Analysis in my Graduation.
Programming Experience
I work on Windows 10 home edition with Intel(R) Core(TM) i5 - 4210U CPU @ 1.70 GHz 2.40 GHz machine with JetBrains PyCharm as a python IDE because of it's user-friendliness and quick learning curve. I am very much familiar with version control system and been using Git(command line) and GitHub for quite some time now. I have been programming for over 3 years now, I started with C and then learnt some Object Oriented Concepts and tried C++ and Due my my keen interest in Cyber Security So i started learning Python. I switched totally to Python over an year ago due to the fact that there is little difference between Pseudo Code and Python code, which makes life of a Programmer much easier.I have secured rank #521 at https://www.hackerrank.com/. in python practice track. and also have begginers level knowledge of Wolfram language Favorite Features of Python: Is its Split() function and beautifulSoup library basically used from developing Web crawlers. I was introduced to sympy from GSoC Website from where i start learning sympy from the tutorials On youtube and modules reference and documentation helped me in understanding Sympy Source Code.
The Project
Overview
SymPy is a Python library for symbolic mathematics. It aims to become a full-featured computer algebra system (CAS) while keeping the code as simple as possible in order to be comprehensible and easily extensible.Presently there are a number of algorithms that handles integration:
sympy.integrals.risch.risch_integrate() - Uses Risch algorithm sympy.integrals.manualintegrate.manualintegrate() - do step wise integration.based on rules.
sympy.integrals.trigonometry.trigintegrate() - Integrates trigonometric functions.
sympy.integrals.rationaltools.ratint() - Integrates rational functions.
sympy.integrals.meijerint.meijerg_definite() and sympy.integrals.meijerint.meijerg_indefinite() - Integration using the Meijer G algorithm
sympy.integrals.heurisch.heurisch() - Use heuristic Risch algorithm.
rule based system is new to sympy . It have many advantages over other integration systems:- – Human and machine readable. Since rules are defined using mathematical formulas rather than pro- cedural programming constructs, they express a self-contained mathematical fact that can be attrac- tively displayed in standard two-dimensional mathematical notation. – Able to show simplification steps. The successive application of rules exactly corresponds to the steps required to simplify an expression. Thus when a rule is applied, it can display itself in standard mathematical notation as justification for the step, and then suspend further simplification so the partially simplified result is returned. – Mechanical rule verification. Since the right side of a properly defined rule is just a mathemati- cal expression, the rules validity can often be mechanically verified. For example, the right side of integration rules can be differentiated to see if they equal the integrand on the left. – Facilitates program development. The fact that properly defined rules are inherently self-contained and free of side-effects makes it easy to test the effect on the system of selectively adding, modifying or deleting rules. Although collections of rules may be highly recursive, each individual rule must be able to stand on its own, thus making it possible to test it on examples before adding it to the collection.. – Platform independent. Since properly defined transformation rules consists only of mathematical expressions and pattern matching specifications, the translation of rules from the syntax of one computer algebra system to another is relatively straight-forward. – White box transparency. For the most part, computer algebra systems appear as mysterious black boxes to users with little or no explanation given as to how results are obtained. However, if the source file of rules on which a CAS is based were included with the system, it becomes a transparent white box, making it possible for users to modify existing rules and even add new ones. – Fosters community development. The open source nature of a rule-based repository of knowledge would foster an active community of users. A website blog dedicated to a repository could provide developers the ability to propose new rules and improvements to existing ones. Developers would vie with one another to get credit for adding new rules to the repository. Others would shoot down defective ones. Thus the system would grow and evolve in Darwinian fashion much the same way Wikipedia does. – An active repository. Encyclopedias and reference manuals, even on-line ones, are inherently passive repositories in the sense that users have to find the knowledge required to solve a given problem, and then manually apply it. However, given a problem a rule-based repository actively finds and applies the knowledge required to solve it. Thus the knowledge in such repositories is in a much more useful form.
Plan
Things to do For implementing Rubi Integrator in Sympy :- 1:- Wolfram to Sympy Convertor :- Converting Integral rule from Mathemaica code to python code 2:- rubi engine
Rubi Engine is introduced based on the following steps :-
Step 1:-Transform algorithm :- for converting expression into Sympy Expression eg ( a + b * x )**n =pow (add (a ,mul (b ,x) ) ,n)
Step 2:- A Pattern Matcher based on general n-trees with index
Step 3:- A decision Tree which collect all the Integral rules
Elaborating Each Steps
Wolfram to Sympy Convertor
The Itegration Rules are available atRubi Website are written in wolfram language . There is a parser fullform2sympy.py which transform Wolfram Fullform Expression to sympy expressions but it is limited to some subsets only .My goal is to improve the given Draft so it can parse every Integral Rule
Rubi Engine
Step 1 :- Transform Algorithm
Develop an Algorithm which can make the given input expression in Sympy Expression eg ( a + b * x )**n =pow (add (a ,mul (b ,x) ) ,n)
There Are some rules for transforming the given expression :-
1:The expression in Denominator are converted into numerator eg 1/x**n = x**-n
2:the root are converted into powers sqrt(a + b*x) = (a + b*x)**1/2
3:The expression then converted into Sympy expression (a + b*x)**1/2 = pow(add(a ,mul(b ,x))1/2)
Step 2 :- Pattern Matcher
The Pattern Matcher takes the expression and convert it into the Transformed Expression from Transform Algorithm and generate the Array of unique Key used in making decision in decision tree containing Integration Rule The pattern Matcher is the general n-tree with contain also contain index value at each node The pattern For Algebraic Expression is given Below
http://www.clavoir.com/1.html
the pattern for exponential and algebraic expression is
Rules:-
1:- if "(" occur igore
2 :-put the function() in stack with its node index
2:-it "," occur backtrack to the node at the top of the stack
3:-if ")" occur remove the top of the stack and move the node at stack [new top]
4:- put the index of every node in the list uniq
5:- Tree always start with muliply (a+bx)**m = 1*(a + bx)**m
Example:- from the tree reffernce www.clavoir.com/1.html
expr = (a + bx)**m
transform_Algo(expr) = mul ( pow (add (a , mul ( b , x ) ) , m) )
pass 1
mul ( pow (add (a , mul ( b , x ) ) , m) )
stack = mul
uniq = oo
pass 2
pow (add (a , mul ( b , x ) ) , m) )
stack = mul,pow
uniq = 00,10
pass 3
add (a , mul ( b , x ) ) , m) )
stack = mul,pow,add
uniq = 00,10,24
pass 4
a , mul ( b , x ) ) , m) )
stack = mul,pow,add
uniq = 00,10,24,36
pass 5
, mul ( b , x ) ) , m) ) // backtrack to node 24
stack = mul,pow,add,mul
uniq = 00,10,24,36,34,
pass 6
b , x ) ) , m) )// backtrack to node 24
stack = mul,pow,add,mul
uniq = 00,10,24,36,34,46
pass 7
x ) ) , m) )// backtrack to node 34
stack = mul,pow,add,mul
uniq = 00,10,24,36,34,46,45`
pass 8
) ) , m) )// pop[top]from stack
) , m) )// pop[top]from stack
, m) )// backtrack to node stack[top]
m) )// backtrack to node stack[top]
stack = mul,pow
uniq = 00,10,24,36,34,46,45,25
pass 9
) )// remove stack[top]
)// remove stack[top]
stack = null
uniq = 00,10,24,36,34,46,45,25
Note :- this uniq key is used for traversing decision tree of integration rule
Decision Tree
The pure decision is made with the layers as
www.clavoir.com/2.html
image:http://www.clavoir.com/3
layer 0: Root Node contain unique key
layer 1: it contain sub category of integration is divided eg (algebraic,exponential,...)
layer 3: the sub category further divided into general expressions
layer 4: the decision from layer 3 to 4 depend upon conditions given on rubi integrator website for exact match