PolynomialRoots.jl

Build Status	Code Coverage

Introduction

PolynomialRoots.jl is a library for finding roots of complex univariate polynomials, written in Julia.

This is an implementation in Julia of the General Complex Polynomial Root Solver, written in Fortran, by Jan Skowron and Andrew Gould. All the credits goes to them for the original algorithm.

The root finding algorithm employed in this library is described in

• J. Skowron & A. Gould, 2012, "General Complex Polynomial Root Solver and Its Further Optimization for Binary Microlenses", arXiv:1203.1034

This algorithm aims to be fast and precise, more than the well known zroots procedure described in Numerical Recipes books, whose implementations in C and Fortran are not available as free software, according to the definition of the Free Software Foundation.

PolynomialRoots.jl can also take advantage of native arbitrary precision capabilities of Julia and achieve more precise results.

Note: the adopted algorithm can give highly inaccurate results for polynomials of order above ~30. This can be mitigated by using multiple precision calculations (see example below).

Installation

PolynomialRoots.jl is available for Julia 0.7 and later versions, and can be installed with Julia built-in package manager. In a Julia session run the command

julia> Pkg.add("PolynomialRoots")

You may need to update your package list with Pkg.update() in order to get the latest version of PolynomialRoots.jl.

Older versions are available also for Julia 0.4-0.6.

Usage

After installing the package, run

using PolynomialRoots

or put this command into your Julia script.

PolynomialRoots.jl provides two functions to find the roots of complex polynomials

roots(polynomial[, roots, polish=true, epsilon=1e-20])
roots5(polynomial[, roots, epsilon=1e-20])

roots can be used to solve polynomials of any degree, roots5 is tailored to (and works only for) polynomials of degree 5. This function exists because one of the methods to calculate gravitational microlensing amplification by a binary lens requires solving a fifth-order complex polynomial. roots5 should be more robust than roots for this class of polynomials.

The mandatory argument for both functions is:

• polynomial, the vector holding coefficients of the polynomial you want to solve, in ascending order, from the lowest to the highest. Coefficients can be complex and real

Optional arguments are:

• roots: if you roughly know in advance the position of the roots, you can pass the vector with the known roots to speed up convergence. roots vector must be one element shorther than polynomial. In roots5, the roots will be only polished. Elements of the vector can be complex and real
• polish (boolean keyword, only for roots): if set to true, after all roots have been found by dividing original polynomial by each root found, all roots will be polished using full polynomial. Default is false
• epsilon (floating point optional keyword): this is used to determine the stopping criterion described in Skowron & Gould paper. If not set, it defaults to machine precision of polynomial (and roots) argument(s). This is not the precision with which the roots will be calculated.

The functions return in output the Complex vector with all roots of polynomial. Note: if roots optional argument is provided, it is not changed in-place.

Examples

Find the roots of

(x - i)*(x - 2)*(x - 3*i)*(x - 4)*(x - 5*i) =
  x^5 - (9*i + 6)*x^4 + (54*i - 15)*x^3 + (138 - 57*i)*x^2 - (184 + 90*i)*x + 120*i

This is a fifth-order polynomial, so we can find its zeros with both roots and roots5:

julia> roots([120im, -(184 + 90im), (138 - 57im), (54im - 15), -(6 + 9im), 1])
5-element Array{Complex{Float64},1}:
 -1.55431e-15+5.0im
 4.0+1.77636e-16im
  1.55028e-15+3.0im
 -1.04196e-16+1.0im
 2.0-2.00595e-16im

julia> roots5([120im, -(184 + 90im), (138 - 57im), (54im - 15), -(6 + 9im), 1])
5-element Array{Complex{Float64},1}:
  5.92119e-16+5.0im
  4.0-1.4803e-16im
 2.0+1.88202e-16im
 -1.88738e-15+3.0im
  2.10942e-15+1.0im

PolynomialRoots.jl handles polynomials with high-multiplicity roots as well. For example, consider

(x + 1)^5 = x^5 + 5x^4 + 10x^3 + 10x^2 + 5x + 1

You can find its roots with

julia> roots([1, 5, 10, 10, 5, 1])
5-element Array{Complex{Float64},1}:
 -1.0+0.0im
 -1.0+0.0im
 -1.0+0.0im
 -1.0+0.0im
 -1.0+0.0im

julia> roots5([1, 5, 10, 10, 5, 1])
5-element Array{Complex{Float64},1}:
 -1.0+0.0im
 -1.0+0.0im
 -1.0+0.0im
 -1.0+0.0im
 -1.0+0.0im

Arbitrary precision

Due to limited precision of Float64 type, extraction of roots of polynomials can give inaccurate results, even for low-order polynomials. This is caused, i.e., by catastrophic cancellation in computation of discriminant Δ = sqrt(b^2 - 4ac) of second-order polynomials. For example, the actual roots of

94906265.625*x^2 - 189812534*x + 94906268.375

are

x_1 = 1.000000028975958
x_2 = 1.000000000000000

but when you try to calculate them in double-precision you get

julia> r = roots([94906268.375, -189812534, 94906265.625]);

julia> r[1]
1.0000000144879793 - 0.0im

julia> r[2]
1.0000000144879788 + 0.0im

If you are interested in double-precision accuracy, you can work around this problem by calculating the roots with higher precision and then transforming the result to double-precision. Julia natively supports multiple precision calculations, so what you have to do is only to pass BigFloat numbers to roots function (note: in order to correctly initialize an arbitrary precision floating point constant it is better to use the big string literal, see http://docs.julialang.org/en/stable/stdlib/numbers/#Base.BigFloat):

julia> r = roots([big"94906268.375", -189812534, big"94906265.625"]);

julia> Float64(r[1])
1.0000000289759583

julia> Float64(r[2])
1.0

Note that in this case there is a trade-off between speed and higher accuracy and precision.

Related projects

Another Julia package for finding roots of complex polynomials is Polynomials.jl, by Jameson Nash and other contributors. This package does much more than finding roots of polynomials (among other features, it can integrate and differentiate polynomials). In order to solve the polynomial, Polynomials.jl calculates eigenvalues of its companion matrix, but PolynomialRoots.jl is usually faster by up to an order of magnitude and often slightly more precise. In addition, Polynomials cannot extract roots in arbitrary precision. If you are after speed and precision, PolynomialRoots.jl can still be a better option.

Development

The package is developed at https://github.com/giordano/PolynomialRoots.jl. There you can submit bug reports, make suggestions, and propose pull requests.

History

The ChangeLog of the package is available in NEWS.md file in top directory.

License

The PolynomialRoots.jl package is licensed under version 2.0 of the Apache License or the GNU Lesser General Public License version 3 or any later version, at your option. These are the same licenses used by the General Complex Polynomial Root Solver.

A custom in the scientific comunity is (regardless of the licence you chose to use or distribute this software under) that if this code was important in the scientific process or for the results of your scientific work, we kindly ask you for the appropriate citation of the paper Skowron & Gould 2012 (http://arxiv.org/abs/1203.1034), and we would be greatful if you pass the information about the proper citation to anyone whom you redistribute this software to.

The authors of the General Complex Polynomial Root Solver, the original Fortran library (http://www.astrouw.edu.pl/~jskowron/cmplx_roots_sg/) from which PolynomialRoots.jl has been translated, are Jan Skowron, Andrew Gould.

The original author of PolynomialRoots.jl is Mosè Giordano.