sympy/sympy — pull request #2468 by katjasophie (2013-09-20 08:26:49+00:00)
Title: Factorization of polynomials over algebraic number fields

This is the third and last part of my GSoC project. It implements an improved algorithm for factorization of multivariate polynomials over algebraic number fields.

If the algebraic field is of small degree, the currently used algorithm by Trager will sometimes still be faster:
```
In [3]: A = AlgebraicField(QQ, sqrt(2))
In [4]: R, x, y = ring('x, y', A)
In [5]: f1, f2 = x + y, x**2 + sqrt(2)*y
In [6]: f = f1*f2

In [7]: %timeit efactor(f)
10 loops, best of 3: 64 ms per loop

In [8]: %timeit f.factor_list()
10 loops, best of 3: 35.6 ms per loop
```

But if the degree of the extension is higher, the new algorithm is clearly the better choice:
```
In [12]: A = AlgebraicField(QQ, 2**(S(1)/5))
In [13]: R, x, y, z = ring('x, y, z', A)
In [14]: f1, f2 = x - y, x**2*y + 2**(S(1)/5)*y**2*z
In [15]: f = f1*f2

In [16]: %timeit efactor(f)
10 loops, best of 3: 105 ms per loop

In [17]: %timeit f.factor_list()
1 loops, best of 3: 873 ms per loop

In [18]: A = AlgebraicField(QQ, sqrt(2), 3**(S(1)/3))
In [19]: R, x, y, z = ring('x, y, z', A)
In [20]: f1, f2 = x**2 + 2*y + sqrt(2), 3**(S(1)/3)*x - z
In [21]: f = f1*f2

In [22]: %timeit efactor(f)
1 loops, best of 3: 647 ms per loop

In [23]: %timeit f.factor_list()
1 loops, best of 3: 99 s per loop
```

Most of the commits are in the polys module. The two commits 40883b2affb563b940d6c26ff74febff4b4e960b and 144038e456d2379ee8bc778174de3c2588a31f8b make a few modifications to the rref code in matrix.py.