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? Sent from my iPhone > On 30 Apr 2016, at 20:44, Mosè Giordano <[email protected]> wrote: > > Hi Sheehan, > > 2016-04-30 8:12 GMT+02:00 Sheehan Olver: >> >> How does this compare to AMVW.jl? >> >> https://github.com/andreasnoack/AMVW.jl > > I compared both programs with this script (requires development version of > PolynomialRoots): > > using Benchmarks, PolynomialRoots, AMVW > > for polynomial in ([120im, -(184 + 90im), (138 - 57im), (54im - 15), -(6 + > 9im), 1.], > rand(Complex{Float64}, 101)) > info("$(length(polynomial)-1)th-order polynomial") > PRroots = PolynomialRoots.roots(polynomial) > AMVWroots = AMVW.rootsAMVW(polynomial) > println("\nPR maximum error: ", > maximum(abs(PolynomialRoots.evalpoly(PRroots, polynomial)))) > println("AMVW maximum error: ", > maximum(abs(PolynomialRoots.evalpoly(AMVWroots, polynomial)))) > println("\nPR benchmark:\n", @benchmark PolynomialRoots.roots(polynomial)) > println("AMVW:\n", @benchmark AMVW.rootsAMVW(polynomial)) > end > > This is the result: > > INFO: 5th-order polynomial > > PR maximum error: 8.526512829121202e-14 > AMVW maximum error: 3.0505379675102492e-12 > > PR benchmark: > ================ Benchmark Results ======================== > Time per evaluation: 2.82 μs [2.74 μs, 2.91 μs] > Proportion of time in GC: 0.00% [0.00%, 0.00%] > Memory allocated: 656.00 bytes > Number of allocations: 9 allocations > Number of samples: 2001 > Number of evaluations: 12501 > R² of OLS model: 0.952 > Time spent benchmarking: 0.78 s > > AMVW: > ================ Benchmark Results ======================== > Time per evaluation: 26.72 μs [24.77 μs, 28.67 μs] > Proportion of time in GC: 0.00% [0.00%, 0.00%] > Memory allocated: 1.03 kb > Number of allocations: 9 allocations > Number of samples: 100 > Number of evaluations: 100 > Time spent benchmarking: 0.12 s > > INFO: 100th-order polynomial > > PR maximum error: 2.2724270820617676e-7 > AMVW maximum error: 1.6100194395356297e-6 > > PR benchmark: > ================ Benchmark Results ======================== > Time per evaluation: 904.96 μs [887.77 μs, 922.15 μs] > Proportion of time in GC: 0.00% [0.00%, 0.00%] > Memory allocated: 18.45 kb > Number of allocations: 424 allocations > Number of samples: 100 > Number of evaluations: 100 > Time spent benchmarking: 0.19 s > > AMVW: > ================ Benchmark Results ======================== > Time per evaluation: 4.03 ms [3.97 ms, 4.09 ms] > Proportion of time in GC: 0.00% [0.00%, 0.00%] > Memory allocated: 9.41 kb > Number of allocations: 9 allocations > Number of samples: 100 > Number of evaluations: 100 > Time spent benchmarking: 0.51 s > > So PolynomialRoots.jl is both faster and more precise than AMVW.jl. Note > that this package employs an algorithm based on finding eigenvalues of > companion matrix, like Polynomials.jl. Note that both algorithms often fail > to converge to the actual roots for large degree polynomials, but next > version of PolynomialRoots will feature support for multiple precision > calculations. I'll hopefully release it in the next few days. > > Bye, > Mosè
