GSoC 2012 Application Bharath M R: Plotting Module
Name : Bharath M R
Email: catchmrbharath@gmail.com
IRC: catchmrbharath on freenode
Github: catchmrbharath
I am a fourth year Electrical Engineering student at IIT Madras, India. I have a decent knowledge of programming. I started out with C++, which I mainly use to compete in algorithm contests. I started using python(scipy and numpy) as an replacement for scilab to most of my assignments in Electrical Engineering. I have mainly used python for filter design, numerical linear algebra, and minimization problems in Electrical Engineering. I also have a decent knowledge of the Django framework and was one of the developers of www.shaastra.org/2011/main/home.
I work on a Linux Mint Debian Edition machine and I am a ardent user of Vim. I started using git seriously in the last 3-4 months and I am still discovering the tool.
A plotting module is an essential part of any CAS. It helps to visualize functions and understand the intricacies which might not be possible with analytic results. SymPy already has an plotting module based on matplotlib (pending merge) for plotting explicit functions. I would like to implement the plotting module based on matplotlib for implicit functions. The project will aim at implementing an extension to the plotting module [3], which will be able to graph implicit functions and region plots.An interval arithmetic library for Numpy will also be implemented.
The implementation of the plotting module will be largely based on the publication [1].
I will also implement a plotting backend for svgfig and integrate it with SymPy Live. This will allow us to plot functions on SymPy Live. I will also be implementing a basic implementation of adaptive sampling based on [2].
My semester exams end on May 4th. I plan to work according to this schedule though there might be some uncertainties.
Community Bonding Period
- Explore the current code base for plotting.
- Try to add adaptive sampling for Stefan's request [2].
- Read through Jeff Tupper's MSc thesis [4] which deals with Interval Arithmetic in detail.
Week 1 -2
Implement the basic plotting as mentioned in Procedure 1 in [1] with mpmath interval arithmetic.
>>> plot(y < x + 1/3,(x, -1, 1),(y, -3, 3))
>>> plot([y < x**2 -1,(x, -2, 2),(y, -5 , 5))Week 3
Extend the mpmath library to implement functions which are not implemented in the main mpmath library like Floor, inverse trigonometric functions etc. These are not implemented for interval arithmetic in mpmath. Add functionality for domain tracking. Integrate it to the plotting module. Make a pull request.
>>> plot(y < x**0.5, (x, -2 , 2), (y, -2, -2))
>>> plot(Abs(x) + Abs(y) < 1, (x, -1, 1), (y, -1, 1))Week 4 - 5
Implement sub -pixel computation as mentioned in Algorithm 2 [1]. Also add continuity tracking and Interval Sets to interval arithmetic for the functions that SymPy will support. Add support for operators like Min, Max.
>>> plot(Min(cos(x) + sin(y), sin(x) + cos(y)) < 0, (x, -3.14, 3.14), (y, -2, -2))
>>> plot(y > 1/x, (x, -2, -2), (y, -5, 5))Week 6
Add branch cut tracking and improve the plotting module as given in Algorithm 3.2 [1].
>>> plot(Floor(x) < Floor(y), (x, -3, 8), (y, -1, 5))Week 7
Write tests and documentation for the plotting module. Clean up the module based on the review. I should have a working plotting module based on mpmath interval arithmetic by the end of this week. Make a pull request.
Week 8-9 ( Midterm Evaluation)
Extend the plotting module and the interval arithmetic class to use Numpy for evaluating functions. The plotting module will then support both Numpy and mpmath, the former for speeding the plot and the latter for plots which require high precision numbers.
Week 10
Write a tutorial on how to use the implicit plotting module. This will be similar to Scipy cookbooks. It will be a showcase of all the things you can do with the plotting module. Add docstrings to Sphinx documentation. Make an atomic pull request.
Week 11 -13
I will be done with the implicit plotting module. I would like to work on the back end for svgfig and integrate it with SymPy Live. This will provide us way to plot on SymPy Live. Make the pull request to get it merged. Send a mail to the group, on what other functions other than the basic ones has to be supported, and try writing rules for their evaluation.
I will be extending the BaseSeries class of [3] and writing a separate plot function for implicit functions. During the initial stages, when I am not using my extended interval arithmetic library, I will be using lambdify for my evaluations. When I start using my extended interval arithmetic library I will call the eval function with the expression in Interval Arithmetic class for a given interval. I will reusing expression parsing from lambdify and the evaluation will happen according to a set of rules for each function. Once the expression is satisfied by the interval, we use the matplotlib's fill_between to fill the interval region. I am also looking also at the polygon class to see whether it is possible to use it and fill rectangular regions.
We recursively subdivide the plotting region into smaller blocks and verify whether the expression is valid in the block. This will result in 3 results.
-
<T,T>if the expression is valid throughout the block. -
<F,F>if the expression is not valid anywhere in the block. -
<T,F>if the expression may or may not be valid in the block.
If we have a <T,T>, then that block can be colored.
If we have <F,F>, the block can be colored white.
If we have <T,F>, then the block has to be subdivided and probed.
The recursion goes on till we reach to a block size of 1 pixel.
####Subpixel Computation.
The general Pixel refining algorithm recursively checks whether an expression is valid only up to a pixel level ie. the maximum resolution of checking is the pixel. Sometimes we will have situations where it cannot be decided whether a particular pixel has to be included or not. Subpixel Computation probes into regions inside the pixel and decides whether the pixel has to be included. Though it may seem that subpixel computation is unnecessary when using matplotlib, it will be necessary when plotting implicit equations with
equality like e**y = x.
####Interval Arithmetic
I will have a basic implementation of the plotting module based on mpmath interval arithmetic. As the complexity of the algorithm increases, I will have an extended interval arithmetic class which derives from
mpmath interval arithmetic. This will have domain, continuity and branch tracking.
Each function operating on the interval should update these values.
#####Domain Tracking
Domain tracking helps to avoid handling interval arithmetic for values where the function is not defined. We will have two boolean values <c,d> for each interval which determines whether interval is completely defined.
-
<c,d> = <T,T>if the evaluation is well defined throughout the interval. -
<c,d> = <F,F>if the evaluation is not defined anywhere inside the interval. -
<c,d> = <T,F>if the evaluation may or may not be defined in the interval.
#####Continuity Tracking
We will have two Boolean values <e,f> for each interval.
-
<e,f> = <T,T>if the evaluation is continuous throughout the interval. -
<c,d> = <F,F>if the evaluation is not continuous anywhere inside the interval. -
<c,d> = <T,F>if the evaluation may or may not be continuous in the interval.
Some functions when evaluated over an interval can evaluate to multiple intervals. Consider 1/(x-1)(x-2) evaluated over the interval [0,5], then the result of the evaluation will be the interval set {[0,1-eps], [1+eps, 2-eps], [2 + eps, 5]}. If the same function is present on both sides of equality / inequality, then the each branching interval should be kept track of, so that intervals belonging to the same branch are compared.
The extended Interval Arithmetic module will be modified to have the intervals evaluated using Numpy functions. This would involve adding an to_ndarray() function to the class and modifying eval to take in an additional argument lib = 'numpy'. Extending to Numpy will involve mimicking the rules for evaluation of functions implemented for mpmath.
####svgfig Backend The svgfig backend will be similar to [3] back end for Matplotlib. The back end will follow the same class structure. As Google App Engine supports Numpy, I will use numpy for evaluations while using it as the plotting backend for SymPy Live. The plot will be saved as a static file and rendered.
####Adaptive Sampling. The present plotting module [3] uses an samples points uniformly and renders a plots. I would like to sample the points adaptively using the idea that more points are required to plot a function if the change in slope is large while few points are required when the slope is not changing. The implementation of adaptive sampling will be based on the implementation given in [2]. This would involve calculating the angle between three points, and depending upon a threshold for the angle, decide whether the curve has to be sampled between those points. This will involve modifying how the points are sampled in the plotting module of [3]. This will be more like a patch for [3].
I have no plans for summer and hence I can dedicate 40 hours a week till July 31st. My next semester starts on August 1st. I have only 2 courses in the next semester and hence I think I will be still able to work 40 hrs a week.
I am mostly a self taught coder. Though I use python regularly, my code is not always pythonic. Through this project, I would like to improve my knowledge of coding styles and practices. This will also be first big project in python, and I would be requiring some help in structuring my code. I think I will have a lot to learn from code reviews.
- https://github.com/sympy/sympy/pull/1102/
- https://github.com/sympy/sympy/pull/1082, merged in https://github.com/sympy/sympy/pull/1099
- https://github.com/sympy/sympy/pull/1086 (Not exactly a patch, helped in removing redundant code).
[1] Reliable Two-Dimensional Graphing Methods for Mathematical Formulae with Two Free Variables, Jeff Tupper, SIGGRAPH 2001
[2] Adaptive polygonal approximation of parametric curves, Luiz Henrique de Figueiredo.