high performance computing on graphics processing units: hgpu.org

I participate to the elaboration of the library cumodp. My objective is to develop code for the exact calculation of the real roots of univariate polynomials. Stating this problem is very easy. However, as one dives into the details, one realizes that there are lots of challenges in order to reach highly efficient algorithmic and software solutions. The first challenge is that of representation. Traditionally, scientific software provide numerical approximations to the roots (real or complex) of a univariate polynomial which coefficients might themselves be known inaccurately. Nevertheless, in many applications, polynomial systems result from a mathematical model and their coefficients are known exactly. In this case, it is desirable to obtain closed form formulas for the roots of such polynomials. It is well know, however, from Galois Theory, that the roots of univariate polynomials of degree higher than 4 cannot be expressed by radicals. In this context, computing the real roots of such a polynomial f(x) elem R[x] means determining pairwise disjoint intervals with rational end points and an effective one-to-one map between those intervals and the real roots of f(x). Algorithms realizing this task are highly demanding in computer resources. In addition, such most efficient algorithms combine different mathematical tools such as Descartes’ rule of signs, Fast Fourier Transforms (FFTs), continued fractions, computing by homomorphic images, etc.