Pre GSoC and Community Bonding21 May 2016
The Kronecker Substitution
I started off my work by reading through the existing
mul_poly function. It uses the Kronecker Substitution technique to multiply two polynomials. An insight can be gained by looking at the slides here. Think of it this way,
“If you evaluate a polynomial at a large enough power of 10, I bet you can tell all it’s coefficients just by looking at the result!”
The mentioned slides call this the KS1 algorithm. Another algorithm it proposes is the KS2 algorithm, which evaluates the polynomial at two points (in contrast to just one) to interpolate the polynomial. A more mathematical explanation on the two techniques can be found here. I implemented the algorithm, and it wasn’t too difficult, as it was a a slight modification to the already existing multiplication technique. Later, I added a benchmark test for comparing the two techniques, KS1 & KS2. The benchmark (roughly) calculates the ratio of the time required for multiplying two polynomials using the two algorithms. Both the polynomial length (from 1 to 10,000) and the bit length of the coefficients (5, 10, 15, 20 bits) were varied. The graphs of the benchmarking are as follows.
Linear & Log scale : During this time, I was asked by Isuru to switch work towards the polynomial interface with FLINT & Piranha (and shift the polynomial manipulations to the end of summer). So, the PR hasn’t been merged in yet, and no conclusions and observations have been made between the two algorithms as of yet. Will be done later during the summer. Here’s the PR #930
I also started work on Dictionary wrappers for SymEngine. One was already made, for the
UnivariatePolynomial class aka the class for univariate polynomials with symbolic coefficients. It is a map from
int -> Expression. We needed another wrapper for the
uint -> integer_class map, so that the
UnivariateIntPolynomial class can be structured the same way as the former. Now that we need almost the same functionality, why not temlatize the wrapper? (suggested by Isuru) That’s what I did, and the PR #946 is almost merged in. More on wrappers next time!
Most of my work during this period revolved around reading the existing polynomial class, and refactor it and removed any redundancies. Some of the miscellaneous work that was done :
Some refactoring was done in the
dict.cppfile. There were some redundancy in the functions which was removed. Templatized methods for checking equality and comparing vectors (and sets) were made. Other specific
comparemethods became derived methods of these base classes. #933
mul_polymethod was constructing a vector of coefficients for the resulting multiplied polynomial (thus, implicitly storing it in a dense representation for a while). However, it was returned as a sparse represented polynomial, using a dictionary. This was changed, so that the dictionary is directly created, and the intermediate vector isn’t requireds. Also, some changes in variable names for clarity, as well as removing the redundant function
A redundant function
createwas removed. All it was doing was calling
from_vecwithin the same class. #941
See you next week, Goodbye!