[ANN] PolynomialRoots.jl: Fast Complex Polynomial Root Finder

[Mosè Giordano]

Hi,

a couple of days ago I released version 0.0.2 of PolynomialRoots.jl (formerly known as CmplxRoots.jl, some people suggested to change the name to something more descriptive), a fast root finder of real and complex polynomials.

This is a Julia implementation of the algorithm described in

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

PolynomialRoots.jl is a registered Julia package, so you can install it with the package manager:

Pkg.add("PolynomialRoots")

Two functions are exposed to the users:

roots(polynomial[, roots, polish=true])
roots5(polynomial[, roots])

The first function can be used to solve polynomials of any order, the second one is specialized and optimized for (and works only for) polynomials of fifth-order

This new version of PolynomialRoots.jl features support for arbitrary precision calculations.  This is very useful for calculating roots of polynomials of very large degree (some hundreds) that couldn't be solved using double precision calculations.  Actually, this cures inaccurate results also for low order polynomials, like second-order ones, where catastrophic cancellation is a problem.  For example, the actual roots of (see https://en.wikipedia.org/wiki/Loss_of_significance)

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. What you have to do is only to pass BigFloat numbers to roots function:

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

julia> Complex128(r[1])
1.0000000289759583 - 0.0im

julia> Complex128(r[2])
1.0 + 0.0im

as expected.

This package is licensed under Apache License 2.0 or GNU Lesser General Public License version 3 or any later version, as well as under a "customary scientific license", which implies that if this code was important in the scientific process or for the results of your scientific work, you are asked for the appropriate citation of the paper Skowron & Gould 2012 (http://arxiv.org/abs/1203.1034).

Cheers,
Mosè

[Steven G. Johnson]

On Thursday, May 5, 2016 at 10:24:53 AM UTC-4, Mosè Giordano wrote:

This package is licensed under Apache License 2.0 or GNU Lesser General Public License version 3 or any later version, as well as under a "customary scientific license", which implies that if this code was important in the scientific process or for the results of your scientific work, you are asked for the appropriate citation of the paper Skowron & Gould 2012 (http://arxiv.org/abs/1203.1034).

It's a really bad idea to imply that citation is a legal requirement in the license.   Such a requirement makes your code non free/open-source software.

The best approach is to simply make a polite request, but be explicit that it is not a legal requirement.   In practice, people will happily comply with such a request in my experience.  e.g. this is what we say for FFTW:

        In addition, we kindly ask you to acknowledge FFTW and its authors in any program or publication in which you use FFTW. (You are not required to do so; it is up to your common sense to decide whether you want to comply with this request or not.) For general publications, we suggest referencing: Matteo Frigo and Steven G. Johnson, “The design and implementation of FFTW3,” Proc. IEEE 93 (2), 216–231 (2005).

[Stefan Karpinski]

The phrasing of this licensing is unclear but essentially the same as the original Fortran library:

The authors release the source codes associated with the Paper under terms of the GNU Lesser General Public License version 2 or any later version, or under the Apache License, Version 2.0 as well as under a "customary scientific license", which implies that if this code was important in the scientific process or for the results of your scientific work, we ask for the appropriate citation of the Paper (Skowron & Gould 2012).

Their wording seems to indicate dual licensing under LGPL 2 or Apache 2, which would mean that following the terms of either license gives the right to use the software. But then it throws in the "as well as under a 'customary scientific license'" clause, which completely muddies the waters. Does that mean that you may use the software if you follow the terms of LGPL 2 AND cite them OR follow the terms of Apache 2 AND cite them? Or that you may use the software if you follow the terms of LGPL 2 OR cite them OR follow the terms of Apache 2 and cite them? Under the former interpretation, it would be illegal to use this software as part of a derived work including any GPL libraries (which includes Julia in its default configuration) since the "customary scientific license" conflicts with the GPL, thereby making it impossible to comply with all terms required to be allowed to use the combined product.

If the authors intended to require you to follow both the LGPL 2 and Apache 2 licenses, the situation may be even worse, since, IIRC, those licenses themselves conflict, so it would be impossible to satisfy the conditions required to be allowed to use the software at all.

It seems like it may be necessary to contact the authors and request their clarification of the terms under which one may use their software.

[Mosè Giordano]

Hi Steven and Stefan,

I confirm I used the same license as the original library. Actually,
I interpreted the "customary scientific license" as a request, not as
a legal obligation (but I'm not a native English speaker nor a
lawyer). The fact that two or more people can't agree on the
interpretation shows that probably the license requires clarification,
I'll contact the author and ask for it.

Bye,
Mosè

[Stefan Karpinski]

Great – they obviously intended for this to be open source and used, so I'm sure they won't mind clarifying.

[Mosè Giordano]

Dear all,

I've just noticed that a few weeks ago Jan Skowron clarified the license of original Fortran library: http://www.astrouw.edu.pl/~jskowron/cmplx_roots_sg/  It's clear now that one can choose to apply either Apache license or LGPL.  The customary scientific license has been dropped, now there is a simple invitation to cite the paper.

In order to make PolynomialRoots.jl as widely usable as possible in Julia environment, does it make sense to preserve this dual license for the package or it's better to choose one of them in order to avoid confusion?  My understanding is that both licenses are MIT-compatible in the sense that both LGPL and Apache codes can be linked in MIT code.

Cheers,
Mosè

[Steven G. Johnson]

On Friday, May 27, 2016 at 7:02:22 PM UTC-4, Mosè Giordano wrote:

In order to make PolynomialRoots.jl as widely usable as possible in Julia environment, does it make sense to preserve this dual license for the package or it's better to choose one of them in order to avoid confusion?

 I would preserve the dual license.  The Apache License is not compatible with GPLv2 (only with GPLv3) according to the FSF, so GPLv2 | Apache2 is strictly more compatible than either by themselves.