Software for solving polynomial equations

From this page you can download software for solving polynomial equations. The code is of high quality and can be used for production purposes and for scientific research purposes. There are solvers for different types of polynomial equations:

  • generic real polynomial equations in double precision (53 bits)
  • generic real polynomial equations in quadruple precision (105 bits)
  • generic complex polynomial equations in double precision
  • generic complex polynomial equations in quadruple precision
  • specialized fast and accurate solvers for real polynomials of degrees 2, 3, 4, and 5
  • specialized fast and accurate solver for sparse polynomials of any degree, both real and complex, with separate code for trinomials of the form a xn1 + b xn2 + c, with real or complex a, b, c.

All software, mentioned above, is believed to be of very good quality. This is demonstrated with an extensive test suite, covering many types of polynomials, including several hard to solve types with high dynamic range of zeros, clustered zeros and zeros with multiplicity larger than 1. A rigorous theoretical error bound for an idealized numerical solver is defined and the error of the actual solver software is assessed against that theoretical error bound. The specialized solvers perform exceptionally well. The general solvers also perform well, albeit sometimes with errors, a few orders of magnitude larger than one would expect from an ideal numerical solver.


Organization of the software packages

The software is written in Java and is tested on a variety of JVM's (OpenJDK and Oracle JDK) of different versions. The code compiles on any Java 11 or newer compiler. The structure of the code is shown in the diagram below.




The diagram above shows green packages, with production-quality code:

  • polarith : A package for doing all kinds of arithmetic on complex numbers and on quadruple precision numbers in Java. This code can be used on its own in any scientific application. The quadruple precision arithmetic is much faster than Java's native multi-precision code, used at similar precision.
  • polsolve.deg2345 : A collection of packages for specialized solvers for real polynomials of degree 2, 3, 4, or 5.
  • polsolve.aberth: Sparse polynomials of the form a xn1 + b xn2 + c xn3 + ..., with real or complex coefficients a, b, c, etc.
  • polsolve.mr : A package, containing general polynomial solvers, based on the Madsen Reid polynomial solver algorithm. This algorithm is fast and very robust. A few small shortcomings of the original algorithm have been repaired, to make it even more robust. It is based on the Fortran codes PA06 and PA07. These algorithms have been ported to Java and at the same time, some improvements were made, clearly indicated in the Java code.
  • polsolve.pzeros : This is based on D. Bini's implementation of the so-called POLZEROS algorithm, implemented in Fortran 90 in 1996. This algorithm is ported to Java, using quadruple precision from the polarith package. It finds all zeros of a given polynomial in one go and does not need polynomial deflation. It is an alternative to the Madsen Reid algorithm. The algorithm can be used on polynomials with complex coefficients, but a specialized faster version, working on polynomials with real coefficients also is available. If you do all your computations in quadruple precision, then the POLZEROS algorithm, may be slightly faster than the Madsen Reid algorithm, but in practice, the differences are marginal and both algorithms seem to perform also comparably in terms of robustness and accuracy.
  • polsolve.testdriver : A package, which allows setting up extensive tests of all kinds of polynomials and doing detailed analysis on the outcomes of the tests. With the help of this test package a large test suite is created, which demonstrates the capabilities of the polynomial solvers, presented here.
  • rnd : A small package, containing an improved implementation of Java's Random class (as a subclass), based on the Xoroshiro random generator, with 256 bits of state. This is a very fast all-purpose random generator, with outstanding statistical properties and a huge periodic length. After I developed the pseudo random number generator, based on this, it also is incorporated in several commercial and open source packages, but I kept this nice little implementation, as it works very well.

Besides the production-quality code, there are two packages in blue color.

One of them is a general package for creating PNG-images (other image formats can also be created, but best results are obtained with PNG's). It can be used for easily drawing grids and drawing graphs or figures in that grid, it also can be used for general plotting of pixels and drawing lines and text. It also allows loading an existing image, drawing text, lines or pixels in that, and then saving it again. It is used quite extensively in demo code, but I would not consider it a mature image generation package. The main reason for me to create this package was that I wanted something, which can be used very easily with just a few lines of code. Performance and flexibility were of secondary concern when developing this package.

The other package, drawn in blue, is for computing zeros of so-called semi-polynomials. I have written a web page about these mathematical objects. This package was used for demonstrating the theory, given in the web page, and for making nice pictures for the web page. This package also is not a production-quality package, but the code for semi-polynomials with rational coefficients is sufficiently robust and versatile to be used in scientific programs, which need solving that type of equations.

Finally, there are several packages, drawn in white color. These packages contain many Java-classes, having a main method, which can be executed. The usage-packages contain code, which demonstrates how to use the underlying polynomial solver packages. This code is very simple and is self-contained. Documentation, if needed at all, is present in that code. The test-packages contain tests, demonstrating the capabilities and accuracy of the polynomial solver packages. The code of these packages also demonstrates how the testing framework from the polsolve.testdriver package can be used. The demo-packages contain code, demonstrating how the polynomial solver packages can be used to create in somewhat more complex programs, while at the same time producing interesting graphs or demonstrating interesting properties of certain types of polynomials.




Downloading the software

The software is available as zip-files. All package names have fully qualified names, starting with oelen.net, followed by the names, displayed in the diagram above. Only the source code is provided. The software is small and the structure is simple. It should be easy, even for a starting Java-engineer, to incorporate the software into your own products, or building your own library/JAR from it, which can be used by your own software packages.

The software may be used freely. The documentation inside the software itself should be sufficient. The Java-doc system provides full API-documentation, which most IDE's (IntelliJ, Netbeans, Eclipse) will provide automatically, when the code is built. There are no dependencies on external libraries, other than what is present in a standard Java SE environment, hence no Maven or Gradle projects files are included. Just create your own projects with these source files in your favorite build environment. The download contains project directories for Netbeans, but the source can easily be extracted from that.

Here follow the links for downloading:

There also is a C-version of part of the software. The solvers for quadratic, cubic, quartic and quintic equations are available as C software. This C-software is an exact port of the Java code for double precision (64 bits, 53 bits mantissa) and it gives exactly the same results as the Java code for the same input. The C code, however, also can be compiled for so-called Intel extended precision (80 bits, 64 bits mantissa, the long double type, when using the GCC compiler on Intel or AMD hardware), giving an additional 3.5 digits of accuracy in the floating point arithmetic.
The C code is can be built, using a script mklib.sh and there are some very basic test programs, both for 53 bit precision and 64 bit extended precision.  These programs also demonstrate how the code can be used.
The C code can be downloaded here: solve2345.zip. 

back to top of page

back to general software page