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 -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/sympy. To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/50d07f38-d86c-4f60-b6a0-3f3a0859a050%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
