GSoC 2016 Application Vic Luo: Port SymPy's new Assumtions to SymEngine and improve its performance

lz96 edited this page Mar 24, 2016 · 2 revisions
Clone this wiki locally

##Personal Information Name: Zheng Luo/Vic Luo

Github username: htfy96

University: Shanghai Jiaotong University

Email: vicluo96@gmail.com

Timezone: GMT +8

Github: htfy96

I am a second-year university student majoring in Computer Science. The first line of my code was written in 2009. and I have spent lots of time on algorithms and coding since then. Now I work in a school laboratory that focuses on paper citation/coauthor network.

##Programming ###Platform and Editor In most cases I work in Arch Linux and Vim is my second-to-none choice when writing C++ programs, because C++ don't have very long method names or well-structured syntax like Java, therefore IDEs could only play a limited role in assisting coding. But I have to admit that when refactoring code, IDEs, such as CLion, tend to be more powerful than Vim+Plugins, while Vim wins in its keybindings and simplicity.

###Experience From 2009 to 2013, I took part in various programming competitions using Pascal, and ranked 18th in my province among 200+ competitors. Then, in 2014, I switched to C++/Python and implemented several programs:

  • https://github.com/htfy96/network_algo C++ network computation
  • https://github.com/htfy96/htscheme A tiny Scheme interpreter written in C++
  • https://github.com/htfy96/nanoSearcher A simple search engine based on PyLucene

My favorite feature of Python is its explicitness - unlike Ruby whose philosophy is there are a lot of ways to do one thing, Python stands for there is only one way to do things like this, which is quite suitable for a scientific computation framework.

I have used git for around two years and got quite familiar with version management as well as resolving conflicts.

##Project Proposal In this proposal I plan to port SynPy's new assumptions module to C++ in SymEngine. Also, I'm going to work on the improvement of algorithm.

###Qualification

  • I learned Discrete Mathematics, Calculus, Linear Algebra in my first year and have a good understanding of propositional logic.
  • My algorithm skills would also be helpful in implementing this module and speeding up the code. I took part in algorithm contests since 12 years old and had extensive experience in the application of algorithm.
  • Before this I have contributed to several open-source projects as a C++ programmer, which could prove that my programming skills are qualified for this position.

###Previous work SymPy has just implemented a new assumptions module, which hasn't been ported to SymEngine yet.

According to https://github.com/sympy/sympy/blob/master/sympy/assumptions/ask.py#L1255 , current implementation includes limited optimization and follows the following steps:

  • Transform assumption to a SymPy object, and get its CNF by calling to_cnf
  • Extract related predicates in assumption
  • Return result in some simple cases
  • Use satisfiable to judge proposition and assumption / ~proposition and assumption

Additionally the wiki mentions that the performance could be improved through caching previous logic inference, and it seems that no cache except known facts exist in repository.

###Project Details

Despite porting current code to Sympy, the following work is planned to be done during GSoC 2016:

  • Improving code quality, including unifying format with clang-format, refactorization, etc
  • Paralleling inference(based on of C++11) since prop and assumption / ~proposition and assumption could be judged simultaneously
  • Bug fixes e.g. ask(Q.is_true(True), Q.even(x) & Q.odd(x))
  • Caching inference result inside map<pair<assumption, subproposition>, bool >

###Schedule My summer vacation is from June 20th to September 10th. I'm going to stay at school and work 40h/week during that time. Before that about 5~10 hours/week could be spent on this project.

Here is my schedule:

  • May 23rd to June 10th : Reading code of sympy.assumptions and SymEngine and porting current implementation to SymEngine
  • June 10th to June 20th: Bug fixes, writing documentation and improving code quality
  • June 21st to June 28th : Mid-term evaluation
  • June 29th to July 6th: Reading papers about inference engine optimization
  • July 7th to July 21st: Implementing optimization and test
  • July 22th to July 31st: Writing documentation of optimization and evaluating performance of it
  • August 1st to August 14th: Code cleanup, fixing issues

###Contribution I reviewed some code in SymEngine and opened https://github.com/symengine/symengine/issues/839 to give some suggestions on code quality.

https://github.com/symengine/symengine/pull/844 , which includes some refactorization, was merged into the repository.