GSoC 2012: Multivariate polynomials
Anthony Burzillo
Alexey U. Gudchenko
Hi, Anthony.
I can't talk about this topic myself, but as it is in the list of idea
is listed on the GSoC ideas list, then it is a good task.
Regarding difficulty, I only add that the problems may be how to embed
it in the SymPy core. It can be easy to implement as a separated
program, but in SymPy the implementation must have effective caching, is
related with interaction with the core, inheritances from main classes,
embedding to the printing system, assumption system, maintain various
bases of polynomials and so on.
Practically the most of efforts for implementation are directed to solve
those problems.
Not also, that some work was started in the master brunch (as mention i
Idea page, take a look at sympy/polys/factortools.py in the SymPy source
code), and also at the PR 609 [1]. May be they are only about the
multivariate polynomials themselves, without factorization problems.
I hope that others can clarify more about current status.
Meanwhile you can go ahead with this topic, see the [2] and try to send
a patch.
[1] https://github.com/sympy/sympy/pull/609
[2] http://code.google.com/p/sympy/issues/list?q=label:Polynomial
Alexey.
Aaron Meurer
> 21.03.2012 07:34, Anthony Burzillo пишет:
>> Hi all, my name's Anthony Burzillo and I am currently a freshman at Johns
>> Hopkins studying Physics and CS.
>>
>> I am particularly interested in SymPy since, as a Physics/Math major, I
>> often find myself checking my processes with Mathematica, and therefore see
>> the value in an open source project like SymPy and would love to get
>> involved!
>>
>> Anyways, after perusing the ideas page I found myself particularly
>> interested by the "Multivariate polynomials and factorization" task (I
>> particularly like algebra). I have read a bit on geobuckets, and
>> looked through the source code.
>>
>> I was just wondering if you guys think that this would be too hard for
>> someone with no previous knowledge of multivariate polynomials to handle (I
>> like challenges, but I hope this is not impossible). I have taken Lin Alg
>> and Calc III, and I am about half way through an abstract algebra text I
>> have been reading on the side.
Well, I guess this is for you to decide. It will depend on your base
knowledge of algebra, because if you don't understand fundamental
concepts like rings, fields, field extensions, polynomial division and
gcd, etc. you will never have a chance to understand polynomial
algorithms (to use an analogy, you could never learn calculus if you
don't have a good understanding of trigonometry and high school
algebra).
If you have those down (those will be in your abstract algebra book),
you may be able to learn the algorithm. It depends on how complicated
it is. Some algorithms require relatively little algebra, and some
require you a bit more (because they build off of many classical
results).
So I don't want to discourage you, because it really depends on where
you are already, and how good you are at learning new things.
It looks like the geobuckets idea requires little algebra knowledge,
because it is more about the internal representation of polynomials.
This will require you to have a good sense of how things work in
Python, so that you can really achieve the running times listed. You
should take a look at the present internal representation in
sympy/polys/densebasic.py, (and other dense* files) and try to
understand how it works. Mateusz's master's thesis would also be a
good source (https://github.com/mattpap/masters-thesis).
You should also look into other ways to efficiently represent
polynomials. This can be considered more of a CS problem than a math
problem, except that you will have to reimplement the basic
fundamental algorithms that rely specifically on the internal
representation. The heaps idea is another way to do this (you should
search for the two papers listed in the ideas page; let me know if you
are unable to download them). You can research other ways to
represent polynomials, especially sparse schemes. Also, take a look
at the sparse stuff that has been started already in the polys module.
>>
>> I'm fully willing to do a lot of reading for the balance of the semester.
>>
>> Thanks!
>>
>> Anthony
>>
>
> Hi, Anthony.
>
> I can't talk about this topic myself, but as it is in the list of idea
> is listed on the GSoC ideas list, then it is a good task.
>
> Regarding difficulty, I only add that the problems may be how to embed
> it in the SymPy core. It can be easy to implement as a separated
> program, but in SymPy the implementation must have effective caching, is
> related with interaction with the core, inheritances from main classes,
> embedding to the printing system, assumption system, maintain various
> bases of polynomials and so on.
> Practically the most of efforts for implementation are directed to solve
> those problems.
The polys are mostly separate from the SymPy core. Sure they use one
another, but you don't have to worry about things like caching,
printing, and assumptions inside the polys, for example. The problems
involved with getting the core to work inside the polys have already
been solved, for the most part, and the separation inside the code is
done pretty well (using the ground types), so that it should be
possible to do this project without really worrying about it.
>
> Not also, that some work was started in the master brunch (as mention i
> Idea page, take a look at sympy/polys/factortools.py in the SymPy source
> code), and also at the PR 609 [1]. May be they are only about the
> multivariate polynomials themselves, without factorization problems.
>
> I hope that others can clarify more about current status.
>
> Meanwhile you can go ahead with this topic, see the [2] and try to send
> a patch.
Yes, start thinking about the patch requirement. Also, the submission
date is right around the corner, so you should start thinking about
the proposal as well (of course, it's probably better to finalize your
idea with here with the discussions first).
Aaron Meurer
>
>
> [1] https://github.com/sympy/sympy/pull/609
> [2] http://code.google.com/p/sympy/issues/list?q=label:Polynomial
>
> Alexey.
>
> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To post to this group, send email to sy...@googlegroups.com.
> To unsubscribe from this group, send email to sympy+un...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
>