GSoC 2017 Report Arif Ahmed : Integration over Polytopes

Arif Ahmed edited this page Jan 6, 2018 · 6 revisions

This wiki page is a summary of the work that I have done during the months of June to August, 2017 on the Integration module in SymPy that deals with Integration of Polynomials over Polytopes. Here is the link to my blog post series which describes the work that I did during the GSoC program. Almost all the work I did was an implementation of the math/algorithms mentioned in this paper.

About Me

I am Arif Ahmed, currently a third year Mathematics and Computer Science student at BITS Pilani Goa Campus, India.

Project Synopsis

My project involved writing a new module in SymPy to extend its integration capabilities. At the time of writing this report(August 28, 2017), this module currently allows the integration of both homogeneous and non-homogeneous polynomials over arbitrary 2/3-Polytopes.

I've implemented most of what I set out to do, and definitely plan to continue after the GSoC period to add the finishing touches to this module.

Pull Requests

Major Implementations

  1. Integration of Polynomials over 2D Polygons : This PR implemented the integration of polynomials with one or two generators over 2D Polygons. Also, this added a new notebook to the /examples/notebooks/ folder detailing the use of the various functions written in the module.

  2. Integration of polynomials over 3-Polytopes : This was the other major PR which involved extending the previous 2D algorithm to 3D. The accompanying notebook was also updated to accommodate the extra methods that was required for implementing this functionality.

Tests and improving functionality :

  1. Change list casting to set casting for decompose() : This was a minor PR to change the return type of decompose() method from list to set. This was necessary due to certain failing test on the master branch. This was the issue raised.

  2. Add Mathematica test cases for 3D polytopes : This PR focused on testing the 3D use-case of the mentioned algorithm with 3-polytopes from PolyhedronData library of Mathematica. On observing the time taken by the algorithm to pass the tests I resolved to port this module into symengine after the GSoC period. Since symengine is written in C++, the time improvement would be a major one.

  3. Compute all monomials upto max_degree(2D case) : If a polynomial is not supplied as input but instead a max_degree is supplied then integration of all monomials with total power less than or equal to the max_degree over the polytope is returned as the result.0

  4. Feature to compute integrals for list of polynomials up to max_degree(3D use case) : If a polynomial is not supplied as input but instead a max_degree is supplied then integration of all monomials with total power less than or equal to the max_degree over the polytope is returned as the result. If a list of polynomials is supplied then those integrals are computed and dictionary of results is returned.

  5. Updating the documentation for the new module : This updates the SymPy docs site with the information on how to use this newly introduced module.

  6. Support for implicit intersecting polygons : In all probability this will not be merged before GSoC deadline(August 29, 2017). This PR addresses the issue of the support for intersecting polygons not existing in SymPy. However, at the time of writing this report this PR has two limitations :

  • The algorithm for computing intersections is not efficient. Needs to be replaced by the Bentley-Ottmann Algorithm.
  • The algorithm doesn't work for polygons with more than two sides passing through the same intersection point.

Eventually, Christopher Smith a long time member of SymPy resolved the issue of implicit intersections by making sure that the order of points in a line segment are kept intact. This is the pull request.

Conclusion

This summer has been a great learning experience. Writing a functionality, testing, debugging it has given me good experience in test-driven development.

If any discrepancies or shortcomings are found in this module I will be more than happy to take it up and work on it. I am grateful to my mentors, Ondrej Certik and Prof. N. Sukumar for reviewing my work and giving me valuable advice. Prof. Sukumar acted an unofficial mentor(that is, not associated with GSoC program) for this project.

Clone this wiki locally
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.