These are chat archives for symengine/symengine

18th
May 2016
Charles Chen
@chenchfort
May 18 2016 08:03
@isuruf benchmark/series seg faults. Is this not caught?
Isuru Fernando
@isuruf
May 18 2016 08:03
Benchmarks are not run in travis
Charles Chen
@chenchfort
May 18 2016 08:05
UnivariateExprPolynomial is able to take UnvariatePolynomial into its constructor. Strange.
Isuru Fernando
@isuruf
May 18 2016 08:06
Because UnivariatePolynomial is also a Basic type and Expression can take it in
Charles Chen
@chenchfort
May 18 2016 08:06
How should this be modified?
Isuru Fernando
@isuruf
May 18 2016 08:06
I think you don't need to modify it
Because UnivariateExprPolynomial is not supposed to be used by the user
Charles Chen
@chenchfort
May 18 2016 08:08
So use UnivariatePolynomial in benchmark?
Isuru Fernando
@isuruf
May 18 2016 08:08
yes
Charles Chen
@chenchfort
May 18 2016 08:09
Should this be a PR?
Isuru Fernando
@isuruf
May 18 2016 08:09
Yes, which benchmark is this?
Charles Chen
@chenchfort
May 18 2016 08:09
series.cpp
Charles Chen
@chenchfort
May 18 2016 08:16
Why is UnivariateExprPolynomial not supposed to be used by the user?
Srajan Garg
@srajangarg
May 18 2016 08:16
It's an internal class, not supposed to be exposed to the user
Charles Chen
@chenchfort
May 18 2016 08:17
But surely they’ll like to have the overloaded operators
UnivariateSeries uses UnivariateExprPolynomial so it’s inevitable that it will be used?
Srajan Garg
@srajangarg
May 18 2016 08:19
I'm a little confused about the structure as well
Isuru Fernando
@isuruf
May 18 2016 08:20
UnivariatePolynomial and UnivariateSeries are exposed to the user
Expression class can be used to wrap both and have operator overloads
Srajan Garg
@srajangarg
May 18 2016 08:21
We aren't overloading UnivariatePolynomial because just overloading the dictionary (wrapper) is faster/lighter?
But wouldn't it be the same operations performed on the dictionary?
Why would it affect performance?
Isuru Fernando
@isuruf
May 18 2016 08:23
I'm not sure I understand what you are asking
Srajan Garg
@srajangarg
May 18 2016 08:24
Basically, why are the operator overloads defined on UnivariateExprPolynomial and not on UnivariatePolynomial directly?
and why do we need UnivariateExprPolynomial as it just contains only the dictionary
Am I making sense?
Isuru Fernando
@isuruf
May 18 2016 08:25
Let me give you an analogy, Integer wraps mpz_class. Integer is immutable and mpz_class is mutable and is used in low level methods
Srajan Garg
@srajangarg
May 18 2016 08:26
Right
Isuru Fernando
@isuruf
May 18 2016 08:26
Integer is a Basic type and memory is managed by RCP, therefore we are using non member functions like add, mul
Srajan Garg
@srajangarg
May 18 2016 08:27
Yes
Isuru Fernando
@isuruf
May 18 2016 08:27
We need UnivariateExprPolynomial because of reasons we talked about, like UnivariateSeries, UnivariateBase, etc
Charles Chen
@chenchfort
May 18 2016 08:28
Various UnivariateSeries methods use UnivariateExprPolynomial, can the user still avoid using UnivariateExprPolynomialdirectly?
Isuru Fernando
@isuruf
May 18 2016 08:29
Yes, UnivariateSeries's static methods are not used by the user. We are still trying to find how to use it in add, mul, pow
See my latest email to the mailing group about polynomials and series
Srajan Garg
@srajangarg
May 18 2016 08:35

UPolyBase will have several implementations. Each implementation has a different container. UnivariateExprPolynomial (this would keep just a map_int_Expr inside), piranha::polynomial, flint::fmpq_polyxx)

Here, you mean a new class which will store map_unit_mpz, instead of UnivariateExprPoly right?

Isuru Fernando
@isuruf
May 18 2016 08:39
You can have both
Srajan Garg
@srajangarg
May 18 2016 08:40
How will a class for symbolic coefficients and others for Integer coefficients interact? Shouldn't there be two different base classes?
Like there is now
I'm assuming 'cross' class operations are permitted
for eg. a function like add(UPolyPiranha a, UPolyFlint b) exists
where both these classes inherit from the base class
If such functions won't be used, then there will be no problem
Isuru Fernando
@isuruf
May 18 2016 08:44
That's easy to handle. You convert one class to another
Charles Chen
@chenchfort
May 18 2016 08:44
Currently is it really possible for Expression to wrap UnivariateSeries and UnivariatePolynomial?
Isuru Fernando
@isuruf
May 18 2016 08:45
Expression can wrap UnivariateSeries, but it'll be buggy. This will be added eventually
Charles Chen
@chenchfort
May 18 2016 08:45
I’m trying that just now. A lot of compile errors.
I suppose that this constructor Expression(T &&o) : m_basic(std::forward<T>(o)) will be used? How would we proceed to make it work?
Charles Chen
@chenchfort
May 18 2016 08:58
@isuruf And back to benchmark of series.cpp, UnivariateExprPolynomial still has to be there right? Also besides just benchmarking multiplication, what else should be there? The one from flint’s benchmark?
Charles Chen
@chenchfort
May 18 2016 10:46
After I call expand, is it guaranteed that it will result in a single Add object?
Isuru Fernando
@isuruf
May 18 2016 10:47
No. x*(x+y+z) - x*y - x*z would result in x**2
Charles Chen
@chenchfort
May 18 2016 10:51

I’m trying to do FFT with symbols. Currently the output is like this

"(0.0 + 2.46519032881566e-32*b - 2.46519032881566e-32*a*b)*x**5 + (0.0 + 1
  .0*a**2 - 5.55111512312578e-17*b**2)*x**4 + (0.0 - 1.23259516440783e-32*b + 2
  .0*a*b)*x**3 + (0.0 + 2.0*a - 1.14967358514655e-17*a*b + 1.0*b**2)*x**2 + (0
  .0 + 2.0*b)*x + (1.0 - 1.14967358514655e-17*a*b + 5.55111512312578e-17*b**2)"
  ==
  "a**2*x**4 + 2*a*b*x**3 + (2*a + b**2)*x**2 + 2*b*x + 1”

If coefficients are only integers and symbols we can go through these and round the dict_ part.
Or any idea?

Isuru Fernando
@isuruf
May 18 2016 10:52
I have no idea how FFT works
Charles Chen
@chenchfort
May 18 2016 10:56
So is it possible for expand() to produce Mul?
Isuru Fernando
@isuruf
May 18 2016 10:56
yes
Charles Chen
@chenchfort
May 18 2016 10:56
Does it only produce Add, Mul, and Pow?
Isuru Fernando
@isuruf
May 18 2016 10:56
It can produce anything
x*(y+z) - x*y - x*z + w == w
Charles Chen
@chenchfort
May 18 2016 10:58
Is x**2 + 1 an Add?
Isuru Fernando
@isuruf
May 18 2016 10:58
yes
Charles Chen
@chenchfort
May 18 2016 10:59
And it will have a Pow in it?
Isuru Fernando
@isuruf
May 18 2016 10:59
yes
What is the branch that you are working on?
Charles Chen
@chenchfort
May 18 2016 11:01
fast_expansion
Isuru Fernando
@isuruf
May 18 2016 11:01
Can you send a link?
Charles Chen
@chenchfort
May 18 2016 11:01
#931
However, 3x + 1 will just be Add?
No Mul in it
Isuru Fernando
@isuruf
May 18 2016 11:03
Yes
Is there a test so that I can run
?
Charles Chen
@chenchfort
May 18 2016 11:08
I haven’t pushed the recent changes yet. Right now I’m in the middle of porting FFT to UnivariatePolynomial
Isuru Fernando
@isuruf
May 18 2016 11:08
In the branch you have, is it possible to get the output you showed?
Charles Chen
@chenchfort
May 18 2016 11:09
Yes, if I push it. And run test_polynomial.
Isuru Fernando
@isuruf
May 18 2016 11:10
Can you do it then?
Charles Chen
@chenchfort
May 18 2016 11:10
Yeah, let me clean some stuff.
Charles Chen
@chenchfort
May 18 2016 11:29
Ok I’ve pushed.
Charles Chen
@chenchfort
May 18 2016 11:45
Is it possible to have Mul in Add after expand()?
Isuru Fernando
@isuruf
May 18 2016 11:45
Yes
Charles Chen
@chenchfort
May 18 2016 11:46
How?
Isuru Fernando
@isuruf
May 18 2016 11:46
(x*y + 1) expanded is (x*y + 1)
Charles Chen
@chenchfort
May 18 2016 11:53
I realized something.
We have pi in constants.h
If I use it, will sin((1/8)*pi) get evaluated to sqrt(2-sqrt(2))/2
Isuru Fernando
@isuruf
May 18 2016 11:54
I don't think so
Charles Chen
@chenchfort
May 18 2016 11:58
Will that be difficult to implement?
Isuru Fernando
@isuruf
May 18 2016 11:59
No, but you are going to end up with lots of complicated expressions that is not easily simplified
Charles Chen
@chenchfort
May 18 2016 12:00
Pow can do negative exponent right?
Isuru Fernando
@isuruf
May 18 2016 12:00
yes
Did you ask @shivamvats, how SymPy has done this?
Charles Chen
@chenchfort
May 18 2016 12:05
@shivamvats How does SymPy do it?
Also for multiplying polynomials with rational coefficients, I believe that flint just has the naive O(m*n) implementation. So I guess there’s no advanced algorithm for that?
Srajan Garg
@srajangarg
May 18 2016 12:36
We can try FFT?
@isuruf Do you feel, that we should rename all the Univariateclasses? Right now their names are very unintuitive
UnivariatePolynomial -> UExprPoly
UnivariateExprPolynomial -> UExprWrapper or UExprDict
UnivariateIntPolynomial - > UIntPoly
and the new wrapper for map_uint_mpz (to be implemented) -> UIntWrapper or UIntDict?
Isuru Fernando
@isuruf
May 18 2016 15:13
Yes, that'll be useful, but let's wait for @chenchfort is done with #931, because when we rename there's going to be lots of merge conflicts
Srajan Garg
@srajangarg
May 18 2016 15:14
Ok
Shivam Vats
@shivamvats
May 18 2016 19:54
@chenchfort You question is about pi, right? It will get evaluated in SymPy.
In [16]: rs_series(sin(a+pi/8),a,4)
Out[16]: -1/6*(sqrt(sqrt(2)/4 + 1/2))*a**3 + (sqrt(sqrt(2)/4 + 1/2))*a - 1/2*a**2*(sqrt(-sqrt(2)/4 + 1/2)) + (sqrt(-sqrt(2)/4 + 1/2))
StoicBronco
@StoicBronco
May 18 2016 20:17
@isuruf
It is my understanding that you wanted MultivariatePolynomial and MultivariateExprPolynomial to have their functionality swapped as to make the structure more mutable? i.e. being able to have += -= and *= work appropiately. I was wondering why there couldn't be functions added to MultivariatePolynomial specifically for this functionality, as opposed to switching the entire structure.
Charles Chen
@chenchfort
May 18 2016 22:32
@shivamvats Can you point to me where the trig implementation is in SymPy?
@isuruf Should we call expand in the operations of UnivariatePolynonial and UnivariateExprPolynomial?
To make sure coeffiicents are simplified.
myluszczak
@myluszczak
May 18 2016 22:45
@isuruf @shivamvats In our current implementation of MultivariatePolynomial, from_dict calls expand on every coefficient in order to simplify it. We do this to check if the coefficients are algebraically equal to zero, so that we can remove terms equal to zero. When working on multivariable series expansion, however, I have found that this imposes a very significant (100x slowdown, mostly in cases involving division) performance penalty. However, removing this simplification can lead to counter-intuitive results (like (x**2 + (a+b)*x + 1) + (x**2 - (a+b) * x + 1) != 2*x**2 + 2*x). As I see it, we have three options: we can continue to expand the coefficients in from_dict, eating the slowdown. Since the slowdown seems to be occurring primarily in cases involving division, there might be something we can do to optimize expand. Secondly, we can stop expanding the coefficients and live with the counter-intuitive behavior. Thirdly, we can change the function __eq__ to ignore terms with zero coefficients --we'ed probably end up calling expand in __eq__ in that case.
After talking with Charles and Iris, it appears that UnivariatePolynomial adopts the second option.
Iris Lui
@irislq
May 18 2016 22:53
I suggest an idea to add on to what Matthew has suggested. In UnivariateExprPolynomial, we can check the Expression terms if they would algebraically equate to 0 (i.e. for subtracting if the terms are equal to each other), and if they are we skip over them so they won't be added to the resulting polynomial
Charles Chen
@chenchfort
May 18 2016 23:10
@isuruf In addition to ^, I submitted PR #945 to fix benchmark/series.cpp.
Charles Chen
@chenchfort
May 18 2016 23:16
@shivamvats nvm I know where it is now. Thanks!
myluszczak
@myluszczak
May 18 2016 23:24
@isuruf @certik @shivamvats Currently there are three MultivariatePolynomial PRs (PR #924, #925, #913), which, as of this writing, have no merge conflicts with master and have passed all integration tests. PR #924 contains MultivariateIntPolynomial, a multivariable polynomial class that can handle integer coefficients. PR #925 contains the contents of PR #924 and the MultivariatePolynomial class, which is a multivariable polynomial class with Expression coefficients. PR #913 contains the contents of PR #925 and the MultivariateExprPolynomial class, which contains overloaded operators. All of these PRs implement the interface changes recommended when we last talked.
myluszczak
@myluszczak
May 18 2016 23:35
@isuruf @certik @shivamvats Currently our polynomial classes are intended to be immutable. James is currently implementing a mutable architecture on a separate branch. He intends to do this by adding additional functions to MultivariatePolynomial, as he has indicated above. He says that he has completed the implementation and is now working on tests of this functionality. This will only affect work in PRs #925 and #913. PR #924 can be merged independently of this work. PRs #925 and #913 are complete without this work; we could either review and merge these immediately and submit the architecture change in a new PR or wait for the architecture change and merge that into the current PRs.
@isuruf @certik @shivamvats In any case, we may want to change PRs #924 and #913 to solve the issue with expand discussed above.