It was on a single core of an Opteron K10 6174 at 2.2GHz. I'm not sure what you mean by KS on the input. Nemo doesn't use KS on that benchmark (except possibly in Flint for the lowest level). This is comparable to what the other systems are doing, except Pari which uses a recursive sparse representation.
The code is in the Benchmarks test in test/Benchmark-test.jl.
It's not surprising the first benchmark is faster in Maple, since Maple can make use of a true sparse representation, possibly quite a bit of vectorisation on the processor you have and possibly multiple cores. The benchmark here uses only a dense representation, a single core and there is no explicit vectorisation (possibly none at all).
Pihanha for example will do both of those first examples in a fraction of the time that Nemo will. But again, it uses sparse representation and again can use multiple cores.
We'll do a sparse representation in Nemo later on, perhaps even wrap Pirhana.
The main purpose of the benchmark is actually to show off what the really fast Julia generics do for us, not to actually do this particular benchmark as fast as is humanly possible. In order to do that as fairly as possible, we deliberately use univariate polynomials over other univariate polynomials in all systems (except Pari, as noted), rather than dedicated multivariate polynomial rings.
For that CPU the times are good. My understanding is that Pari uses recursive dense, and Nemo is also using that, and you are instructing Magma to do that. I'll have to download Nemo and try it out :)
I used to think Pari used recursive dense too, but I've recently been informed it is more of a recursive sparse format. This is essentially the same thing except that they have special zero objects in every polynomial ring, so that their recursive tree is essentially a pruned tree.
As another comparison, on a 3.1GHz Opteron 4386 we get 33s for the first benchmark. I'm told this is not particularly modern either, but it's at least a bit closer to what you were using.
Just out of curiosity I tried adding a couple of lines of code to Nemo to force it to use its mul_ks for the first benchmark. This was actually way slower. I didn't look into why.
That first benchmark is pretty dense, so it's not at all unreasonable to use KS.
On the other hand, if we force it to use KS for Z[x][y][z][t] down to Z[x][y], then classical down to Z[x], then Flint for Z[x] itself, it gets marginally faster, with 40.6s.
Clearly neither of these approaches is an optimal strategy, as the Maple timings show.
The first benchmark is dense up to the total degree and the staircase structure is bad for Kronecker substitution. The fastest method is probably sparse polynomial interpolation.
It can certainly be done much faster, even on that CPU. We'll eventually get around to that.
We have a lot of generic matrix stuff missing at present though, so that's the priority for now.
There's also things like Puiseux series and capped absolute power series and a few things like that which we can't do without.
It would be a hell of a lot of fun to optimise the hell out of both those polynomial benchmarks, but we have to be realistic and go for breadth first, rather than depth, I think.
I modified the description of the second benchmark to be a little clearer. I can see why you were wondering about Kronecker segmentation. By "univariate" we simply meant generic univariate rings, over other generic univariate rings. But I removed that word altogether to prevent confusion.
Comments
I'd like to know the CPU to compare. For example, the first one is 5 seconds on a Core i5 4570 3.2 GHz in Maple.
The second problem is also not clear. Is there a Kronecker substitution on the input? If so, what are the degrees? I'd like to see the code used.
It was on a single core of an Opteron K10 6174 at 2.2GHz. I'm not sure what you mean by KS on the input. Nemo doesn't use KS on that benchmark (except possibly in Flint for the lowest level). This is comparable to what the other systems are doing, except Pari which uses a recursive sparse representation.
The code is in the Benchmarks test in test/Benchmark-test.jl.
It's not surprising the first benchmark is faster in Maple, since Maple can make use of a true sparse representation, possibly quite a bit of vectorisation on the processor you have and possibly multiple cores. The benchmark here uses only a dense representation, a single core and there is no explicit vectorisation (possibly none at all).
Pihanha for example will do both of those first examples in a fraction of the time that Nemo will. But again, it uses sparse representation and again can use multiple cores.
We'll do a sparse representation in Nemo later on, perhaps even wrap Pirhana.
The main purpose of the benchmark is actually to show off what the really fast Julia generics do for us, not to actually do this particular benchmark as fast as is humanly possible. In order to do that as fairly as possible, we deliberately use univariate polynomials over other univariate polynomials in all systems (except Pari, as noted), rather than dedicated multivariate polynomial rings.
For that CPU the times are good. My understanding is that Pari uses recursive dense, and Nemo is also using that, and you are instructing Magma to do that. I'll have to download Nemo and try it out :)
I used to think Pari used recursive dense too, but I've recently been informed it is more of a recursive sparse format. This is essentially the same thing except that they have special zero objects in every polynomial ring, so that their recursive tree is essentially a pruned tree.
As another comparison, on a 3.1GHz Opteron 4386 we get 33s for the first benchmark. I'm told this is not particularly modern either, but it's at least a bit closer to what you were using.
Just out of curiosity I tried adding a couple of lines of code to Nemo to force it to use its mul_ks for the first benchmark. This was actually way slower. I didn't look into why.
That first benchmark is pretty dense, so it's not at all unreasonable to use KS.
On the other hand, if we force it to use KS for Z[x][y][z][t] down to Z[x][y], then classical down to Z[x], then Flint for Z[x] itself, it gets marginally faster, with 40.6s.
Clearly neither of these approaches is an optimal strategy, as the Maple timings show.
The first benchmark is dense up to the total degree and the staircase structure is bad for Kronecker substitution. The fastest method is probably sparse polynomial interpolation.
It can certainly be done much faster, even on that CPU. We'll eventually get around to that.
We have a lot of generic matrix stuff missing at present though, so that's the priority for now.
There's also things like Puiseux series and capped absolute power series and a few things like that which we can't do without.
It would be a hell of a lot of fun to optimise the hell out of both those polynomial benchmarks, but we have to be realistic and go for breadth first, rather than depth, I think.
I modified the description of the second benchmark to be a little clearer. I can see why you were wondering about Kronecker segmentation. By "univariate" we simply meant generic univariate rings, over other generic univariate rings. But I removed that word altogether to prevent confusion.