@isuruf Sorry for this late response; I know I've been gone for some time. Based on your response about having

`UnivariateExprPolynomial`

containing the dictionary and `UnivariatePolynomial`

wrapping around `UnivariateExprPolynomial`

, does this mean all the operators like operator+ need to be from `UnivariatePolynomial`

?
@irislq, no, operators should be in

`UnivariateExprPolynomial`

But in place operators like

`+=`

and `-=`

should be written so that there is not extra allocation
@shivamvats @irislq @chenchfort @StoicBronco Iris said we'd be meeting here?

Is everyone here?

I dont know if he's actually online, he's not responsive @chenchfort

He might just have it open; he tends to keep a lot of tabs open

He can join when he does

I have been travelling for the past few days so I couldn't see what optimisations you did.

In univariate

On the Univariate side, we're still trying out FFT. Charles has been working heavily on the FFT multiplication, it's still a work in progress from what I've seen a couple of days. We haven't actually pushed a PR or anything because it's still experimental and we aren't sure if it'll actually make things faster

Also, I havent done much this week because of schoolwork, but I was going to do what Isuru suggested about this, and Im starting to ask about this:

`UnivariateExprPolynomial`

containing the dictionary and`UnivariatePolynomial`

wrapping around`UnivariateExprPolynomial`

, does this mean all the operators like operator+ need to be from`UnivariatePolynomial`

?

Oh! I was expecting more progress on this as I do not have high hopes on fft.

Fft will improve only very large multiplication whereas all our operations are slow I think.

He said that he had gotten about a factor of two or three improvement in speed with an optimized implementation but that inverse FFT was not giving the correct output

@irislq

So should we not work with FFT?

Hey guys, FFT is working. But the tricky part is to deal with different types of Expression.

Well, I'll definitely see what I can do about modifying

`UnivariatePolynomial`

and `UnivariateExprPolynomial`

and see if that will help the performance
Perhaps @chenchfort can finish fft and then help @irislq with mutability.

So so far, the math is working correctly and it halves the time of the naive implementation.

Or types

@irislq I think it should just preform the computation symbolically

That would be pretty slow, though.

First

And figure out the rest later.

It sounds like he's almost done if he's just debugging for correctness

What would happen if the coefficients are symbolic? Wouldn't it still work?

It would not work. So right now when doing FFT it would convert those integers to real_doubles

@isuruf Charles is still trying to fix it to work with all the tests (from what I understand)

Basically all coefficents would need to be converted to real_double at some point to do the computation.

@chenchfort Can this be changed or is it strictly that all coefficients need to be doubles for FFT?

All you need for FFT is addition and multiplication with complex numbers

Only the following two lines need to be changed. https://github.com/symengine/symengine/pull/931/files#diff-1edcb93b88e109f562b95db96b5c5eeeR91

```
Expression thetaT = Expression(pi) / N;
base phiT(cos(thetaT), sin(thetaT))
```

Yes

@isuruf Other than fft and making the objects mutable, do you have anything in mind?

For improving speed

I will push those branches soon.

Btw, you should focus on getting polynomials with

`Expression`

coefficient to be as fast as possible.
Focusing on polynomials with integer coefficients is not really necessary

Shouldn’t it be symbols since it’s called SymEngine haha.

We are able to do that without using Expressions.

The current MultivariateSeries implementation uses Expression coefficients.

Using

`ring`

, you can add a fixed number of variables which makes it faster than going fully symbolic/Ezpression.
Yes

That could be a long term goal(porting ring) but lets focua on Expressions now as Isuru said.

Based on benchmarks done on PR924 the speed is faster when you have polynomials of the same variables. Rewriting the class to only work with specific variables would be faster.

Yes, the benchmarks we have uses rationals, but there needs to be a Expressions. Polynomials like

`x**2 + y**2`

and `x**2 + sin(y)**2`

are the same in my mind. It's just a matter of using generators, but `x**2 + sin(1)**2`

is a totallly different thing.
Also, Expression coefficients allow us to do multivariate Taylor series expansion by using univariable series expansion on each coefficient.

As long as we take it to be a symbolic object.

If you do that series expansion of

`cos(x**2 + sin(1)**2)`

becomes needlessly complicated
Wait

@myluszczak Were you talking in terms of the problem of the "" (empty) `var`

in the Univariate case? And what do you mean by this

Perhaps you could return whatever the coefficient type is when you get a constant polynomial, and overload all of the operations appropriately?

Wait, @isuruf I was talking about this

`base phiT(cos(thetaT), sin(thetaT))`

@srajangarg My impression was that the idea of having the variable "" in the univariate case was to allow the addition of a constant polynomial to any other polynomial. This would be another way of accomplishing the same thing: Whenever you find that you would be returning a constant polynomial, just return that constant and define your operations to work with that

@srajangarg with function overloading.

which will have overloaded functions like

`add_poly`

?
@srajangarg Well, whatever class you're using for coefficients

Hmm, makes sense. Will have to thing about it. But I feel this will kind of increase our work a lot.

@myluszczak, that will lose the information that the coefficient is an actual polynomial and then you cannot return it from a function returning a polynomial instance

And the fact that a constant is a polynomial too, semantically loses value

Yes

So should the way the current polynomial class handles constant change?

We need a solution like the

`set`

way in Multivariate case. How about maintaining a `set`

here too, but limit it's size to only 0 or 1?
It may not be a good idea. Is a similar consideration why SeriesBase inherits from Number?

@irislq It need not right now, but we are thinking of improving it

SeriesBase inheriting from Number is a hack, that will be fixed

*Anything else

/ have we been told we need to change things

Ah that reminds me, Matthew have any of the Multivariate PRs been handled yet?

@srajangarg If you use a set in the Univariable case, would it make sense to have a single polynomial object with different behavior based on the size of the set? I think Shivam has floated merging the classes together.

@srajangarg has been reviewing PR924

About #924, can you explain a little bit about what some of the functions do? See https://github.com/symengine/symengine/pull/924#discussion_r62145355

Wait, that

's in from_dict.

from_dict takes a set_sym and a dictionary and returns a polynomial in cannonical form

I don't have the time to look into literature this week, so I'll need some comments about what you have done. If you could start with it, I'll ask some more questions to get familiart with it

I'll add some comments tonight.

Is from_dict the only major area of confusion, or do you want me to comment more liberally generally.

?

@chenchfort @irislq I dont have anything to add. This week's goals should be clear.

`MultivariateIntPolynomial::from_dict({y, z}, {{{2, 1}, -2_z}, {{0, 2}, 1_z}, {{1, 0}, 3_z}});`

In the above, what if

`set_sym`

orders `{y, z}`

to `{z, y}`

?
Yes, but the order depends on a hash and the hash is dependent on compiler

I will let you know the exact time after figuring out the time difference.

sac*

`MultivariateIntPolynomial::from_dict({y, z}, {{{2, 1}, -2_z}, {{0, 2}, 1_z}, {{1, 0}, 3_z}});`

is `-2*y**2*z + z**2 + 3*y`

right?What is

`MultivariateIntPolynomial::from_dict({z, y}, {{{2, 1}, -2_z}, {{0, 2}, 1_z}, {{1, 0}, 3_z}});`

?
I thought we could pass an order when defining the object--In dict.h I give it RCPSymbolCompare?

i don't live down there O.o

Ok, so how about Sunday like we usually do? You'll be on the same timezone as us

@myluszczak, @StoicBronco, see my comment here, https://gitter.im/symengine/symengine?at=573165101aac35a00e4ac2e2

But I haven't tested that.

the canonical form that from_dict uses normally works

but we haven't put testers for it as far as I know

ill add some testers when i can

the powers would be swapped?

i imagine the powers are matched with the symbol before putting in canonical order

Looking at test_polynomial.cpp in branch mulexprpoly, I see a test for RCP<const MultivariatePolynomial> p2 = MultivariatePolynomial::from_dict(

{n, m}, {{{1, 0}, comp1}, {{2, -1}, comp4}});

{n, m}, {{{1, 0}, comp1}, {{2, -1}, comp4}});

and it seems to have worked out there

First one would give

`-2*y**2*z + z**2 + 3*y`

and I expect the second to give, `-2*z**2*y + y**2 + 3*z`

. Is that what is happening?
I don't think so, no.

matt

he didn't swap the power's places

only the symbols

and i think

`-2* y*z**2 + y**2 + 3*z`

err

@irsuruf I believe that the current implementation will give the same polynomial in both cases.

and a negative in front

how do i do that ?

Use `

instead of quotations marks

~

except don't push shift

@isuruf So I think the current implementation should return the same polynomial in both cases.

@irsuruf If you give me a few minutes I could test it.

MultivariateIntPolynomial::from_dict({z, y}, {{{2, 1}, -2_z}} would map 2 to y and 1 to z?

I think]

and i see

Let me look at how SymPy and piranha does multivariate polynomials

@isurf @StoicBronco Just tested it on CSIF,

`RCP<const MultivariateIntPolynomial> p1 = MultivariateIntPolynomial::from_dict({x,y}, { {{1,2},integer_class(1) } });`

and `RCP<const MultivariateIntPolynomial> p2 = MultivariateIntPolynomial::from_dict({y,x}, { {{1,2}, integer_class(1)} } );`

both print as `x y**2`

and recognize each other as equal on calling `p1->__eq__(*p2)`

We originally went with std::set because it is an ordered container, which could be used to define an order on the variables which would make comparisons between polynomials simpler.

Also when printing, for example, we could iterate through the set and iterate through the vec_uint's containing the exponents and know when exponent corresponded to which variable.

That's fine. I think you should make

`::from_dict`

a private function and add public method that would use std::vectors and construct from them
Just to hold the symbols or to hold the information from the dictionary as well?

When converting to

`set_sym`

the dictionary would have to permuted as well
For things like add_mult_poly and mul_mult_poly I'd like to avoid the extra overhead; but this could probably be accomplished by making them friend functions.

Currently it's not a member function, wouldn't it not have access to a private function?

@isuruf you mean the vectors (the individual keys) of the dictionaries?

And all such vectors will have to be permuted right?

@srajangarg I already have a translate function which can permute the entries of a vector given a vector representing the permutation.

And how will the vector containing the permutation be built?

So far as calculating the vector, since we'll need to create the set anyways we could create the set from the vector and then iterate through the set to find each symbol's position in the set.

There might be a better way, that's just off the top of my head.

So long as the number of variables is small doing linear search shouldn't matter too much.

How about this, create a

`map<symbol, vec_int, symbolcompare>`

for each symbol. So `{y, x}, {{1, 2}, 3}, {{2, 5}, 4}, {{0, 2}, -1}`

will be represented as`x -> [2, 5, 2]`

`y -> [1, 2, 0]`

`coeffs -> [3, 4,-1]`

and then, they will be stored in order in the map

and you can pickup the kth element from each vector (in order) to construct the original dictionary back

which will be what we desire

I think the "picking kth" part can be highly optimized too

So, the new dictionary will be

`{x, y}, {{2,1}, 3}, {{5,2}, 4}, {{2,0}, -1}`

@chenchfort, in what kind of scenario? Ideally we would want to avoid double -> integer conversions

@srajangarg Could you elaborate on what you mean by the "picking kth" optimization?

Once the map is ordered, you just sort of convert the map into a 2D matrix

like above, and then each vector (key in original dict) is just a column in that matrix

@shivamvats sorry again for being late, and i got to go, talk to you next week

so the whole process takes O(m*n) time, where m is the number of vars, and n is the number of terms. This is basically I think the same amount of time that will be taken to permute too. (O(m) permutation time for each of the n vecors) But this ideas seems simpler I guess.

I'll implement it tomorrow, since it's getting late where I am.

Actually this uses extra O(m*n) space. Which is a waste. Your permutation methods seems better. You can construct the permutation using the same idea (use indexes for the variables in the map) and get the permutation vector. And then permute each dict key. Takes same time, and only O(m) space.

@isuruf So pi and those trigs are invovled so I think that’s why coefficents are converted to double.

So I’m wondering if there’s a way for it to convert those coefficients to what type it’s supposed to be.

You can construct the permutation using the same idea (use indexes for the variables in the map)

I mean the `map`

that we constructed additionally. So for {y, z, x} it would be `y -> 0, z -> 1, x -> 2`

. And after iterating over this map you'll get the permutation vector `[2,0,1]`

Yes, that's faster than just iterating through the set and vector.

Yes, basically use the same idea, I just suggested a better way to construct the permutation vector I think . Silly me

I think I'm going to log off soon, to get some sleep. What time zone are you in?

@srajangarg Thanks, I'll keep that in mind when contacting you. I'm on PST. Bye!

@shivamvats Quick update on Multivariable Series: Multivariable series now passes all tests when is_cannonical is commented out, but It only fails on one when is_cannonical is operative and I expect that the error should be easy to fix. I do not plan to submit a PR with this until the polynomial stuff dies down, but if you want to look at it its on branch mulseriesfour on my remote. I am logging off after this message.

@isuruf Why isn't

`Basic`

operator `==`

overloaded? Is it because of performance reasons?
the explanation in that document about the interaction between const correctness, performance and developer-friendliness does not make much sense in modern C++

I agree on that part, in the sense that overloading operators for classes you have no full control on could be problematic

my comment was more in the general sentiment that (at least to me) seems implied by the document

that is that you have to trade off nice notation for performance

we had some discussions about this in the past (e.g., pointer semantics vs value semantics), and I understand that this is the path chosen by symengine and it's fine... I just wanted to point out that generally speaking in modern C++ you can have nice syntax and performance at the same time (and it's actually one of the main drivers of the evolution of the language over the last few years)

(and that it is not particularly hard)

Generally speaking it's not that easy. (Expression templates. :D) But I agree, it shouldn't be that hard.

@isuruf Since

`UnivariatePolynomial`

will wrap around `UnivariateExprPolynomial`

, does this mean that `UnivariateSeries`

would now need to take in `UnivariatePolynomial`

instead (or rather an RCP of it)?