GSoC 2012 Application Manoj Babu K: Simplification, Term rewriting, Pattern matching

Sean Vig edited this page Apr 11, 2012 · 1 revision
Clone this wiki locally

Personal Details

Name : Manoj Babu K

Email: manoj.babu2378@gmail.com

IRC: Manoj on freenode

Github: manoj2378

About Me

I am a 3rd year Undergraduate student pursuing my Btech in Mining Engineering at Indian Institute of Technology Kharagpur, India.I have a perfect foundation in math and physics, which helped me cracking IIT-JEE AIR 3744.I have secured A grade in Programming and Data structures course.

During my second year i have done many web related projects in php and django.In my third year 1st semister i have developed a nude image detector using the A14 algorithm in MATLAB which is based on supervised machine learning and identifies a picture if nude or non-nude.

This semister i have developed a GUI for reading and writing GIS shapefiles in python using shapefile.py(GSoc 2011 project) and wxpython.I'm an intermediate level coder in python.I have 1 and a half year experience with python.I am comfortable with Git and subversions too.Recently 3 of my patches got merged into sympy.I am a Windows user but comfortable with linux also.

My Contribution to Sympy

  • I have written numerical evaluation of weierstrass elliptic,zeta,sigma funcitons,neville theta, inverse jacobian functions.

  • After going through the sympy code base i have improved the gamma function so if gamma(improper fraction) is called a*gamma(properfraction) be returned. A sort of simplification.Pull 1132

  • Improved rewriting function for sin cos tan etc.Pull 1152

  • Added some identities in trigsimp() . Pull 1202

Project Idea

I would like to work on improving the simplification ,term rewriting algorithms and pattern matching skills as
listed in GSoc ideas page.

Tentative Schedule

Till March 21st I will go through the Code base.

Week 1- Week 2:

Improving the Wild and match functions.And expanding their capabilities

Week 3 :

Implementation of Trigonometric Simplification ref: paper by fu. As i have already done some groundwork on this it would be easy to complete this in a week .By that time match function i have improved may come handy.I am presently stuck with implementing Rulelist2.

Week 4 -5 :

Formatting the rewrite function such that e.rewrite(func, arg) makes a little more meaning or a multiple or power of the function i.e if user wants the expr rewritten as sin(x)2 or e2*x.If there is a double arg func of which user needs only terms involving one arg should be rewritten? Add verbatim and semi-verbatim modes to rewrite()

Week 6-7 :

Implementing similarity measure between expression trees.

  1. Implementing Lattice Based similarity measures for ordered trees.

  2. Implement Boorman and Olivier's approach to develop metrics which is based on Transformation of partitions.These metrics are computationally straight-forward, yet offer a least-moves interpretation at the tree level.

. If the tree is valued, the heights are given. If the tree is bare, heights can be assigned according to the number of elements in the partition.

Therefore, given two trees, there exists exactly one partition at every height for each tree. The problem of calculating a distance between two trees reduces to calculating the distance between partitions, then summing across all heights.

Week 8:

Expression complexity measures using Kolmogorov Expression Complexity.

Kolmogorov Expression Complexity is a easy to learn topic and this is also one of the good ones to use.I'm +1.It also helps the future sympy developers to make their hands dirty in no time.

Week 9 -10:

Implementing expressions signatures and heuristic equivalence testing.

I feel a good resource to learn about this topic would be

http://www.google.co.in/url?sa=t&rct=j&q=&esrc=s&source=web&cd=6&ved=0CEcQFjAF&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.72.9076%26rep%3Drep1%26type%3Dpdf&ei=hzB_T7ffNKGfiAfvv_y8BA&usg=AFQjCNGG3Iq5UnOcc3-77_sZIi085L2idg

This link directly downloads the file and so only google url is the way to go.

This would be good add-on for sympy.

Week 11 -12:

Implenting Semantic Macthing.

Implementing S-match algorithm by Fausto Giunchiglia ,work in collaboration with

Pavel Shvaiko and Mikalai Yatskevich, university of Trento,Hannover , Germany.

The outlines of the research project are found at http://semanticmatching.org/presentations/2004-semantic-matching-giunchiglia-shvaiko-yatskevich.pdf