## FastPolynomialRoots.jl

Fast and backward stable computation of roots of polynomials in Julia
Author andreasnoack
Popularity
8 Stars
Updated Last
2 Years Ago
Started In
August 2014

# FastPolynomialRoots.jl - Fast and backward stable computation of roots of polynomials

This package is a Julia wrapper of the Fortran programs accompanying Fast and Backward Stable Computation of Roots of Polynomials by Jared L. Aurentz, Thomas Mach, Raf Vandebril and David S. Watkins.

## Usage

The package provides the unexported function `FastPolynomialRoots.rootsFastPolynomialRoots(p::Vector{<:Union{Float64,Complex{Float64}}})` which computes the roots of the polynomial `p + p*x + p*x^2 + ... + p[k]*x^(k-1)`. The package also overwrites the `roots(::Polynomial)` methods in the `Polynomials` package for `Float64` and `Complex{Float64}` elements with the fast versions provided by this package. See the examples below.

## Example 1: Speed up `roots`

```julia> using Polynomials, BenchmarkTools

julia> @btime roots(p) setup=(p = Polynomial(randn(500)));
223.135 ms (23 allocations: 3.97 MiB)

julia> using FastPolynomialRoots

julia> @btime roots(p) setup=(p = Polynomial(randn(500)));
30.786 ms (7 allocations: 26.41 KiB)```

## Example 2: Roots of a polynomial of degree 10,000

A computation of this size would not be feasible on a desktop with the traditional method but can be handled by FastPolynomialRoots.

```julia> using Polynomials, BenchmarkTools, FastPolynomialRoots

julia> n = 10000;

julia> r = @btime roots(p) setup=(p = Polynomial(randn(n + 1)));
10.290 s (13 allocations: 508.38 KiB)

julia> sum(isreal, r)
7

julia> 2/π*log(n) + 0.6257358072 + 2/(n*π) # Edelman and Kostlan
6.489284260212659```

### Used By Packages

No packages found.
{"ft_lang_label":"__label__en","ft_lang_prob":0.58833134,"math_prob":0.84422976,"size":1485,"snap":"2022-05-2022-21","text_gpt3_token_len":442,"char_repetition_ratio":0.17420661,"word_repetition_ratio":0.02020202,"special_character_ratio":0.2949495,"punctuation_ratio":0.1521739,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9840082,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-05-16T12:58:45Z\",\"WARC-Record-ID\":\"<urn:uuid:929915df-9985-4373-969f-be7e9415e267>\",\"Content-Length\":\"86596\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:2b8217e4-6c6b-4630-9e7b-2f1393bb57a8>\",\"WARC-Concurrent-To\":\"<urn:uuid:ea4782f6-9a12-4951-937d-c48532ac6f90>\",\"WARC-IP-Address\":\"99.86.231.53\",\"WARC-Target-URI\":\"https://juliapackages.com/p/fastpolynomialroots\",\"WARC-Payload-Digest\":\"sha1:LUENCGU2K6RCFQLQC544DCFFSMJTBNIB\",\"WARC-Block-Digest\":\"sha1:VC2GPHO4QFUHCH64MZD36ZOFSFZRYDWE\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-21/CC-MAIN-2022-21_segments_1652662510117.12_warc_CC-MAIN-20220516104933-20220516134933-00316.warc.gz\"}"}