UC Davis Series Expansion project

Team Members: Charles Chen, Iris Lui, Matthew Luszczak, James Stojic
Inputs received from Shivam Vats, Ondřej Čertík and Isuru Fernando

This is the current progress on the series expansion module, based on Ralf's ideas on expression series expansion. We are currently working to have a SymEngine implementation of UPSeriesPiranha with no additional dependencies (to modify series_generic.h to fit into series.h model). To do this, we decided to split into two teams to work on a univariate series implementation (Charles and Iris) and for a multivariate series implementation (Matthew and James). Because this is a senior design project, we also heavily document our plans, meetings and decisions here.

We also have performance benchmarks for both univariate and multivariate operations. See the corresponding pages.

As part of our course, we also have a wiki page for documenting the functionalities of these classes, look at [Functionalities of Univariable & Multivariable Polynomials and Series](Functionalities of Univariable & Multivariable Polynomials and Series)

As of May 2016, the names of the univariable polynomial classes has been modified in the PR here

List of pull requests:

• Univariate Series has been merged (thanks to everyone who contributed!): PR #868
• MultivariateIntPolynomial: PR #891
  • This has been moved in favor of PR #913
• Fix for UnivariatePolynomial::\__eq\__: PR #847
• PR to change UnivariatePolynomial to UnivariateIntPolynomial has been merge: PR #851
• Implementation of UnivariatePolynomial and UnivariateExprPolynomial has been merged: PR #857
• Initial Multivariate PR: PR #819
  • Closed
• Multivariate Polynomials: PR #913
  • Also see PR #924 and PR #925 (PR #925 merged)
  • Later moved to PR #947. See PR #950.
  • Final PR with all functionalities of Multivariate Polynomials (has been merged, finally!): PR #950
• Fast Series Expansion (attempt at faster polynomial multiplication with algorithms such as Fast Fourier Transform): PR #931
  • Closed
• Structure change of UnivariateExprPolynomial and UnivariatePolynomial (has been merged): PR #940
• Multivariate Polynomial Mutable Architecture change: PR #967
  • The changes here was moved to PR #968
• Karatsuba polynomial multiplication for univariate polynomials: PR #958
  • Will be closed
• Multivariate Series: PR #968

Univariate Series

• From the following, we were deciding which would be best:
  
  • 1. Implement UnivariateSeries strictly exactly like UPSeriesPiranha without using the piranha library.
       
    • So far, we have already copied the functions from UPSeriesPiranha into `UnivariateSeries`` to implement. If this decision is made then we would have to look line-by-line in UPSeriesPiranha's function to see how it does in order to conform to it.
      
  • 2. Implement with UPSeriesPiranha and Flint in mind without using piranha and flint libraries.
       
    • So far, we have not taken into account of Flint. There are a lot of functions in Flint are also in UPSeriesPiranha. But for those that aren't, should we also take care of them?
      
  • 3. Don't need to care about UPSeriesPiranha or Flint. Implement UnivariateSeries to make it work as long as no additional dependencies used.
       
    • So far our UnivariateSeries implements the functions in UPSeriesPiranha. Essentially what would happen here is that we simply ignore how UPSeriesPiranha implemented those functions, as long as we implement it correctly. We noticed that some functions that Ralf already wrote for UnivariateSeries are also in UPSeriesPiranha, so we can just use those.
      
• Eventually we decided option 3, since that would fulfill the requirements to implement a series class without dependencies from Piranha and Flint.
  Remarks
  • To be able to implement option 3, again from Isuru's advice, we needed to have Coeff be Expression and Poly to be a Polynomial class that would take in Expression coefficients.

###Univariate Polynomial

• The original UnivariatePolynomial class did not support coefficients besides integer coefficients, which means that terms like ax + bx + cx could not be done.
  
• We initially decided to create UnivariateExprPolynomial class that has overloaded operators +/-/* (not operator/, which we decided against since it’s not necessary).
  Design, Problems, and Solutions
  
  • Still does not handle Expression class coefficients because we use an RCP of UnivariatePolynomial, but based on Isuru’s suggestion we may need to create a new class that can use std::map<short, Expression> as our new dict_.
    
  • This has been solved by implementing the new class as UnivariatePolynomial and renaming the old UnivariatePolynomial to UnivariateIntPolynomial (since it only takes in integer coefficients). UnivariatePolynomial now has a dict_ of map_uint_Expr (defined in dict.h).
    
  • We have now changed map_uint_Expr to map_int_Expr to take in signed degreed polynomials (see PR commit).
    
• UnivariatePolynomial's functions need to be refactored to use Expression instead of integers. Many of them required a simple replacement from map_uint_mpz to map_uint_Expr, and so on. However, some need to be modified to use Expression's Basic value.
  Design, Problems, and Solutions
  
  • from_dict() needed refactoring from just handling integer coefficients to Expression coefficients. We decided to separate how it handled integers and symbolic coefficients. For integers, it would handle the dictionary like in UnivariateIntPolynomial (this was put in its own if-statement). For symbols, we used to mul method to get the result.
    
  • Other problems was with with eval_bit which we deleted, and how to implement it now that the coefficients can be integers or symbols. These are resolved in commit 5b6897b1.
    
• Other minor changes are also in the comments of PR #810
  
• Some unfinished issues: UnivariateExprPolynomial::get_basic implementation, UnivariateSeries::mul does not do precision multiplication, UnivariateSeries::integrate has not been implemented.
  
  • UnivariateExprPolynomial::get_basic has been implemented in commit 9aeb2a7a216
    
  • UnivariateSeries::integrate has been implemented in commit fb36281f178
    
• Implementation of diff was difficult at first. We originally had DiffImplementation::diff. Thanks to Isuru we managed to correct this (see commit 4f196b9d9f)
  

Move to a Pull Request

• Due to our merged PR for the new UnivariatePolynomial and UnivariateExprPolynomial classes (which introduced a new stream of bugs that could not be easily resolved in our univariateseries branch), we decided to close our old UnivariateSeries PR (#810) and create a new PR (#868).

###Univariate Series

• We changed the series_generic constructors to use UnivariateExprPolynomial and map_uint_Expr. We also had to create helper functions convert_map, convert_poly, and convert_vector to reuse the original implementation in SeriesBase.
  
• We started creating and implementing functions used in series.h to series_generic. Some such as convert and as_dict required simple changes, which others needed more complicated refactoring like diff.
  Remarks
  • Copied all trigonometric functions from series_piranha because it also uses Expression
    
  • UnivariateSeries::pow has pow_poly from UnivariateExprPolynomial for polynomial multiplication
    
  • Needed to add add_uni_series, neg_uni_series, sub_uni_series, and mul_uni_series (we took these out previously)
    
• Issue: Constructor of UnivariateSeries is throwing a bad allocation error, which is unusual. However, it may be due to the function convert_poly which needs to be changed anyways.
  • This is solved. We also eliminated convert_map and convert_vector; convert_poly has been renamed trunc_poly although this may be deleted soon.
    
• More Design, Problems, and Solutions
  • Eliminated redundant constructors for UnivariateSeries. In the scenario where a UnivariateSeries needs to be created from a dictionary or a vector, calls from from_dict() and from_vec() will construct the series. It will also eliminate 0 coefficient terms, which are not canonical.
  • Deleted functions add_uni_series, mul_uni_series, neg_uni_series, sub_uni_series and operator==. These operations can be done with Basic's add, mul, because UnivariateSeries is derived from Basic.
  • Moved tests from UPSeriesPiranha for series expansion into test_series_generic then adjust them accordingly.
    
• Thanks to Akash Trehan, who addressed some bugs and issues with UnivariatePolynomial, including adding support for negative exponentials in polynomials and fixing some is_canonical issues
• Finally, a big thanks to Ondřej and Isuru, UnivariateSeries is finally merged!

###Faster, Optimized Univariate Series All benchmark times are on this page

• Create tests for UnivariateExprPolynomial and UnivariateSeries to have more code coverage.
• Add performance benchmarks to compare before/after series expansion. We will upload them either here or on a separate wiki page once this is started.

Multivariate Series

The overall plan for multivariate series expansion is to first create a multivariable polynomial object, and then create a SeriesBase type object that can handle multivariable series expansion, and then finally to create a multivariable series object. As of 22 March 2016, we have completed a multivariable polynomial object that can handle integer coefficients, and expect to quickly have the multivariable polynomial end of the project completed.

###Multivariable Polynomials

The MultivariableIntPolynomial object is a sparse representation of a multivariable polynomial, and contains three data members: a std::set of symbols holding the variables of the polynomial, an std::unordered_map from symbols to unsigned integers storing the maximum degree of each variable, and an std::unordered_map containing the terms of the polynomial. The terms of the polynomial are stored as pairs consisting of an integer_class with keys that are vectors of unsigned ints. The vectors of unsigned ints represent the exponents of the various variables and the integer_class represents the coeficinet, so the term 4*x y**2 z**3 could be represented by the pair {{1,2,3},4} and the polynomial 4*x y**2 z**3 + 8*x**5 y**6 z**7 would be represented by the dictionary {{{1,2,3},4}, {{5,6,7},8}}. Since we are using a sparse representation of the polynomial, only those terms with non-zero coefficients are added to the dictionary. The order of the exponents in the tuple is determined by the order of the variable in the std::set (std::set is, surprisingly, an ordered container), which is determined by Symbol::compare.

####reconcile and translate functions

Consider the polynomials 4*w x**2 y**3 + 8*w**5 x**6 y**7 and 4*x y**2 z**3 + 8*x**5 y**6 z**7. These polynomials both have the same dictionary--{{{1,2,3},4}, {{5,6,7},8}}—but obviously they are not the same polynomial. The same positions in the vectors containing the exponents represent the exponents of different variables in the different dictionaries. If we wanted some way to add or multiply these two polynomials together, we will need some way of accounting for this difference.

We need a way to translate vectors of exponents associated with a polynomial in w,x,y and vectors associated with a polynomial in x,y,z into vectors appropriate for a polynomial in w,x,y,z. For clarity, we will consider the translation from the polynomial in x,y,z only; the other case is similar. We need to indicate that the first, second, and third entries of the vectors in the x,y,z polynomial must be mapped to the second, third, and fourth entries respectively of the vectors in the w,x,y,z polynomial, we can store this information in a translator vector {2,3,4}. The translate function takes the vectors from the x,y,z polynomials and the translator vector and returns the equivalent exponent vector for the w,x,y,z polynomial. uint_vec_translate_and_add performs both translation and component-wise addition of two vec_uints. The translator vectors are generated by the reconcile function, which also generates the set of symbols of the resulting polynomial.