Super Fast Sparse Polynomial Interpolation
I’ve started a new research project with the goal of implementing a new algorithm which interpolates a polynomial F of degree D in N variables with T non-zero terms.
It has long been known how to interpolate a polynomial F(x) in one variable of degree D from D+1 values of F in O( D log D ) time. The tool to do this is the Fast Fourier Transform. It is considered to be one of the top 10 scientific computing achievements of the 20th century. It has many applications. But, if the polynomials are multivariate, in N variables they are usually sparse, that is, the number of terms T is much less than D^N, the Fast Four Transform may not help. On such polynomials, the Fast Fourier Transform may take a very long time. Since sparse polynomials occur in many practical applications, we need new algorithms and new tools. A lot of researchers, beginning with Richard Zippel in his PhD thesis in 1979, have developed algorithms which are efficient for sparse polynomials.
We have a new algorithm that theoretically, is much better than Zippel’s algorithm, and the other algorithms in the literature. Theoretically, It combines ideas and tools from cryptography, theoretical computing science, number theory, and algebra. But in order for it to be fast, we need to implement a variety of algorithms, including the Fast Fourier Transform, for polynomials with coefficients from the integers modulo a prime where the prime can be small, e.g., 32 bits, medium, e.g. 64 bits, and large, i.e., more than 64 bits long. Each case will be important for practical applications. We need help with programming mathematical algorithms for different cases and trying out various algorithms. The list of algorithms needed includes algorithms for computing roots of polynomials over finite fields, taking discrete logarithms in finite fields where discrete logarithms are tractable, multiplying and dividing polynomials, computing greatest common divisors of polynomials, etc.The student would participate in a small group of students, two graduate students and one other undergraduate student in a project to design and implement a software package of mathematical algorithms for polynomials in GF(p)[x], that is, polynomials in one variable whose coefficients are integers reduced modulo a prime p. We will need a 32 bit library, a 64 bit library and a quadruple precision 128 bit library. We will use the C programming language for the final version of the code but will try out algorithms in Maple.
