#Implementing Solvers Module(and Sets Module en route) in SymEngine

##Personal Details

Name: Akash Trehan
University: Indian Institute of Technology, Bombay
Email: [email protected]
Github: CodeMaxx
Other Contact Methods: Google Hangouts, Gitter Chat
Blog: codemaxx.github.io (TODO)
Time-zone: UTC+5:30

##Personal background

I am a first year B.Tech. undergraduate at Indian Institute of Technology, Bombay. I am pursuing Computer Science and Engineering as my Major. I love coding. I'm just addicted to it. I have a keen interest in Mathematics and Theoretical Physics. I like reading books on theoretical physics, such as Feynman Lectures.

Other than this I like tinkering with electronic circuits and making small robotic vehicles. I also like dancing, listening to music and performing Card magic tricks. I'll like learning and trying out new things.

#Programming Details

##Platform and Text Editor Used I use both Mac OS X and Ubuntu 14.04 LTS as my work machines. I use Sublime Text 3 as my primary text editor because of its functionality, user-friendly nature and the useful packages which can be installed on it. Sometimes I also use vim.

##Programming Experience I have been using C and C++ since the past one year and python since past 4 months.

Apart from these I also do web programming so I have used Javascript,PHP with SQL for databases.I contribute to mozilla's open source project 'wptview' which is a web app for displaying results of web-platform-tests.

While working with SymEngine I also learn about 'cmake' and 'CMake files' - how to create them and how they function to create 'Makefiles'.

I use git and Github everyday and I am well acquainted with how to use them for version control.

Among all the programming languages I'm most comfortable with C++ and use it in most of my projects. I developed a game of Checkers, with Artificial Intelligence for one player game, using C++ for my class project.

#Contributions to SymEngine

I was introduced to SymEngine in mid-December 2015 and I have been contributing ever since. It has been an enriching experience and I look forward to continue contributing to it. A list of my contributions is as follows:

1.PR #678(Merged) - Wrote a python script to check for the presence of Trailing Whitespace in the code during continuous integration in Travis.

2.PR #715(Merged) - Moved dependencies(Catch and Teuchos) to utilities directory so that all the dependencies are together in a single subfolder.

3.PR #727(Merged) - Added an additional compiling test for Travis with the latest gcc and g++ compiler(version 5.2 for both when I did this) so that new warnings coming up from these can be fixed.

4.PR #736(Unmerged) - Adds two new functions, one for finding quadratic residues and second for checking if a number is a quadratic residue of another .Added tests for both. Also fixed variable names in another function which were causing ambiguity. This led to an issue for checking Integer overflows.

4.PR #758(Merged) - Removed some redundant code left by another Developer's PR.

5.PR #761(Merged) - Fixed a bug in eval_mpfr.cpp and eval_mpc.cpp where Euler's constant was being instead of Euler's Number.Added Tests for the same.

6.PR #767(Merged) - Code for Whitespace Check shifted to the end of Travis file so that other more important errors can be handled first, before the program exits due to trailing whitespaces.

7.PR #792(Merged) - Added complete functionality for functions sech, csch and acsch and their Derivatives,printing and tests.

8.PR #795(Closed) - This meant to prevent the use of 'Arb' when the user disables 'Flint'. It was closed since the discussion proved the corresponding Issue #788 to be Invalid.

9.PR #807(Merged) - Improved and fixed functions of Polygamma class and added tests for the same.

10.PR #815(Unmerged) - Add a cmake switch to prevent Catch from catching exceptions so that stacktraces can be obtained from Teuchos.

11.PR #835(Unmerged) - Improves the abs functions so that it can handle Complex and also abs(x-y) is treated as equal to abs(y-x)

• I also try to review some less complicated Pull Request and follow the discussions on others. I also follow discussion on SymEngine's Gitter Chat. This has helped me learn a lot of new stuff.

#Contributions to SymPy

1.PR #10714(Unmerged) - Added complete functionality for Inverse hyperbolic function acsch.Added Tests.

2.PR #10721(Unmerged) - Fixed typo in documentation of asech function.

3.Issue #10717(Open) - Issue about missing acsch function which I fix in PR #10714.

#The Project

##What excites me

I've been working with SymEngine community from quite some time and want to remain associated with it for long. Making a significant contribution to it by taking up this project would be the best method to achieve this and to develop better understanding with the mentors. Maybe I can be a mentor myself some day.

I have always liked Maths and a projects such as this would help me improve my skills. Solvers would expose me to diverse areas of mathematics and help me learn new things in each.

Also being a programming and open source enthusiast, I've always wanted to take part in Google Summer of Code.

I also want to meet other people working in this area and learn from them. Open Source indeed has a lot of talented people.

##Qualification

In this project I will be working with Sets, Polynomial Manipulation and Solvers of Algebraic Equations and System of Linear Equations.

The related courses I've taken are - Calculus, Linear Algebra, Differential equations. As regard the programming skills I've done courses on - Computer Programming and Utilisation,Introduction to Computer Science, Abstractions and Paradigms for Programming. I have also knowledge about Algorithms and Data Structures. I think I am well suited to work on this project.

Also since I've worked with SymEngine, I've got comfortable with its code. I recently audited symengine's code for UnivariatePolynomials and Matrix class which will be key components around which solvers will be based.

I have also started auditing Sympy's code for Set ,Solveset module and the Polynomial Manipulation Module and would complete that in the Pre-GSoC period.

I also already have a pretty good bonding with the community.

##Previous Implementations

This project has not been tried before in SymEngine, so I will be starting these modules. SymPy on the other hand has a very robust and flexible Sets module and a partially developed Solvers module. These would act as a good reference since these are very well documented.[1][2]

For Infinity class, there is a reference of Pynac's Infinity class.

For polynomial factorisation there are well written wiki pages on Polynomial Factorisation, Berlekamp's algorithm and Cantor-Zassenhaus algorithm and most importantly the Modern Computer Algebra Book.

##Time during and after Summers

I have no other commitments this summer. So I'll be able to give a full 50 hours or more per week.

My summer break starts from 24th April so I can start working full time from that day on. I'll not be taking any vacations.

My classes start around 20th July. That might reduce the time given during weekdays but I'll try to compensate on weekends. I'll not be having any exams during that time so everything would be manageable.

I'll continue to contribute to the project after Summer of Code although I'll not be able to work full time.

##What I want to Achieve

Currently SymEngine lacks any support for Solvers and Sets. My aim through this project is to get a fully functional Sets module and use it for the implementations of the Solvers Module. I basically want to set the ground so as to facilitate the porting of Sovers Module to SymEngine. Also I would improve the Polynomial module by adding Polynomial factorisation and other algorithms to provide support to the Solvers module. Infinity class is also missing in Symengine and is much needed. Solvers are a necessary part of any Computer Algebra System and since the final aim is to use SymEngine as a core for SymPy, we definitely need this functionality.

• For the design of Infinity class there was a confusion between following Sympy's design and Pynac's design. Discussion with Isuru Fernando and Ralf Stephan led to finalising on Pynac's design. This is because Pynac's design can be easily extended to handle any direction while Sympy's design has Infinity, NegativeInfinity and ComplexInfinity as separate classes with Singleton as metaclass and the only way to accommodate more directions is by creating new classes.

• Sympy is currently trying to replace their Solve module with Solveset module which returns solution in the form of sets and also has other useful functionality such as checking if all solution have been found or not. This obviously led to the decision of porting Solveset, rather than Solve, to SymEngine. This requires a Sets module to be implemented before starting with the implementation of Solveset( Though the implementation of Solver for System of Linear Equations can be done alongside the development of Sets since it depends mostly on the Matrix module which is already present in symengine ).

• For the boundaries of Intervals and the members of FiniteSet are to be kept

• As regard the polynomial factoring algorithm to be implemented for Solvers of polynomials, there was a choice among two algorithms - Berlekamp and Cantor-Zassenhaus.

A fundamental difference between the two algorithms is that the Berlekamp algorithm is deterministic. This means that given any polynomial it will provide the unique factorisation eventually, regardless of how many steps it takes. The Cantor-Zassenhaus algorithm on the other hand is probabilistic, in that it can effectively fail to factor a polynomial completely. The tradeoff is that probabilistic factoring algorithms tend to utilise tricks that enable them to perform tasks quicker if they do succeed.

1. Regarding the Infinity class, I've audited Sympy's Infinity. I've also taken a look at how Pynac(backend for symbolic expression in Sage) does it. Its pretty interesting and I would probably be implementing SymEngine's Infinity along its lines.

2. Learning from Sympy, I propose to return Set as a solution in cases we know the answer and an unevaluated Solve object in case solvers fail to get an answer or cannot guarantee that it has found all the solutions.

• Sets can be used to represent all types of solutions.

Since we don't have any support for Sets, these would have to be implemented first. The output of Solve would make heavy use of a lot of functionalities of Sets. The Set capabilities we need to have

• Empty Sets - Represent the solution of equation with No solutions.(x**2 + 1 = 0)
• Finite Sets - Represent a finite set of discrete numbers.These would be required to represent discrete solutions such as those of Polynomials.(x**2 = 1)
• Interval - Represents a real interval as a set. These are required for the representations such as range of solutions, domain of the independent variables.(floor(x) = 0)
• Image Set - Represents the image of a set under a transformation f. These would be used to represent infinitely many solutions.(sin(x) = 0)
• Universal Set - When we talk of complement of a set, it requires some kind of Universe for context.
• Union
• Intersection
• Complement - Represents the set difference of a set with another set.A - B = \{x \in A| x \\notin B\}

I would also implement some special and commonly required sets such as

• Naturals
• Whole Numbers
• Integers

3. Next thing we require are polynomial algorithms for solving Algebraic equations.

• One of the non-trivial algorithms I plan to implement is the Cantor-Zassenhaus algorithm.

The constructor would look something like

Infinity::Infinity(const Integer & _direction)

There will be other overloaded constructors taking input from other datatypes such as int but the behaviour will essentially be the same.

When _direction is positive, it behaves as Positive Infinity; when negative as Negative Infinity and when zero(0) it behave as Infinity with unknown direction.

Various other properties of Infinity will be defined such as:

1. Infinity + Infinity = Infinity
2. Finite + Infinity = Infinity
3. Infinity - Infinity = NaN
4. PositiveFinite * Infinity = Infinity
5. NegativeFinite * Infinity = -Infinity
6. Infinity * Infinity = Infinity
7. Finite / Infinity = Zero
8. Infinity / Infinity = Nan
9. Infinity**Zero = Nan
10. Infinity**Infinity = Infinity

Any more properties required for some specific functions in symengine will also be implemented as required.

Using the concept of inheritance and keeping the Sets class as the parent class, other classes would be implemented as derived classes.

Constructors

• FiniteSet(std::vector<RCP<const Number>>)

This would take a vector of RCP of type Number

• The printing would be done so as these can be used as direct inputs to Sympy.

The user will be allowed to declare different types of sets and perform operations of Union, Intersection and Complement.

Initialisation

RCP<const Number> i1 = integer(1);
RCP<const Number> i2 = integer(2);
RCP<const Number> i3 = integer(3);
RCP<const Number> i4 = integer(4);
RCP<const Number> i5 = integer(5);
RCP<const Number> i6 = integer(6);

std::vector<RCP<const Number>> v1 = {i1,i2,i3,i4};
std::vector<RCP<const Number>> v2 = {i1, i3, i5, i6};

//Finite Sets
RCP<const Set> fs1 = finiteSet(v1);
RCP<const Set> fs2 = finiteSet(v2);

//Intervals
RCP<const Set> in1 = interval(i1, i5); // [1, 5]
RCP<const Set> in2 = interval(i3, i5,true,true); // (3, 5)

//Empty Set
RCP<const Set> es1 = emptySet();

//Universal Set
RCP<const Set> us = universalSet();

Union

RCP<const Set> in3 = union(in1, in2);
RCP<const Set> fs1 = union(fs1, fs2);
RCP<const Set> in4 = union(fs1, in1);

Intersection

RCP<const Set> si4 = intersection(fs1, fs2);
RCP<const Set> sif2 = intersection(in1, in2);
RCP<const Set> sif2 = intersection(fs1, in2);
RCP<const Set> es2 = intersection(in1, es1);

Complement

RCP<const Set> sif2 = intersection(in1, in2);
RCP<const Set> sif2 = intersection(fs1, in2);

• Before the official period of GSoC begins, I would do a rigorous audit of sympy's Sets and Solve, Solveset for algebraic equations especially UnivariatePolynomials, simultaneously helping out in solving bugs found in those modules. I would also go over Sympy's implementation of Polynomial factoring and root finding algorithms. In fact I've already got started with this task.

• Develop a bonding with Sympy community through the above task.

• Submit a wiki on the possible algorithms for various implementation and their details.

• Start with the implementation of Infinity and NaN(Not a Number) class and complete most of it.

• Complete the Infinity and NaN class, send in a PR and get it merged during the first week of this period.

Rest of the three weeks would be spent in implementing the following classes:

• Finite Set
• Empty Set
• Intervals
• Universal Set

Implement:

• Union
• Intersection
• Complement
• Symmetric Difference

I'll be maintaining a blog at codemaxx.github.io to record my progress each week so that the community can keep track of my work and also give their opinion on it.

##References

1. Gitter Chat with Isuru Fernando and Ralf Stephen[1][2][3]