@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
@isuruf What do you mean?

@shivamvats

@shivamvats @irislq @chenchfort @StoicBronco Iris said we'd be meeting here?

Hi guys

Which one is wrong?

Ignore that

Hi shivam.

Hi!

Hi

Is everyone here?

Charles is on Slack, James is MIA

Could Charles join us here?

I left a message in slack, Charles hasn't responded yet.

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

Let us begin then.

He can join when he does

Sure

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.

I talked with Charles on Saturday

Im sorry I havent pulling my own weight recently :/

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

Yes, an optimised fft is tricky to implement.

@irislq

Oh, I see

So should we not work with FFT?

Do not fret. We still have time.

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

No point leaing it mid way now.

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

`UnivariatePolynomial`

and `UnivariateExprPolynomial`

and see if that will help the performance
Glad to hear!

Oh hi Charles :D

I have it as #931

Perhaps @chenchfort can finish fft and then help @irislq with mutability.

Sounds good. I'll do my best on my end

Nice to hear :)

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

One option is to have it for certain special cases.

Or types

What would the FFT do in the case of symbolic coefficients?

@myluszczak I only have 9 tabs...

Haha

@irislq I think it should just preform the computation symbolically

That would be pretty slow, though.

I think we should do fft for int and float.

First

And figure out the rest later.

Sounds good for now, to me

How much time will it take @chenchfort ?

For?

Fft for int and reals

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

So assuming all Expression coefficients are int?

I thought this was implemented in #931 ?

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?

We’ll need to figure it out.

It's cetainly not a mathematical requirement

Yet preserving that O(nlogn)

Alright, I can help with that if needed

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

Is that line 91 and the other?

```
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’ve tried porting flint’s implementation

I will push those branches soon.

Excellent!

No, I don't have any suggestions other than that

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

Yes.

Alright

Series expansion mostly uses rationals, right?

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

In Sympy

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.
Do we have anything like that in SymEngine? I don't think we do

But that of course is not here in Symengine.

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.

One could consider

`sin(1)`

to be a generator too.
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
For cos and sin, use SymEngine’s right?

yes

I can't see why. Is one is expanding wrt a variable

Wait

Are you talking abt multivariate expansion?

Yes

Oh! I was thinking of the univariate case.

hi shivam sorry im late :x:

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

Hi @StoicBronco

hello

@chenchfort, yes

`sin`

and `cos`

should be SymEngine ones
Ok, thanks!

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

You mean to say, a different class for constants?

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 we want to talk about?

*Anything else

matt, have you bugged anyone about the PRs yet

/ 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

In is_cannonical, or more generally?

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

All right.

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}`

?
When shall we meet again.

@shivamvats I dont have anything else either

@isuruf std::set is an ordered container.

Right, is next week going to be back to our normal schedule?

saturdays aren't looking good for me :/

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

Most probably. I will reach there on 13th.

You have plans James?

sunday is the only real free day I have nowadays

What about this friday

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

my fridays are spent in sasc

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}});`

?
Oh right, Shivam are you going to be in the US this weekend?

Thursday?

thursday im in san fran

Yes

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

But you can still get on a laptop

with what internet?

i don't live down there O.o

@myluszczak, ah okay.

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

@isuruf I assumed that It'd be the same.

But I haven't tested that.

likewise

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

I was expecting the second one to have

`y`

and `z`

swapped
err, one moment

the powers would be swapped?

@shivamvats

I don't think we tested that on purpose.

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

@irislq We could do that.

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?
Alright great : )

But we haven't tested that deliberately.

I don't think so, no.

it should be yes..?

matt

he didn't swap the power's places

only the symbols

and i think

The correct behavior would be no, I'd think.

it would return

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

err

I think you mean

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

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

with z instead of x

and a negative in front

how do i do that ?

Changed

Use `

instead of quotations marks

set_sym should be ordered by RCPSymbolCompare

i see

@irislq which character is that?

the one on the same key as the tilde

~

except don't push shift

What James said

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

No, it would give

`-2 * y**2 z`

I think]

so.. yes. 2 to y and 1 to z, aka y^2 and z

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

welp

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?

Just to hold the symbols

When converting to

`set_sym`

the dictionary would have to permuted as well
I see.

`{y, x}, {{1, 2}, 3}`

-> `{x, y}, {{2, 1}, 3}`

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.

`add_mul_poly`

wouldn't have to be changed at all
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 That is what I understood.

@myluszczak, yes, those will have to be declared friend

@myluszczak How are you gonna achieve the permutation?

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

@isuruf How do we round Real_double to Integer?

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

I see.

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?

Umm, it's off the top of my head but

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.

@srajangarg I can see how that would work. Thanks.

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

No, no, this has been helpful.

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

IST, it's 11:30 AM same as Isuru's. Goodbye!

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

You think we should define operator overloads for

`RCP`

?
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

Right

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