Implement combinatorial derivative, etc. for CycleIndexSeries
Add doctests for _lps_* methods
#10255 Improve karatsuba multiplication.
Improved Karatsuba: cosmetic changes to docstrings and comments
errata, improve random tests
Merge branch 'develop' into cis/deriv
Merge remote-tracking branch 'origin/develop' into cis/deriv
Redesign patch to eliminate _lps_* methods and bad dependencies
Move log and exp series code to generating_series.py
Trac 13379: splitting field function for polynomials over finite fields
Trac #14824: Frobenius endomorphism over padics
Merge branch 'develop' into ticket/14824

Conflicts:
	src/module_list.py
	src/sage/rings/padics/padic_generic.py
document "map" flag of FiniteField.extension()
Increase precision if needed in E.pari_curve()
trac 14971: Add LaTeX rendering for Farey symbols.
Improved Karatsuba: more thorough tests
Trac #10255: Correct karatsuba multiplication of univariate polynomials for different degree polynomials

In the generic implementation of univariate polynomials over exact
rings, plain karatsuba is used.

However, for different degree polynomials, the karatsuba code makes more
products and additions than the classical multiplication code. Moreover,
for equally sized polynomials, the degree in which karatsuba starts to
be better than plain multiplication looks too high for me.

See attachments comparison_product_50_400.png and
comparison_addition_50_400.png for the number of operations multiplying
degree 50 and 400 polynomials, in yellow, the number of operations using
_mul_generic, in red using current _mul_karatsuba as of 4.6.1 and in
blue with the patch proposed.

{{{
sage: K=QQ[I][x]
sage: f=K.random_element(1500)
sage: g=K.random_element(1500)
sage: %time _ = f._mul_generic(g)
CPU times: user 6.03 s, sys: 0.08 s, total: 6.11 s
Wall time: 6.43 s
sage: %time _ = f._mul_karatsuba(g)
CPU times: user 6.95 s, sys: 0.06 s, total: 7.01 s
Wall time: 7.76 s
}}}

See comment:13 for some benchmarks

Apply: trac_10255_karatsuba_improbement.patch

URL: http://trac.sagemath.org/10255
Reported by: lftabera
Ticket author(s): Luis Felipe Tabera Alonso, Marc Mezzarobba
Reviewer(s): Marc Mezzarobba, Luis Felipe Tabera Alonso
Trac #13163: E.minimal_model() crashes with large coefficients.

This code

{{{
E=EllipticCurve([4382696457564794691603442338788106497, 28, 3992,
16777216, 298])
E.minimal_model()
}}}

Spits out this error:

{{{
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_23.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8
-*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("RT1FbGxpcH
RpY0N1cnZlKFs0MzgyNjk2NDU3NTY0Nzk0NjkxNjAzNDQyMzM4Nzg4MTA2NDk3LCAyOCwgMz
k5MiwgMTY3NzcyMTYsIDI5OF0pCkUubWluaW1hbF9tb2RlbCgp"),globals())+"\\n");
execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>

  File "/tmp/tmpQWTtgb/___code___.py", line 4, in <module>
    exec compile(u'E.minimal_model()
  File "", line 1, in <module>

  File "/sagenb/sage_install/sage-5.0-boxen-
x86_64-Linux/local/lib/python2.7/site-
packages/sage/schemes/elliptic_curves/ell_rational_field.py", line 2552,
in minimal_model
    F = self.pari_mincurve()
  File "/sagenb/sage_install/sage-5.0-boxen-
x86_64-Linux/local/lib/python2.7/site-
packages/sage/schemes/elliptic_curves/ell_rational_field.py", line 713,
in pari_mincurve
    e = self.pari_curve(prec)
  File "/sagenb/sage_install/sage-5.0-boxen-
x86_64-Linux/local/lib/python2.7/site-
packages/sage/schemes/elliptic_curves/ell_rational_field.py", line 664,
in pari_curve
    self._pari_curve[prec] =
pari(list(self.a_invariants())).ellinit(precision=prec)
  File "gen.pyx", line 10416, in sage.libs.pari.gen._pari_trap
(sage/libs/pari/gen.c:49843)
sage.libs.pari.gen.PariError: precision too low (10)
}}}

It looks like the precision needs to be increased when such a large
curve is fed to PARI's minimal model algorithm.

URL: http://trac.sagemath.org/13163
Reported by: weigandt
Ticket author(s): Jeroen Demeyer
Reviewer(s): John Cremona
Trac #13379: Add a splitting field function for polynomials over a finite field

The purpose of this patch is to add the splitting_field() function to
polynomial elements with coefficients in a finite field.

See also #2217, the number field analogue of this ticket.

URL: http://trac.sagemath.org/13379
Reported by: abrochard
Ticket author(s): Adrien Brochard, Peter Bruin
Reviewer(s): Jeroen Demeyer
Trac #14846: CycleIndexSeries derivative, integral, exponential methods are not combinatorial

The ''CycleIndexSeries'' class inherits ''derivative'', ''integral'',
and ''exponential'' methods from its parent class ''LazyPowerSeries''.
However, these operations (which are perfectly reasonable at the
''LazyPowerSeries'' level) are not combinatorially natural. In fact,
there is a differentiation operator on cycle index series, but it's
something entirely different, and anti-differentiation is in general
impossible!

In addition to being confusing, this discrepancy has the potential to
hinder work using the ''CycleIndexSeries'' class. The combinatorial
operation of cycle index differentiation is very useful in enumerative
work.

All that said, the existing ''exponential'' and ''derivative'' methods
are used for algebraic magic tricks in some of the existing code, so
it's important not to take it away altogether.

The attached patch makes the following changes:

* Adds ''_lps_derivative'', ''_lps_integral'', and ''_lps_exponential''
methods to ''CycleIndexSeries'' which call up using ''super''.

* Refactors the internal code which previously used ''exponential'' and
''derivative'' to use ''_lps_exponential'' and ''_lps_derivative''
instead.

* Implements a new ''derivative'' method which computes the
combinatorial derivative of a cycle index series.

* Implements a new ''pointing'' method which implements a related
combinatorial operation.

* Implements a new ''integral'' method which raises a
''NotImplementedError'' to prevent any user confusion (since, as
explained in the docstring, there may be infinitely many very distinct
cycle indices with a given derivative).

* Implements a new ''exponential'' method which returns the composition
E(self) for E the cycle index series of ''SetSpecies''.

* Implements a new ''logarithm'' method which returns the composition
Ω(self) for Ω the cycle index series implemented in
''CombinatorialLogarithmSeries''.

Docstrings and doctests are included for everything but the _lps_*
methods, which just call up to ``super``. I'm not sure what a doctest
for these would even look like, but I'm open to suggestions.

URL: http://trac.sagemath.org/14846
Reported by: agd
Ticket author(s): Andrew Gainer-Dewar
Reviewer(s): Martin Rubey