2016-04-30 14:22 GMT+02:00 Sheehan Olver:
>
> Hi Mose,
>
> I think AMVW is specifically designed for large degree polynomials: it's
> an O(n^2) algorithm that works via orthogonal transformations on the
> companion matrix
>
> How do the timings compare on, say, a degree 200 polynomial?
>
Just replace 101 with 201 in my previous script. For 200th-degree
polynomial, PolynomialRoots.jl is still a bit faster, AMVW becomes faster
at even larger degrees:
INFO: 400th-order polynomial
PR maximum error: 3.1349840509961133
AMVW maximum error: 8.091848829362318e30
PR benchmark:
================ Benchmark Results ========================
Time per evaluation: 133.95 ms [125.45 ms, 142.45 ms]
Proportion of time in GC: 0.07% [0.00%, 0.27%]
Memory allocated: 1.20 mb
Number of allocations: 38837 allocations
Number of samples: 75
Number of evaluations: 75
Time spent benchmarking: 10.27 s
AMVW:
================ Benchmark Results ========================
Time per evaluation: 52.97 ms [52.36 ms, 53.57 ms]
Proportion of time in GC: 0.00% [0.00%, 0.00%]
Memory allocated: 33.64 kb
Number of allocations: 9 allocations
Number of samples: 100
Number of evaluations: 100
Time spent benchmarking: 5.45 s
I wouldn't say that speed is of any utility if one gets such inaccurate
results. Hpwever, I feel that for large degree polynomials limited
precision is set to be always a problem, either in root finding or
polynomial evaluation.
Bye,
Mosè
