GSoC 2017 Rule Based Integration Report

About Me

My name is Arihant Parsoya. I am a junior undergraduate student at Indian Institute of Technology Bombay. My GSoC project was to implement rule based integration module in SymPy.

Rule Based Integration

Rule based integration (Rubi) consists of ~10,000 transformation rules. Computer Algebra System(CAS) can match the integrand with the right rule to directly solve the integration without using general integration algorithms. Adding Rubi frees developers of algorithms from having to worry about the annoying and trivial problems and the special cases, and instead focus on the genuinely hard and interesting problems.

Community Bonding Period

My original plan was to implement pattern matching module in SymPy which would be optimised for our project and then create a decision tree by parsing Mathematica rules.

After my selection for GSoC, we came across MatchPy(which has good pattern matching capabilities) and decided to use it for implementation of our module. MatchPy is a pattern matching library which has matching capabilities similar to Mathematica. MatchPy compiles many patterns into a discrimination-net which is efficient for matching an expression with multiple patterns. Detailed disctiption on the algorithm MatchPy uses can be found here. However, MatchPy is only implemented in Python3.6 because of which we could not use MatchPy for Python<3.6 versions of SymPy. I tried to use 3to2 to make MatchPy code compatible with Python<3.6 but it turns out that MatchPy also has few external dependencies and they also had to be added into SymPy.

Coding Period

We decided to implement the module only for Python3.6 using MatchPy hoping that we could do code-generation of rules once we added all the rules to MatchPy’s ManyToOneReplacer. Manuel Krebber helped us a lot in adding support for optional arguments and code-generation in MatchPy. Our plan was to generate code of discrimination-net which was compiled by MatchPy. Code generation of rules would help us to remove the dependency on MatchPy and make the module useable for Python<3.6. Unfortunately, the code generation still has the dependency on MatchPy.

Implementations / work done

  • Utility functions. These are helper functions for the module for integration. The functions are written in Mathematica. We have re-written those rules into SymPy.
  • Python parser for rules written in Mathematica. The parser takes FullForm[DownValues[]] of the rules as input and convert them into Python format. The parsed output are MatchPy Patterns and ReplacementRules which can be used to compiled as a discrimination-net using MatchPy.
  • Added rules in MatchPy’s ManyToOneReplacer. The work done could not be merged since it has dependency on MatchPy and is not fully tested.

Merged Pull Requests

Future Work

The module so far is not really usable due to its high loading time and dependency on MatchPy. In my opinion, to add Rubi to SymPy, we need to implement MatchPy capabilities into SymPy(along with code generation) so SymPy doesn’t have dependency on MatchPy. There is some work left in the current module which could not be completed since they require longer time than available:

  • Testing all the rules. There are thousands of tests in Rubi test suit. All the tests should be tested properly. I have done majority of tests in linear_products. Testing takes lot of time since Rubi takes time to load. Every failure needs to be investigated individually. For debugging purposes, Francesco helped us create get_matching_rule_definition function which helps us identify the rule which is getting matched.
  • Code generation of rules. In my opinion, it is important to complete the test suit of Rubi. Code generation can be done after that.
  • Adding support for Piecewise functions.

Conclusion

I am grateful to work with my mentors Francesco Bonazzi and Ondřej Čertík for this project. They were really supportive and guided us well through the challenges we faced. I am thankful to the SymPy community to believe in my capabilities and give me the opportunity to work in this project. I would also like the thank Manuel Krebber for helping us by adding more features into MatchPy.

Post GSoC

I plan to continue working with SymPy to help it grow by adding more functionalities. I may even apply again in a future year to implement some other thing in SymPy, or maybe apply as a mentor for SymPy to help someone else improve it.

References