Re: [sympy] GSoC 2013: Univariate polynomials over algebraic domains

[Aaron Meurer]

You'll want to take a look at Mateusz's recent work in the polys
module, both at https://github.com/sympy/sympy/pull/1840 and at
https://github.com/mattpap/sympy/tree/new-polys.

Other than that, my recommendation is to keep digging into the polys
code. It can be dense, so take some time to try to understand how it
works. Also, take a look at the papers that describe the algorithms
you will be implementing, and make sure you understand enough of the
theory to do it.

Aaron Meurer

On Tue, Apr 23, 2013 at 3:14 PM, Katja Sophie Hotz
<katja.so...@student.tuwien.ac.at> wrote:
> Hi,
>
> my name is Katja Sophie Hotz and I am studying Technical Mathematics at the
> Vienna University of Technology.
> I'm in the last year of my master and have specialized in Mathematics in
> Computer Science.
>
> I would like to work on the GSoC project "Univariate polynomials over
> algebraic domains".
> At university I took courses on Linear Algebra (two semesters), Algebra (two
> semesters), Universal Algebra and Algebraic Number Theory,
> so I feel comfortable with algebraic extension fields and polynomial rings.
>
> I also acquired basic programming skills in C++, Java and Matlab at the
> university.
> My experience with Python is limited, but I am eager to learn more.
>
> Until now I submitted two patches.
> The first one is already merged and the second one is still work in
> progress.
>
> I'm about to start writing my application and would appreciate any guidance.
>
> Thanks,
> Katja Sophie
>
> --
> 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 sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy?hl=en-US.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Katja Sophie Hotz]

I just finished a first version of my GSoC application. As it turned out, some of the stuff I wanted to do is already implemented, so I changed the direction of my proposal a bit.
The new title is Faster Algorithms for Polynomials over Algebraic Number Fields. As far as I can see these algorithms would be new to SymPy.

I would be very grateful for any feedback.

Thank you in advance,
Katja Sophie

[Aaron Meurer]

Don't forget to submit this in Melange.

Aaron Meurer

[David Joyner]

I realize that this is not your fault, but the fact that the Sympy documentation [1] lacks 

examples of algebraic numbers will make it more difficult to evaluate the feasibility of

your proposal.

 

[1] http://docs.sympy.org/dev/modules/polys/reference.html#algebraic-number-fields

Thank you in advance,
Katja Sophie

--

[Aaron Meurer]

Algorithms like factor can handle algebraic numbers using the extension flag

In [182]: factor(x**2 + 1, extension=[I])
Out[182]: (x - ⅈ)⋅(x + ⅈ)

In general, algebraic numbers can be slow, because minpoly is slow
(this is being fixed at https://github.com/sympy/sympy/pull/2038). I
think multiple extensions are also slow for other reasons.

Currently, only algebraic numbers are supported, but it would be great
to support algebraic functions (like sqrt(x) instead of sqrt(2)).

Aaron Meurer

[Katja Sophie Hotz]

As far as I know, the modular gcd algorithm and the factorization algorithm from my proposal
can be extended to algebraic function fields, but I don't think there will be enough time to go that far in one summer.

[mario]

It would also be interesting to have a faster factorization algorithm for integer polynomials. Currently the Zassenhaus method is used;

the van Hoeij algorithm is faster. A faster factorization algorithm would be useful e.g. in computing the minimal polynomials;

there are cases in which minpoly stalls in factorizing a polynomial which is factored in Sage very fast.

[Katja Sophie Hotz]

I was unsure how the two algorithms compare, this is why I didn't include the integer polynomial case in my proposal.
But it would be great to also work on this case.