GSoC'19 Project in Multivariate polynomials and factorization and proposed plan of action.

[shrivast...@gmail.com]

Hello,

I would be interested to take up the idea of Multivariate polynomials and factorization as a GSoC project this year. I've gone through the related documents and paper required for the execution of this project, and here is a proposed plan of action (rudimentary for now and will involve modification after consulting with mentors).

1. Implementing the Euclidean algorithm to determine GCDs. (In Euclidean domains)

2. Move on to implementing the Modular GCD algorithm or MGCD (when the polynomials have a dense rather than a sparse structure)

Whilst MGCD might work well for univariate polynomials, for multivariate polynomials we need to look at other algorithms.

3. SparseMod algorithm for multivariate polynomials (A probabilistic algorithm better suited for multivariate polynomials, developed by Zippel in 1979 in his Ph.D. thesis).

4. Implementing the Extended Zassenhaus Algorithm (EZ-GCD). (Another GCD algorithm better suited for multivariate polynomials, developed by Moses and Yun in 1973 and named after Zassenhaus to honor his work in number theory). Here, multivariate polynomials are reduced to a univariate representation, the GCD is then determined in a simpler domain. Hensel’s Lemma is used repeatedly to lift the results up to the multivariate domain. As with the MGCD, relatively prime polynomials are discovered quickly.

Several factorization algorithms first need GCDs of the polynomials. Computing GCDs of polynomials is also necessary for adding rational functions. Both problems are aided by algebraical concepts which allow us to break a hard problem (a multivariate polynomial over the integers) up into several much easier problems (univariate polynomials over finite fields). This is done by applying the Chinese Remainder Algorithm and Hensel Liftings.  

5. Start with an easy algorithmic implementation for finding the square-free factors of a polynomial. This algorithm can be applied by other factorization algorithms, and the square-free decomposition used to find the ”proper” factorization.

6. A better alternative to the above-mentioned algorithmic implementation is the Yun’s Square-Free factorization algorithm as it calculates one additional differentiation, but manages to avoid the repeated GCD calculation of SquareFree.

For references to theory and algorithms, I'll be using the following links and papers (also subject to change):-

1. https://pdfs.semanticscholar.org/e64a/29b3b0a991d292acd97ba2da88247a0be1e1.pdf

2. https://www3.risc.jku.at/education/courses/ws2011/ca/3-gcd.pdf

3. http://wwwmayr.in.tum.de/konferenzen/Jass07/courses/1/Freund/Freund_slides.pdf

4. https://dl.acm.org/citation.cfm?id=1089228

If any mentor is willing to take this up, as a project, during the GSoC'19 summer please let me know. I'd love to receive any reviews on this plan (whether it's about the addition of a few topics/algorithms or their modification) so that I can start working on my proposal.

Thank You.

Regards,

Avi Shrivastava

[Kalevi Suominen]

I think that most of those topics have already been implemented. You can find the implementations in factortools.py and galoistools.py to see what remains to be done.

Kalevi Suominen

[shrivast...@gmail.com]

Dear Kalevi,

I didn't realize that the ideas page for GSoC'19 hadn't been updated - at least for the multivariate polynomials and factorization idea. Please do update it.

I'll be highly motivated to work in this module though, as it's an interesting module to expand on. Can you suggest me some algorithms that could be implemented in this module (regarding factorization and GCDs of multivariate or univariate polynomials would be great, but not limited to it) that'll be big enough that can constitute an entire summer? (Of course, I'll go through factortools.py and galoistools.py and see what all can be done but a piece of advice from you or any mentor in the matter, would be highly valuable).

Thank you.

Regards,

Avi Shrivastava