September 01, 2017

About Me

My name is Abdullah Javed Nesar, I am an undergraduate student at Indian Institute of Technology, Kharagpur.

About the Project

Rule based integrator nicknamed Rubi is an entirely new module in SymPy, Integrals. It is an implementation of more than 10,000 rules to cover a wide variety of indefinite integration. Currently SymPy uses algorithms for indefinite integration which are too slow and presents results which are not simplified. Rubi utilizes a set of well defined rules which makes it smart to present the results in a more symmetric and simplified manner.

The Plan

The plan earlier was to implement a completely new pattern matcher with multiple functionalities which was as efficient as Mathematica’s pattern matcher. As the pattern matcher would be the back bone of Rubi. But later we came across matchpy and we planned to implement it in our module. But because it is implemented in Python3.6 Rubi isn’t capable to support Python version less then 3.6.

Work Done

  • Utility functions: We have managed to cover majority of the utility functions. Our job was to re-write functions from mathematica to Python.
  • Added rules into SymPy using Python parser.
  • Added tests cases. But unfortunately we could not include all the tests due to performance issue in Python. Tests was taking too long so we decided to include only a few of them.

Future Work

  • Although we have implemented all the rules, but we could not work much on the performance and so it takes too long for Python to compute results. Because of this issue we could not add all the test cases.
  • Working on left out Utility functions. Few of the utility functions were a bit tricky like Dist,  FixRhsIntRule etc are yet to be implemented.
  • Extending rules set for a smarter computation and better results.
  • Replacing the SymPy’s pattern matcher with matchpy in utility functions.

Conclusion

I would like to thank my mentor Ondřej Čertík for this project idea and helping me understand the project, I am also thankful to Francesco Bonazzi and Aaron Meurer for helping me from the very beginning at every stage whenever I needed help.

References


August 31, 2017

This is a detailed report on how things went during Summers 2k17.

Goal of the project :

My proposal for GSoC 2017 was to Implement Solvers for SymEngine.

Community Bonding Period -

I added FLINT wrappers for factorisation during this period. Most of the time during this period was on getting more thorough with the code base, going through the FLINT documentation and understanding some design concepts like Visitor pattern which are required in later stages of the program.

Progress during First Phase -

Major focus during this phase was on Improving the Sets module. I added set_intersection and implemented Complement, ImageSet and ConditionSet. After adding this, the robustness required in Sets module for implementing Solvers was achieved as expected. I really thank my mentors for being patient, when I made several silly errors during this phase. I was able to push a raw version of Polynomial solvers just before First Evaluations.

Progress during Second Phase -

I worked on Polynomial solvers for the initial half of this phase. SymEngine’s own implementation for lower degree polynomials and integrating FLINT wrappers developed during the community bonding phase for solving polynomials of higher order was successfully implemented.
Next target for me was to focus on Trigonometric solvers. The PR, I initially sent for trigonometric solvers was a lot messed up with a lot of independent stuff. I had to break it into smaller parts and then my focus shifted to getting all these parts merged before returning to actual solvers. I implemented visitors for expand_as_exp and as_real_imag, which came as surprising visitors to my To-Do list(Not part of my proposal). I learnt a lot of new and interesting c++ and design stuff in this phase.

Progress during Third Phase -

I continued on getting all the parts for the Trigonometric Solvers ready. I landed in various Travis errors which ate quite a lot of time. Thanks to Isuru who figured this part out, I was able to get them cleared up. I also implemented function to compute eigen_values of a Matrix(Under Applications of Solvers) and system of equations and visitor for xreplace. Unfortunately, these PRs are not yet merged. This phase was really harsh for me, primarily due to hectic schedule of my college. High Fever for around 6 days made life even more miserable.

Immediate Goal:

  • Getting all the pending PRs merged.

Things that were planned but didn’t get done during GSoC (Future Work):

  • Implementing fu algorithm. I have already made some progress here. I would like to continue working on this after #1305 gets in.
  • Completing the PR #1058.

Conclusion:

I am grateful to work with my mentors Srajan, Sumith, Nishant, Shivam and Amit for this project. They helped me throughout summers. I am really thankful to the SymPy community for giving me this opportunity to work in this project.

References:

Weekly Blog : https://ranjithkumar007.github.io/
Progress report : https://github.com/symengine/symengine/wiki/GSoC-2017-Solvers-Progress-report
All PRs sent by me : https://github.com/symengine/symengine/pulls/ranjithkumar007
Discussions : https://gitter.im/ranjith-gsoc/Lobby

August 29, 2017

This page summarizes the work which I’ve done this summer. About me My name is Szymon Mieszczak and I’m master student at Adam Mickiewicz University in Poznań, Poland. The goals The aim of my work was to introduce different kind of orthogonal curvilinear coordinate systems to vector package in SymPy. Previously coordinate system could be only rotated or/and translated with respect to other coordinate systems. My work can be split into tasks.

As I’m writing this post, the deadline for code submission has finally arrived. It has been a wonderful journey, and the experience has certainly left me as a much better programmer than I originally thought I was. From my first bug fix, which despite being a minor issue, took up so much of my time, I wasn’t even sure that I’d be associated with the SymPy and SymEngine team for so long.

Google Summer of Code ‘17 has officially ended. It had its own ups and downs, though both being rewarding to say the least. Currently all my work is pushed up to the respective repositories, and should be ready to merge soon. Thanks to Isuru, for allowing me to work on this even after the official period ends.

Report

SymEngine.py

I pushed in #182 implementing Expr class and fixing the inheritance of various other classes. Some minor changes still might be required in this repository in the time to come, since it might require some more tweaks to finally get everything running in SymPy.

SymPy

Here is a list of all my PRs currently pending in SymPy. I pushed a lot of them in the last few hours to spare some time before the deadline. These will consequently be worked upon and merged.

I had a great summer, much more exhilarating than I had expected it to be. A more detailed work report can be found here. A final thanks to the SymPy community, Google, and my mentors Isuru Fernando and Sumith Kulal, for giving me the opportunity to be a part of this. I hope to stay around for a while.

पुनर्दर्शनाय

August 28, 2017

Introduction

My project was to enhance the code-generation facilities of SymPy. You can read my proposal for the motivation behind this work. The overall goals were the following:

  • Allow to render code targeting a specific precision (e.g. binary32 vs. binary64 floating point numbers). Prior to this project the printers would sometimes generate code containing a mixture of single, double and extended precision, and there were no way to change this short of subclassing the printers and overriding the methods.
  • Allow to render blocks of code and not only expressions. There was an initial effort to support this in the submodule sympy.codegen.
  • Improve the Lambdify functionality in SymEngine's python wrapper. Before this project it did not handle outputs of mixed shape, and it also had considerable overhead.

Summary of the final work product

A whole new repository with code and notebooks for code-generation was created during the first part of GSoC:

Jason Moore, Kenneth Lyons, Aaron Meurer and I (my commits) created this for the tutorial in code generation with SymPy at the SciPy 2017 conference.

The majority of the work are contained in these pull-requests:

  • symengine.py, #112 (merged): Heterogeneous output in Lambdify.
  • symengine.py, #171 (merged): Bug fix for heterogeneous output in Lambdify.
  • sympy, #12693 (merged): Extending the sympy.codegen.ast module with new classes (for generating ASTs).
  • sympy, #12808 & #13046 (merged): PythonCodePrinter, MpmathPrinter, SymPyPrinter NumPyPrinter, SciPyPrinter.
  • sympy, #13194 (open): Add .codegen.rewriting module.
  • sympy, #13200 (merged): Add .codegen.approximations module.
  • sympy, #13100 (open): More AST nodes. Building on #12693, this is the biggest PR. In addition to improving the AST nodes it introduces .codegen.algorithms as well as an internal testing module .utilities._compilation which allows to compile and import/run strings of C/C++/Fortran code.

In addition there were smaller pull-requests made & merged:

  • sympy_benchmarks: #37, #38, #39, #40: Benchmarks for lambidfy and common sub-expression elimination.
  • sympy: #12686 (Support for __abs__ in SymPy matrices), #12692 (subclass support for SymPy's deprecation decorator), #12762 (Fix floating point error under windows), #12805 Revert change to cse (performance regression), #12764 environment variable use, #12833 string formatting, #12944 allow relative path in autowrap, #13063 fix test timing script (and updated timings), #12833 (some of the commits) Allow custom class in autowrap & codegen, #12843 (one of the commits) allow changing compile arguments in CythonCodeWrapper.

Detailed review of the work

The first weeks of the summer was mostly spent on the code generation material presented at the SciPy conference tutorial, in parallel with that work was done to handle different choices of data types in the printers. And new AST nodes were introduced to represent type.

Code for the tutorial

During the writing of this code improvements were made to the existing code-generation facilities and SymPy (and experience with their shortcomings were gained). One of the challenges in this work was that the attendees at the conference would be using all major platforms (Linux/macOS/Windows) and different Python versions, we needed to ensure that generating code, compiling, linking and importing worked all combinations.

Lambdify in SymEngine's python wrapper

Writing the code for the tutorial provided great test cases for the code-generation capabilities of SymPy. The motivation of doing code generation is usually that of speed (but sometimes it may be motivated by wanting to work with some library written in another language). An alternative to generating high level code which then gets compiled, is to go toward assembly (or some intermediate representation). SymEnigne had support for doing this via LLVM's JIT compiler. The Python bindings however needed an overhaul (something I had included in the time-line in my proposal), and now I wanted to use Lambdify (the SymEngine version of sympy.lambdify), and together with the help of Isuru Fernando we got it to work (and benchmarks for pydy show that it is even faster than using the cython backend).

AST nodes

I had made AST nodes in my prototype for my proposal, right at the start of the project I ported those to SymPy. It took some rewriting and discussion with Aaron (both during our weekly meetings and at the conference) to get it to a point where we were confident enough to merge it into SymPy's codebase.

One of the major challanges when designing the new classes for sympy.codegen.ast was dealing with optional arguments in our subclasses of symyp.core.basic.Basic. The solutions which worked best was to have a subclass sympy.codegen.Node which stored such optinoal information as instances in a SymPy Tuple as its last argument (accessible as .attrs`). This allowed the code printers for Python, C and Fortran to support the same ``Variable class for instance, where the C printer would also look for attributes "value_const", "volatile" etc. and the Fortran printer would look for e.g. "intent".

Language specific nodes have been added under their own submodules in sympy.codegen (e.g. sympy.codegen.fnodes for Fortran and sympy.codegen.cnodes for C). The most common statements are now implmeneted, but the nodes are by far not exhaustive. There are now also helper functions for generating e.g. modules in sympy.codegen.pyutils & sympy.codegen.futils (for Python and Fortran respectively).

Code printers

Dealing with floating point types is tricky since one want to be pragmatic in order for the types to be helpful (IEEE 754 conformance is assumed), but general enough that people targeting hardware with non-standard conformance can still generate useful code using SymPy. For example, one can now choose the targeted precision:

>>> from sympy import ccode, symbols, Rational
>>> x, tau = symbols("x, tau")
>>> expr = (2*tau)**Rational(7, 2)
>>> from sympy.codegen.ast import real, float80
>>> ccode(expr, type_aliases={real: float80})
'8*M_SQRT2l*powl(tau, 7.0L/2.0L)'

Here we have assumed that the targeted architechture has x87 FPU (long double is a 10 byte extended precision floating point data type). But it is fully possible to generate code for some other targeted precision, e.g. GCC's software implemented float128:

>>> from sympy.printing.ccode import C99CodePrinter
>>> from sympy.codegen.ast import FloatType
>>> f128 = FloatType('_Float128', 128, nmant=112, nexp=15)
>>> p128 = C99CodePrinter(dict(
...     type_aliases={real: f128},
...     type_literal_suffixes={f128: 'Q'},
...     type_func_suffixes={f128: 'f128'},
...     type_math_macro_suffixes={
...         real: 'f128',
...         f128: 'f128'
...     },
...     type_macros={
...         f128: ('__STDC_WANT_IEC_60559_TYPES_EXT__',)
...     },
...     math_macros={}
... ))
>>> p128.doprint(tau**Rational(7, 2))
'powf128(tau, 7.0Q/2.0Q)'

For generating Python code there was previosuly one function (sympy.printing.python) which generated code dependent on SymPy. During the project a proper code printer for Python was introduced (an example of its output is shown later). The much used function lambdify was also changed to use this new printer. Introducing such a big change without breaking backward compatibility was certainly a challenge, but the benefit is that the user may now subclass the printers to override their default behaviour and use their custom printer in lambdify.

Rewriting

One usual challenge when working with symbolic expressions is that there are many ways to write the same expresisons. For code-generation purposes we want to write it in a manner which maximizes performance and minimizes significance loss (or let the user make that choice when the two are at odds). Since SymPy already has a great tools for traversing the expression tree and applying quite advanced pattern matching based replacements using Wild it was reasonably straightforward to implement rewriting rules for transforming e.g. 2**x to exp2(x) etc. Using the same structure, rules for rewriting expressions to drop small elements in sums (based on a user-predefined bounds).

Algorithms

One of the great benefitst from being able to represent abstract syntax trees as (largetly) language agnostic SymPy obejcts is that we can create functions for building these trees. Simpler numerical algorithms (which are ubiquitous in scientific codes) can be collected under sympy.codegen.algorithms. As a first case Newton's algortihm was implemented:

>>> from sympy import cos
>>> from sympy.codegen.algorithms import newtons_method_function
>>> ast = newtons_method_function(cos(x) - x**3, x)
>>> print(ccode(ast))
double newton(double x){
   double d_x = INFINITY;
   while (fabs(d_x) > 9.9999999999999998e-13) {
      d_x = (pow(x, 3) - cos(x))/(-3*pow(x, 2) - sin(x));
      x += d_x;
   }
   return x;
}

once we have the AST we can print it using the python code printer as well:

>>> from sympy.printing import pycode
>>> print(pycode(ast))
def newton(x):
    d_x = float('inf')
    while abs(d_x) > 1.0e-12:
        d_x = (x**3 - math.cos(x))/(-3*x**2 - math.sin(x))
        x += d_x
    return x

or the Fortran code printer:

>>> from sympy.printing import fcode
>>> print(fcode(ast, source_format='free', standard=2003))
real*8 function newton(x)
real*8 :: x
real*8 :: d_x = (huge(0d0) + 1)
do while (abs(d_x) > 1.0d-12)
   d_x = (x**3 - cos(x))/(-3*x**2 - sin(x))
   x = x + d_x
end do
newton = x
end function

Newton's method is quite simple, but what makes SymPy suitable for this is that it needs the ratio between the function and its derivative.

Conclusion

I think that I managed to address all parts of my proposal. That being said, there is still a lot of potential to expand the sympy.codegen module. But now there are purposefully made base classes for creating AST node classes (sympy.codegen.ast.Token & sympy.codegen.ast.Node), the language agnostic ones are general enough that an algorithm represented as a single AST can be printed as Python/C/Fortran. At some level code will still be needed to be written manually (presumably as templates), but the amount of template rendering logic can be significantly reduced. Having algorithm AST factories such as the one for Newton's method in sympy.codegen.ast.algorithms is also exciting since those algorithms can be unit-tested as part of SymPy. Ideas for furthor work on code-generation with SymPy have been added to the list of potential ideas for next years GSoC.

Post-GSoC

I plan to continue to contribute to the SymPy project, and start using the new resources in my own research. Working with the new classes should also allow us to refine them if needed (preferably before the next release is tagged in order to avoid having to introduce deprecation cycles). SymPy is an amazing project with a great community. I'm really grateful to Google for funding me (and others) to do a full summers work on this project.

This was the last week of work on GSoC. I have been hard at work improving documentation and examples for the code.

Adding much needed documentaiton

I've spent the weekend adding examples and writing up documentation for my big PR #13100 which is not yet merged. I am quite excited how this PR turned out and I am happy with the design of the underlying AST nodes.

Rewriting

A new submodule .codegen.rewriting was added (in #13194), this allows a user to rewrite expressions using special math functions. The provided rules are those to rewrite to C99's special math functions (expm1, log1p etc.). I think it will be a useful addition (I have myself had the need for exactly this in my own research). The design is quite simple thanks to the excellt replace function in SymPy. There are still some corner cases (I have an "xfailed" test checked in for example).

Final evaluations are due in a day and GSoC 2017 will soon come to an end.
Here is the link I submitted for the final report -> GSoC 2017 Report. The last three weeks I have been wrapping up the 3D use case, writing its test cases and documentation.

The only deliverables which remain :

  1. Computing all monomials given a max_degree for the 3D case.
  2. Handling implicit intersecting polygons.

I would have loved to at least have the first one merged before SoC deadline but unfortunately I have two tests and two lab sessions in the span of three days hence will have to implement after the 30th.

Let us discuss how close the above issues are to being resolved :

  1. For the 2D case it was simple to just generate a list of all monomials up to a given max degree. I wanted to do a similar thing for the 3D case, but was having problems with having to find out the correct indices for \delta (monom)/\delta x\delta (monom)/\delta y and \delta (monom)/\delta z in the flat_list. But then I remembered a certain PR in SymPy which two SymPy members and me had worked on(PR#12490). It seems that creating a flat list out a given matrix is a compiler optimization, therefore it would be a lot of work with quite less benefit if a flat_list is attempted to be made(in the code itself) for the 3D case as well.
    Therefore, a list of lists can be used for the 3D case which makes indexing for the partial derivatives much easier. After this all that needs to be done is to simply take up of the faces of the polygon and compute the left_integral of 1 over it and then that value would be re-used. This is partly implemented and should be a part of the module soon but unfortunately after the 30th.
  2. As mentioned in the Report, the intersection algorithm needs to be replaced and the case for more than two intersecting sides needs to be dealt with. The first problem isn’t that hard to be dealt with but I haven’t thought about the second one yet.

GSoC has been a great learning experience and I look forward to porting this module to symengine after the loose ends in SymPy are tied up. Grateful to both my mentors Ondrej and Prof.Sukumar for their guidance.


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

August 25, 2017

GSoC is coming to an end, and it’s time for the final report (which is not to say that I won’t make a couple more posts after this). In this post I will summarise the work I’ve done so far with links to PRs in approximately the order they were submitted.

First of all, looking at my proposal, I’d say that I have done all that was planned plus some minor additional things here and there (discovering and fixing bugs, modifying existing functions and occasionally adding new ones beyond what was planned). However, there is certainly room for improvement, and I will mention where the work could continue as I go through the PRs. So here it is.

  1. The subgroup method PR. Here I added subgroup() methods to the PermutationGroup and FpGroup classes. There were some discussions as I wondered if FreeGroup class could be implemented differently, but it was mostly straightforward. Perhaps, it would be useful to add a keyword argument or something like that to FpGroup’s subgroup() to allow the user to get hold of the injective homomorphism from the subgroup to the parent group.

  2. Improvements to simplifying subgroup presentations. I didn’t look at _elimination_technique_2 because it is not used anywhere in the code at the moment but it could probably be improved as well, especially now that some new FreeGroupElement methods are available: one of them is the general substitution of words that I implemented in this PR and, as I recall, I modified a few other FreeGroupElement methods there, as I discovered that some of them were buggy or not general enough. In a later PR (#9), I united the main elimination technique (which removes redundant generators) and the simplification of relators into one function simplify_presentation that can be applied to any group, not just as part of reidemeister_presentation (used for finding presentations of subgroups).

  3. The Smith Normal form PR. This is the only time I did work somewhere other than the combinatorics module during the project. I implemented the Smith Normal form for principal ideal domains because it could be used to test if a group is infinite (not a definitive test, as if the test is negative, we can’t conclude the group isn’t infinite). It’s a bit awkward to use at the moment because the user has to add manually a certain attribute to their matrix and it won’t be resolved until some further work is done on matrices. I wrote a bit more about it in the relevant post.

  4. Changing the order method. The previous PR allowed returning S.Infinity as the order of the group in some cases where in the past the order() method wouldn’t terminate. This PR extended it even further by calculating the order in stages. First, it attempts to find a finite index subgroup and, if it succeeds, it finds the presentation of this subgroup and applies order() to it. In some cases, other methods can determine that this subgroup is infinite in which case, of course, the whole group is infinite. If it’s finite, then the order of the group is the index times the order of the subgroup. It is still possible that this never terminates if a finite index subgroup is not found, but it’s an improvement. It can be faster than direct coset enumeration on the trivial subgroup (that was used before) but occasionally it seems too slow for even smallish groups. Usually, the slowest part is finding the subgroup’s presentation but sometimes it’s the search for this subgroup that takes up the time. I feel that more work should be done here to make it more efficient.

  5. The homomorphism PR. This was a substantial PR: not only did it introduce two new classes (GroupHomomorphism and FpSubgroup), it also involved quite a lot of work in the PermutationGroup class in order to implement the method that expresses a given permutation in terms of the group’s strong generators. At this stage only homomorphisms from FpGroup to PermutationGroup were fully implemented. The kernel computation can’t handle infinite domains - maybe, this could be addressed in the future.

  6. The Rewriting System PR. This was probably the hardest thing in the project and it probably took the longest to get merged after its review started (or at least it felt the longest). Even after it did, some problems kept coming up. It seems stable at the moment but it could certainly do with more work. One thing that comes to mind is the reduction method: it is possible to do it more efficiently with an automaton which is built and modified as more reduction rules are added to the system. Also, perhaps, the completion algorithm could be made more efficient in some way.

  7. Fixing a bug in reidemester_presentation. Discovered by accident, there was a small bug in reidemeister_presentation that led to order() returning wrong answers in some specific cases.

  8. FpSubgroup’s __contains__ method. After the homomorphism PR was merged, it was discovered that occasionally the tests involving kernels would time out. This was because FpSubgroup’s __contains__ method would go into an infinite loop on encountering elements of the conjugate form a**-1*w*a. It took some time to work out a way of dealing with it.

  9. Finite presentation of permutation groups. This is something I keep working on. The general algorithm is implemented and merged, however, the efficiency could potentially be improved by using a different method based on the group’s strong generating set. I have tried one implementation but it’s not clear when exactly it is more efficient. Currently, I am trying to implement a different, hopefully more consistently efficient, algorithm.

  10. Fixing a bug in minimal_block. A small bug in minimal_block was discovered during the implementation of sylow subgroups.

  11. Adding the other homomorphism cases. This PR enabled homomorphisms with FpGroup as codomain (became possible after merging the rewriting PR) and PermutationGroup as domain (provided the keyword argument check was set to False).

  12. Sylow subgroups PR. This one also took a while. The main function is fairly long and it required implementation of two types of action homomorphisms and a method for finding all minimal block systems of a group. At the moment another related PR (#16) is being reviewed: it treats symmetric and alternating groups separately as the generators of their Sylow subgroups can be written down.

  13. PermutationGroup methods for FpGroup. This is something that gave me the idea for the project in the first place: many methods for permutation groups are already available while finitely presented groups have limited functionality. However, it’s possible to use an isomorphism between a finite FpGroup and a relevant permutation group to perform computations in the latter and then go back to the former. This is precisely what this PR does for many permutation group methods. It is still being reviewed.

  14. Storing coset tables in _finite_index_subgroup. Until the presentation PR, it wasn’t possible to get hold of an incomplete coset table for which coset enumeration returned with an error (for example if the maximum number of entries was exceeded). After it was merged, I made use of this new feature in the search for a finite index subgroup (used by FpGroup’s order() method). This somewhat decreased the required time as coset tables didn’t have to be recomputed.

  15. Checking that a homomorphism from PermutationGroup is well defined. After the presentation PR was merged, it became possible to complete the homomorphism class by enabling the check for whether given generator images define a homomorphism when the domain is a permutation group. Not merged yet.

  16. Sylow subgroups for Sym(n) and Alt(n). A separate method for computing Sylow subgroups of alternating and symmetric groups, to be used as part of the main sylow_subgroup method. This hugely improves the performance in the case of alternating and symmetric groups. Still being reviewed.

A couple other PRs had to do with renaming attributes (this one and this one) or moving code around (for example, moving all of the coset table and coset enumeration functions to the file coset_table.py in this PR). These didn’t include any actual work so I didn’t include them in the main list.

Hopefully, this report will be of use to whoever else might be interested in developing the group theory module. I plan to continue working on it myself for some time, though probably less productively as the new academic year starts soon.

Overall, this was a fun summer and I enjoyed working on this project. I’d like to thank Google for sponsoring it, SymPy for giving me the opportunity to participate and my mentor Kalevi (jksuom) for giving me guidance and useful suggestions on my code and generally being very helpful. :)

August 23, 2017

During week 11 I extended differential operator to handle mixed coordinate system. Mixed means that scalar or vector which we’re using as argument has elements coming from several different coordinate systems. Not necessarily connected. These work were split into three PR’s, one for every differential operator, gradient#13118 , divergence#13128 and curl#13154. To implement this, we need to only take care about product rule for scalar and vector, but they are well defined.

August 22, 2017

Greetings!

This is the combined post for weeks 11 and 12. As mentioned earlier, Isuru had been unavailable for the last week, during which my focus was entirely fixed on getting the countless assertion failures in SymPy fixed while using SymEngine as a core.

I was also able to get all the pending work merged in, namely the Singleton pattern and a host of other miscellaneous additions.

After that, we had to update the conda binaries for both SymEngine and SymEngine.py for through #3 and #2 respectively. Currently, we’re good to go for porting over the changes made over the summers for different directories in SymPy.

This is officially the last week of GSoC 2017. I’ll push all my work as separate PRs on SymPy, and try to get them merged before the deadline on 29th August.

Mirupafshim

The final evaluation period has started, and I’ll be writing a post with the list of all submitted PRs and some summarising comments later this week (perhaps, tomorrow). Overall, I have done all that was planned though there is room for improvement as is the case with the finite presentation of permutation groups algorithm.

I have tried out computing a presentation on basic stabilizers, i.e. starting with the presentation of the smallest basic stabilizer and building up from it. This should probably be available in any case because it gives a strong presentation which could be desirable (it has more generators but on the other hand, fewer relators; theoretically, if known, these relators could be used to check if a homomorphism is well-defined a bit quicker). However, I was looking to see if this would be faster than the general version. What I found was that in some cases it’s considerably faster and in others much slower, with no clear pattern. For example, it doesn’t perfectly correlate with the size of the group or the number of strong generators. The slowest part is filling in the coset tables for intermediate presentations so I looked if the difference correlates with the index of the subgroup on which a presentation is built, or the difference between the generators of the subgroup and the original group, or their multiple (i.e. the size of the unfilled part of the table) and none of it properly accounts for the difference. There would seem to be a number of factors at play. I’m thinking of writing a simple function that generates a random group with a fixed degree and use it to collect data for the various parameters of many different groups. That might give me more to go on than the examples I make up myself. Not sure how successful this would be though. At the moment, I’m not certain I’d be able to figure it out by the end of this week. I’ll probably carry on the work until after the end of GSoC.

I sent a couple of small PRs last week. One for checking homomorphisms with permutation group domains (using the general presentation method for now) and the other is with the more efficient method of computing Sylow subgroups of alternating and symmetric groups that I mentioned in the previous post. These two and the PR implementing permutation group methods for finitely presented groups are still being reviewed.

On a different note, lately I’ve been thinking of extending the FreeGroupElement class to handle group words with symbolic powers, e.g. a**n where n is an instance of Symbol. I don’t see any reason why it shouldn’t be available in general (though we’d have to be careful to raise errors where appropriate when someone tries to use this in methods; or to modify some methods to handle them if possible) and I was thinking of using something like this when implementing the FpSubgroup class so it can probably be put to use in some situations. One would also need to have a subs method for substituting desirable powers. This, along with the earlier idea of grouping things like a*b*a*b into (a*b)**2, could be another thing I could work on after GSoC.

August 21, 2017

Working on new AST nodes

#13100 is shaping up to be the largest PR of my GSoC project. The design of the new AST nodes especially (Token) is really helpful. But there is still a design issue: some nodes would naturally take different arguments depending on what language is being targeted. So I came to the conclusion that I needed some way of representing attributes. The solution I came up with would be to have a slightly more capable Node class (subclassing Token) which would in turn be subclassed from for nodes that need attributes.

I also enhanced the printing of both of these classes and introduced a String class, which in contrast to Symbol does not accept assumptions in its constructor, and does not have implied printing rules of sub- & superscript etc.

Adding .codegen.algorithms

A new submodule .codegen.algorithms was added, containing a AST generating function for Newton's method. This makes a nice design target for both the printers and AST nodes: being able to express the same AST in differnt languages is definitely an indication that we have a versatile printing system.

Compiling code on the fly

Introducing the .codegen.algorithms module also made the need to test generated code during CI runs clear. Jason Moore has previously mentioned that he thinks one of my python packages (pycompilation) would fit nicely into SymPy. I've been a bit relucatant to port it over since I have felt that it has not seen enough testing (and only under Linux). But now there was a need and we could start by making it an internal package only used by our own tests. That way it will get to mature without having to worry about deprecation cycles. And once more platforms are added to SymPy's CI configuration it would also see testing on other platforms (using AppVeyor for SymPy has been discussed for a long while now).

August 16, 2017

The presentation PR got merged fairly quickly last week. Now I could try using the new functionality of resuming coset enumeration with incomplete coset tables in the _finite_index_subgroup function. I expect it should speed it up since at the moment the coset tables inside the function have to be recomputed every time the maximum number of allowed entries is increased. I could also implement a faster version of the presentation algortihm that makes use of strong generators.

Sylow subgroups required a bit more attention. One thing that we were discussing on the Group Theory channel the other day was that symmetric and alternating groups should be treated separately as the generators for their Sylow subgroups can be written down. It took some thinking to work out the details and justify the algorithm. In fact, the alternating group case still doesn’t have a formal proof; but it seems clear that it should work and, indeed, it does as I discovered yesterday on implementing the function. It was a bit fiddly to lay out the code so that it works properly and isn’t too complicated so it took a long time. Now all that remains is to tidy it up and add comments. I briefly described the algorithm in the docstring and hopefully it will make the code clear to whoever might need to work with it in the future. I think this can be added in a separate PR once the current one is merged, though if I have to make any more corrections to the current one, I might push this as well.

The title of the post is to do with the new PR I sent this week in which I added some of the PermutationGroup methods to the FpGroup class so that they can work with finite instances of FpGroup. I didn’t actually need the presentation PR for it, homomorphisms were enough. At the moment, when a permutation group method returns a group, the equivalent fp group method returns its generators. An alternative to it would be to return an instance of FpSubgroup on the generators from where its FpGroup presentation can be found via to_fp_group method. Or, now that the presentation PR is merged, another possibility would be to run presentation on the permutation group returned by the permutation method and return the result together with a homomorphism from it to the original group - though that would probably be too time-consuming so shouldn’t be the default.

For the rest of this week, I’m going to keep working on the Sylow PR and the permutation group methods one if its review starts this week. I’ll also try to speed up the _finite_index_subgroup method and look into the strong generator algorithm for FpGroup presentations.

August 15, 2017

Travis errors were finally resolved, thanks to Isuru for digging deep into these errors. The problem was with the coverage info generated with Piranha. So, as per Isuru’s suggestions, I went on to move piranha on to a different test where CODECOV was disabled.

PRs ready for a review -

I will continue working on improving fu so that once #1305 gets in, I can send a PR of that as well.

End of GSoC-2017 :
This is officially the final week of GSoC 2017. It has been a great journey where I learnt a lot of new stuff. My mentors helped me throughout, Special Thanks to them. There are still some pending works wrt to the proposal as listed below.

Remaining work :

  • Getting the above 3 PRs merged.
  • completing fu and the PR #1058 on interop of polynomials.

GoodBye !!

This post contains progress in week-10 and week-11.

Most of the focus was on trying to get the earlier PRs merged. In improving #1305, Isuru suggested to implement xreplace. I completed this in #1320. I got it merged recently.

Other than this, I worked on implementing a function for computing eigen values of a given matrix. It is implemented in #1319. #1317PR on system of equations is done and it needs a review.

Travis is bothering from quite some time with some unusual errors. I will try to fix them.

Thats all !

August 14, 2017

Checking in the new AST node types

#12693 got merged 🎉. It took a few rewrites essentially but I fell that the design of the new nodes will allow us to scale with reasonable maintance cost when adding new language specific nodes. The base class for new AST nodes (Token) to sublcass from allows one to implement nodes in an expressive manner by setting __slots__. The constructor of Token then sets the .args of Basic based on __slots__ this has the benefit that you need not write setters and getters using @property decorators (which quickly becomes tiresome when you have many classes).

Checking in the refactored PythonPrinter and changes to lambdify

Finally the challenging work of refactoring lambdify got merged into SymPy's master branch: #13046. We eventually decided to drop the contents of the old translations dictionaries but leave them be (in an empty state) in case users were modifying those in their code. Hopefully this approach doesn't break any code out there. Given how popular lambdify is among SymPy's users, it is a bit worrying that the test suite is not that extensive. I do remember a google engineer mentioning that the follow the "Beyonce principle": "I you liked it you should have put a test on it". Funny at is may be I hope I don't need to defend these changes with that arguement.

August 13, 2017

Hi all, sorry for the delay. We have added test suit 1.2 successfully, This week we will complete implementing all tests for expressions involving products of powers of linears. I have completed parsing test suits for quadratic but implementation is yet to do.  There are about 5-6 Utility functions which are left and are difficult to implement using SymPy’s pattern matcher but, I’ll try to implement those as soon as possible. There were few failing test cases for PowerVariableDegree I’ve fixed those.


August 10, 2017

This week I continued work on PR#13082. The last implementation left for the 3D case is the hyperplane representation. For example, the user can express the list of facets of the polytope by a list of points for each facet or a list of hyperplane parameters(a tuple for each facet).

p1 = [(0, 1, 0), (1, 0, 0), (0, 0, 0)]
p2 = [([-1, 0, 0], 0), ([1, 1, 0], 1), ([0, -1, 0], 0)]

The code should be able to figure out what the points are and then pass on that list of points representation to the rest of the other functions. I should be done with this in a day or two. To finish up the work for GSoC I’ll get the PR on intersecting polygons sorted out. After that, remaining documentation will have to be written and requisite clean-up to be done.


During week 10 with my mentor, we finished creation of new CoordSys3D constructor. We can set now transformation while coordinate system is created. We’ve moved functionality from _connect_to_standard_cartesian to constructor so we support the same type of transformation as previously. Now I demonstrate shorty how coordinate system different that Caertsian can be created in SymPy: a = CoordSys3D('a', transformation='spherical', variable_names=["r", "theta", "phi"]) a.lame_coefficients() a.transformation_to_parent() b = CoordSys3D('b', lambda r, theta, phi: (r*sin(theta)*cos(phi), r*sin(theta)*sin(phi), r*cos(theta)), variable_names=["

Work Done

  • Completed test suit for Algebraic Linear products.

Todo

  • So far, we have implemented large utility functions using some of inbuilt SymPy’s functions(example: trigsimp). These functions are very large to be implemented by hand. I have an idea to implement these functions using MatchPy’s ManyToOneReplacer(similar to what we have done with main Rubi Integrate function).
  • Test Algebraic Quadratic products rules.

August 08, 2017

I sent the PR with the other homomorphism cases a week ago, so about a day after my last post. The work required for the main part of the PR wasn’t really complicated but it took a while to get merged (earlier today) because some more problems showed up in the rewriting system part.

It started off with Kalevi noticing that in the case of a free abelian group, the list of rewriting rules after initiation seemed incomplete - it so happened that the test didn’t pick up on it because it didn’t need the missing rules. In itself, that wouldn’t be much of a problem because the missing rules could be added during the run of make_confluent but is_confluent was already True - that was definitely wrong. So for one thing, _check_confluence wasn’t working properly and also I thought that the type of rules that wasn’t added during rule initiation, could be added as another case - if it could be done in place, why wait till it’s discovered by the double loop in make_confluent. I made a few little changes throughout the code to fix things but ultimately, it was the inadequacy of add_rule that was causing problems.

When a pair of words is given to add_rule, it first multiplies them by the inverse of the first element of the longer word until the length difference is 0, 1 or 2 (greater length differences are redundant when the smaller length differences are in the rules dictionary). Then it does the same on the other (right) side which leads to a different set of rules. We could obtain even more rules right here, without waiting for make_confluent, if we allow switching sides, i.e. not just continuously multiplying on the right or on the left, but perform some left multiplications after several on the right, etc. This makes make_confluent a little more efficient as more rules are discovered at one time but trying all possible combinations of sides would probably take too much time without actually being productive. At the moment, when the length difference becomes sufficiently small, instead of adding the rule directly, add_rule calls itself recursively which allows for some side switching. Perhaps in the future, it would seem fit to try all combinations. A couple of days ago I added a rules cache to prevent repeating the work that has already been done by the function so maybe it won’t cause too much of a slow-down in practice.

After this, one rule was still missing. I reread the code several times and it took a while to work out that the problem was what seems quite obvious now. When a pair of words w1, w2 of the same length is given to add_rule, the only rule that was added was w1: w2 for w1 > w2. But another possibility right there could be w2**-1: w1**-1 provided w2**-1 > w1**-1. Normally, this inverse rule doesn’t need to be added because if len(w1) > len(w2), then w1**-1 > w2**-1 and w**-1: w2**-1 is implied by how word reduction is set up. Adding this last case solved the issue.

There were some other little improvements. For example, make_confluent has been made to returns a boolean at all times, not just when checking if the system is confluent. This could be used to see if it is successful. I also spotted an error in the kernel computation method that hadn’t come up before only by sheer luck.

Now that all the basic homomorphism functionality is available, I can have a go at extending the FpGroup class with PermutationGroup methods. I might be able to get it to work without the finite presentation of permutation groups PR (it hasn’t been reviewed yet) but I’m not entirely sure yet.

Another thing on my hands is sylow subgroups. I actually thought I got them to work several days ago but then one of the test groups (SymmetricGroup(10)) revealed a bug in the _strong_gens_slp attribute. It wasn’t caused by the sylow method and only comes up after computing a stabilizer or a normalizer - something I only realised yesterday; this bug really confused me for a while. I did fix it now but a different problem came up and what worked before no longer does. I don’t see why the bug fix would lead to it but evidently it did… So still trying to sort it out.

Update: Have just worked out that sylow thing. Turned out minimal blocks weren’t being computed properly (my fault: I wrote a separate function that should have outputed all minimal block systems but failed on minimality). So now all that remains is to do some more testing and tidy up the code, and I can send a PR with it in a day or so (if no other bugs turn up, that is).

August 07, 2017

Refactoring lambdify

In my work to refactor lambdify I had come up with a solution where I would dynamically subclass the CodePrinters in lambdify to add translations from the old translation dictionaries. I was not happy with the solution and I don't think Aaron was either, we decided to keep the old import mechanism of lambdify which populated the namespace (instead of trying to generate code for the used imports which I had been trying).

So the work on refactoring lambdify has continued in #13046. And with this <https://github.com/sympy/sympy/commit/265314fa63f5a662a7a187913d51d55a852b503c> commit I hope we are close to getting the new version of lambdify out the door.

New FloatType representation

With some underlying assumptions about floating point representation (two's complement etc.) I have now a new representation of FloatType. I'm much happier with this representation and I think with it #12693 is much closer to getting merged.

Greetings! The GSoC final submissions are about three weeks away and I’m trying my best to get everything sorted out before the deadline. However, we are faced with an issue. Isuru won’t be available for the major part of the penultimate week. As such, I’ll have to reach out to Sumith for reviews, who’s been pretty busy lately. Hence my goal for the next week would be to get everything reviewed and merged as soon as possible. Here is a gist of the work done in the previous week.

Report

SymEngine.py

I implemented some attributes seeking inspiration from SymPy’s classes in #180, which is reviewed and merged. I also took some time fixing the assertion failures in SymPy’s modules, which would be pushed in soon. More on this next week.

That’s all I have.

Totsiens

August 06, 2017

Work Done

  • I have parsed all the rule in SymPy syntax and removed Rubi’s dependency on machpy-sympy converters and MatchPy’s Operations. I have also updated the parser to accommodate for this change.
  • Completed the test suit for 1.2. Tests are failing since Travis is still using older version of MatchPy which does not support new functionalities.

Todo

Tests for all algebraic rules are already added.

  • I have already added test for test suit 1.3. I am investigating them locally. I am trying my best to pass all the algebraic test suit by this week.
  • AppellF1 is not implemented in SymPy. I couldn’t find time to implement is last week. I will implement basic version of AppellF1.

August 03, 2017

We are almost done with the implementation of utility functions. My next task would be to parse all test suits and minimize the test cases as there are numerous tests (of similar type) which is taking too long to run in Python. Along with it I’ll be completing some incomplete utility functions and fixing bugs. We need to port all the rules and test it as early as possible to fix all possible bugs. Although a major bulk of our work is completed adding rules and test should not take much time.


August 02, 2017

This week I returned to college and quite some time was spent in setting up the room, registering for courses, etc. Also, I have 27 hours a week of classes from now on which is okay considering that some of my batch-mates have 31 – 32 hours/week.

The good thing is that the major part of my work is complete. This week I worked on the 3D case. Here is the PR : #13082 . A minor limitation(minor from the perspective of fixing it) is that only constant expressions are supported. Another limitation is that the input has to be a list of the polygons constituting the faces of the 3D polytope. This should actually be a list of points in correct order and the algorithm should figure out the polygon from the input. Examples of such input are in Chin et. al(2015) .
I’ll finish it up by Saturday and then proceed to completing PR #12931 . That might extend to the first few days of next week as well.


Reconstruction of constructor in CoordSys3D is like never ending story, but fortunately we are almost at the end of the work. We decide to distinguish two cases. When rotation matrix or location is set and when transformation is set. In the first case we are creating transformation equations from rotation matrix and translation vector. In the second, user is responsible for defining transformation equations but it is also possible to use some pre-defined curvilinear coordinate system.

August 01, 2017

Hi all, we’re in the final month of GSoC with only about 4 weeks remaining on the development time. Last week was a bit rough because my college semester started off with a heavy schedule on the very first day, and a number of boarding issues, due to which a number of my days were spent in shifting my stuff from one room to another. Add to that the summer heat of this country, and it becomes a total nightmare. Here’s what I could do.

Report

SymEngine

I pushed in #1316, resolving some of the scope issues we were facing in SymEngine.py. I’m expecting a light implementation schedule here in SymEngine form now on, as we have most of the stuff we need for a sizeable amount of SymPy’s directories to be ported over SymEngine.

SymPy

Pushed in #13051, fixing a minor piece of code that was previously preventing us from using SymEngine’s igcd in SymPy’s LieAlgebras module. I had also taken some time updating the work on other directories.

SymEngine.py

I worked on implementing some miscellaneous missing functionalities in #179, which should soon be ready to get merged.

Since we are slowly reaching towards the end of the project, I’ll have to request Isuru for a release in SymEngine and SymEngine.py so that our latest work becomes available for SymPy.

Pozdrav

Hey everyone, this post contains progress in week-9. We are in the last phase of GSoC project. My progress is a bit lagging from the proposed timeline primarily due to commencement of classes.

As mentioned in my last blog, I was able to get the PR on fixes for ImageSet merged in and I baked all remaining pieces within #1305.

In this, I implemented a IsALinearArgTrig as follows

class IsALinearArgTrigVisitor
    : public BaseVisitor<IsALinearArgTrigVisitor, StopVisitor>
{}

It checks if the argument of Trigonometric and Hyperbolic parts is linear in symbol or not. If input is not linear in symbol, then we can’t solve that equation using the present TrigSolver.

Next is invertComplex.

class InvertComplexVisitor : public BaseVisitor<InvertComplexVisitor>
{}

This is useful for finding inverse. Ex: for finding the x that satisfies the equation exp(I*x) = 3. Some tests are failing on MSVC15 compiler. I will try to figure out and fix that ASAP.

Meanwhile, I implemented basic solvers for system of equations in this PR.

That’s all for now. See you next time.


Older blog entries


Planet SymPy is made from the blogs of SymPy's contributors. The opinions it contains are those of the contributor. This site is powered by Rawdog and Rawdog RSS. Feed readers can read Planet SymPy with RSS, FOAF or OPML.