Investigation on Jenkins-Traub RPOLY Algorithm
Contents
Problem Explanation
Scilab Debian package contains code that is under the ACM software license. The problematic code is the Fortran implementation of the Jenkins and Traub algorithm
The problem is reported here in Debian and here in Scilab.
Investigation
In Freemat
Uses eigenvalues of companion matrix to find the roots:
In R
Uses a C implementation under GPL-2 software license
http://searchcode.com/codesearch/view/18690281/
In Maxima
Uses a Lisp implementation that is a translation of TOMS 493 implementation (should be under ACM software license)
http://searchcode.com/codesearch/view/22770129/
In Python Numpy
Uses eigenvalues of companion matrix to find the roots
https://github.com/numpy/numpy/blob/master/numpy/polynomial/polynomial.py
In Wolfram Research
Uses the implementation of IMSL numerical libraries which is proprietary:
http://mathworld.wolfram.com/Jenkins-TraubMethod.html
In SimTK
Uses a C++ implementation of TOMS 493 (should be under ACM software license)
https://simtk.org/api_docs/api_docs10/SimTKcommon/classSimTK_1_1PolynomialRootFinder.html
Suggested solutions
Using R implementation
R implementation is under GPL-2 which is compatible with CeCILL V2 software licence. However proprietary software are forbidden to link or use GPL-2 code:
This General Public License does not permit incorporating your program into proprietary programs. If your program is a subroutine library, you may consider it more useful to permit linking proprietary applications with the library. If this is what you want to do, use the GNU Lesser General Public License instead of this License.
While this is not a problem for Scilab distribution, it could be problematic for people using Scilab inside a proprietary, non-free application.
Coding the Algorithm from the publication
The algorithm is described in this paper by Jenkins and Traub and the stopping criterion is described in this paper by Duane A. Adams (see also the webpage by the royal society open science).
Coding it directly from the paper would add another free implementation of the algorithm that could be used inside Scilab.
Using a different method to find roots
Other algorithms exists:
- Eigenvalue method (calculate the eigenvalues of the companion matrix of the polynomial)