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è
