These are chat archives for symengine/symengine

30th
Apr 2016
Isuru Fernando
@isuruf
Apr 30 2016 06:51
@srajangarg, can you review #924 and #925?
Srajan Garg
@srajangarg
Apr 30 2016 07:40
@isuruf Yes, looking at them now
Srajan Garg
@srajangarg
Apr 30 2016 13:31
@isuruf I've been pondering over the chosen implementation in the `MultivariateIntPolynomial` class. It currently uses an unordered map from `vector -> coefficient (int)`. Even Piranha does the same. However, doesn't it seem like a better choice to use ordered maps? This may help in fast implementation of evaluation (using Horner's modification for Multivariate Polynomials), which is also used by the modified Kronecker substitution (for multiplication). The ordering of the monomials maybe of the form, just like the univariate case. At the first level the ordering is decided by the power of a particular variable (say `x`) in all monomials. Ties are then resolved by looking at the second variable and so on.
So, the ordering of tuples like [x, y, z], for eg. [1, 2, 1], [1, 1, 1], [3, 2, 1], [3, 2, 2] will be
[1, 1, 1] -> [1, 2, 1] -> [3, 2, 1] -> [3, 2, 2] for the ordering x<y<z
This method can also take in a vector (which decides the ordering of the variables to be used) (eg. it was [0, 1, 2] for the previous example
The horner method for multivariate polynomials will work like this:
"Chooses a variable and apply the Hornerâ€™s evaluation scheme in that variable.
Thereby we will be treating the other variables as constants. Afterwards another
variable is chosen and the same process is applied again. This is repeated until all
variables are processed."
This won't be possible using an unordered map
Srajan Garg
@srajangarg
Apr 30 2016 13:37
Plus I think the kronecker method which will need evaluation (at symbolic points) won't be fast enough otherwise
Shivam Vats
@shivamvats
Apr 30 2016 15:38
@chenchfort The speed advantage of FFT doesn't really kick in for multiplication of small to medium order polynomials.
I suspect the issue in more related to our design choices, something @isuruf said. I guess it would be insightful to have a look at how Piranha does it.
myluszczak
@myluszczak
Apr 30 2016 19:15
@srajangarg I think I understand what you want and how it'd be done. For now, I'll make the changes you requested in PR 924 and try to implement what you've suggested here in a separate branch on my own remote