I think AMVW is backward stable: so it's calculating the exact roots of a near by polynomial
But even when roots are inaccurate, certain functions of the roots are accurate: e.g. f(lambda_1) + ... + f(lambda_n) Where f is a polynomial. Sent from my iPhone > On 30 Apr 2016, at 22:48, Mosè Giordano <[email protected]> wrote: > > 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è
