Re: sparse polynomial arithmetic

On Apr 3, 3:57 pm, Bill Hart <goodwillh...@xxxxxxxxxxxxxx> wrote:
You want to know the time for classical multiplication, or FLINT's
fastest algorithm for doing this computation? The classical algorithm
is going to take forever. There is no attempt to optimise that for big
problems like this.

I was hoping to get a time for the classical O(n^2) algorithm, because
for sparse problems that's the amount of coefficient arithmetic that
everyone has to do. FLINT has fast arithmetic for Z, so it's a good
test. I realize you could do blocking and stuff to better utilize the
cache.

And I would actually like to see the times for the best dense
algorithm as well :)
.

Relevant Pages

  • Re: Large-numbers division way too slow -- what to do?
    ... algorithm is now responsible for most of the slowness. ... construct test cases where q has m+1 digits. ... Contrary to popular belief, it does NOT use less elementary ... operations than a well-implemented classical algorithm. ...
    (sci.crypt)
  • Re: Solving mazes!!!
    ... >> The classical algorithm of solving mazes is keep looking left or keep ... >> elseif then go forward ...
    (comp.lang.c)
  • Re: The clock is ticking on encryption
    ... If someone had shown that there isn't a quantum algorithm ... there can't be a classical algorithm for breaking FOO either. ...
    (sci.crypt)
  • Re: Recursively enumerable sets
    ... If n is not a member of the ... this algorithm may run forever." ... I know you already wrote me that the algorithm may run forever. ... What about evens plus "3"? ...
    (comp.theory)
  • Re: Which function is used for computing a gradient of an image
    ... Which is the best way to optimise this? ... is there a simple method of not using an algorithm? ... NASA) produces gigapixel images by panning the camera by subpixel ...
    (comp.soft-sys.matlab)