@isuruf benchmark/series seg faults. Is this not caught?

Benchmarks are not run in travis

UnivariateExprPolynomial is able to take UnvariatePolynomial into its constructor. Strange.

Because

`UnivariatePolynomial`

is also a Basic type and `Expression`

can take it in
How should this be modified?

I think you don't need to modify it

Because

`UnivariateExprPolynomial`

is not supposed to be used by the user
So use UnivariatePolynomial in benchmark?

yes

Should this be a PR?

Yes, which benchmark is this?

series.cpp

Why is UnivariateExprPolynomial not supposed to be used by the user?

It's an internal class, not supposed to be exposed to the user

But surely they’ll like to have the overloaded operators

UnivariateSeries uses UnivariateExprPolynomial so it’s inevitable that it will be used?

I'm a little confused about the structure as well

`UnivariatePolynomial`

and `UnivariateSeries`

are exposed to the user
`Expression`

class can be used to wrap both and have operator overloads
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?

I'm not sure I understand what you are asking

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?

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
Right

`Integer`

is a `Basic`

type and memory is managed by `RCP`

, therefore we are using non member functions like `add`

, `mul`

Yes

We need

`UnivariateExprPolynomial`

because of reasons we talked about, like `UnivariateSeries`

, `UnivariateBase`

, etc
Various

`UnivariateSeries`

methods use `UnivariateExprPolynomial`

, can the user still avoid using `UnivariateExprPolynomial`

directly?
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

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?

You can have both

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

That's easy to handle. You convert one class to another

Currently is it really possible for Expression to wrap UnivariateSeries and UnivariatePolynomial?

`Expression`

can wrap `UnivariateSeries`

, but it'll be buggy. This will be added eventually
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?
@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?

After I call expand, is it guaranteed that it will result in a single Add object?

No.

`x*(x+y+z) - x*y - x*z`

would result in `x**2`

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?

I have no idea how FFT works

So is it possible for expand() to produce Mul?

yes

Does it only produce Add, Mul, and Pow?

It can produce anything

`x*(y+z) - x*y - x*z + w == w`

Is x**2 + 1 an Add?

yes

And it will have a Pow in it?

yes

What is the branch that you are working on?

fast_expansion

Can you send a link?

#931

However, 3x + 1 will just be Add?

No Mul in it

Yes

Is there a test so that I can run

?

I haven’t pushed the recent changes yet. Right now I’m in the middle of porting FFT to UnivariatePolynomial

In the branch you have, is it possible to get the output you showed?

Yes, if I push it. And run test_polynomial.

Can you do it then?

Yeah, let me clean some stuff.

Ok I’ve pushed.

Is it possible to have Mul in Add after expand()?

Yes

How?

`(x*y + 1)`

expanded is `(x*y + 1)`

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

I don't think so

Will that be difficult to implement?

No, but you are going to end up with lots of complicated expressions that is not easily simplified

Pow can do negative exponent right?

yes

Did you ask @shivamvats, how SymPy has done this?

@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?

We can try FFT?

@isuruf Do you feel, that we should rename all the

`Univariate`

classes? 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`

?
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

Ok

@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))
```

@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.

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.

@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.

@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.

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
@isuruf In addition to ^, I submitted PR #945 to fix benchmark/series.cpp.

@shivamvats nvm I know where it is now. Thanks!

@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.

@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.