Related projects
Discover more projects across a range of sectors and discipline — from AI to cleantech to social innovation.
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.
Dr. Michael Monagan
Jaiganesh Balasundaram
Mathematics
Information and communications technologies
Simon Fraser University
Globalink Research Internship
Discover more projects across a range of sectors and discipline — from AI to cleantech to social innovation.
Find the perfect opportunity to put your academic skills and knowledge into practice!
Find ProjectsThe strong support from governments across Canada, international partners, universities, colleges, companies, and community organizations has enabled Mitacs to focus on the core idea that talent and partnerships power innovation — and innovation creates a better future.