Sage 4.1.1 released
Sage 4.1.1 was released on August 14th, 2009. For the official, comprehensive release note, please refer to sage4.1.1.txt. The following points are some of the foci of this release:
 Improved data conversion between NumPy and Sage
 Solaris support, Solaris specific bug fixes for NTL, zn_poly, Pari/GP, FLINT, MPFR, PolyBoRI, ATLAS
 Upgrade/updates for about 8 standard packages
 Three new optional packages: openopt, GLPK, p_group_cohomology
In this release, 13 people made their first contribution:
 Adam Webb
 Anders Claesson
 Andrew Mathas
 Dag Sverre Seljebotn
 Evan Fosmark
 Jens Rasch
 Nathann Cohen
 Peter McNamara
 Simon Morris
 Steven Hartke
 Taylor Sutton
 Tim Dumol
 Vincent Delecroix
We closed 165 tickets, details of which are available on the Sage trac server. Among these tickets is the longstanding #111, which was closed due to the work of Alex Ghitza and David Loeffler. Thus, ticket #111 is our lowest ticket winner for this release. With the merging of ticket #877, there is a change in the way docstring coverage is counted. Previously, the docstring coverage script also counted functions that are local to other functions. In this manner, the docstring coverage for Sage 4.1 is:
 Overall weighted coverage score: 77.8%
 Total number of functions: 22398
With ticket #877, nested functions or functions local to other functions are no longer counted towards the docstring coverage. This results in a reduced number of functions, hence we have the following statistics for Sage 4.1 as a result of #877:
 Overall weighted coverage score: 78.3%
 Total number of functions: 22210
Using the docstring coverage technique from ticket #877, in Sage 4.1.1 we increased coverage by 0.3%, while adding 120 functions:
 Overall weighted coverage score: 78.6%
 Total number of functions: 22330
Known Issues
The standard package cliquer doesn’t build under some 64bit platforms. There are reports of cliquer failing to compile under 64bit Fedora 10 (see ticket #6746) and 64bit Intel Mac running OS X 10.5 (see ticket #6681). We provide the 64bit binary
 sage4.1.1OSX10.5intel64biti386Darwin.dmg
on the Mac OS X binary download page. However, users should note that the README.txt file in that binary contains a warning about cliquer. In the above binary, the cliquer import statement in sage/graphs/all.py has been commented out like so
#from sage.graphs.cliquer import *
as a workaround to allow Sage to start up. In the meantime, users of 64bit OS X won’t have access to functionalities of the cliquer spkg until ticket #6681 has been resolved.
Here is a summary of main features in this release, categorized under various headings:
Algebra
 Adds method __nonzero__() to abelian groups (Taylor Sutton) #6510 — New method __nonzero__() for the class AbelianGroup_class in sage/groups/abelian_gps/abelian_group.py. This method returns True if the abelian group in question is nontrivial:
sage: E = EllipticCurve([0, 82]) sage: T = E.torsion_subgroup() sage: bool(T) False sage: T.__nonzero__() False
Basic Arithmetic
 Implement real_part() and imag_part() for CDF and CC (Alex Ghitza) #6159 — The name real_part is now an alias to the method real(); similarly, imag_part is now an alias to the method imag().
sage: a = CDF(3, 2) sage: a.real() 3.0 sage: a.real_part() 3.0 sage: a.imag() 2.0 sage: a.imag_part() 2.0 sage: i = ComplexField(100).0 sage: z = 2 + 3*i sage: z.real() 2.0000000000000000000000000000 sage: z.real_part() 2.0000000000000000000000000000 sage: z.imag() 3.0000000000000000000000000000 sage: z.imag_part() 3.0000000000000000000000000000
 Efficient summing using balanced sum (Jason Grout, Mike Hansen) #2737 — New function balanced_sum() in the module sage/misc/misc_c.pyx for summing the elements in a list. In some cases, balanced_sum() is more efficient than the builtin Python sum() function, where the efficiency can range from 26x up to 1410x faster than sum(). The following timing statistics were obtained using the machine sage.math:
sage: R. = QQ["x,y"] sage: L = [x^i for i in xrange(1000)] sage: %time sum(L); CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s Wall time: 0.01 s sage: %time balanced_sum(L); CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s Wall time: 0.00 s sage: %timeit sum(L); 100 loops, best of 3: 8.66 ms per loop sage: %timeit balanced_sum(L); 1000 loops, best of 3: 324 µs per loop sage: sage: L = [[i] for i in xrange(10e4)] sage: %time sum(L, []); CPU times: user 84.61 s, sys: 0.00 s, total: 84.61 s Wall time: 84.61 s sage: %time balanced_sum(L, []); CPU times: user 0.06 s, sys: 0.00 s, total: 0.06 s Wall time: 0.06 s
Calculus
 Wigner 3j, 6j, 9j, ClebschGordan, Racah and Gaunt coefficients (Jens Rasch) #5996 — A collection of functions for exactly calculating Wigner 3j, 6j, 9j, ClebschGordan, Racah as well as Gaunt coefficients. All these functions evaluate to a rational number times the square root of a rational number. These new functions are defined in the module sage/functions/wigner.py. Here are some examples on calculating the Wigner 3j, 6j, 9j symbols:
sage: wigner_3j(2, 6, 4, 0, 0, 0) sqrt(5/143) sage: wigner_3j(0.5, 0.5, 1, 0.5, 0.5, 0) sqrt(1/6) sage: wigner_6j(3,3,3,3,3,3) 1/14 sage: wigner_6j(8,8,8,8,8,8) 12219/965770 sage: wigner_9j(1,1,1, 1,1,1, 1,1,0 ,prec=64) # ==1/18 0.0555555555555555555 sage: wigner_9j(15,15,15, 15,3,15, 15,18,10, prec=1000)*1.0 0.0000778324615309539
The ClebschGordan, Racah and Gaunt coefficients can be computed as follows:
sage: simplify(clebsch_gordan(3/2,1/2,2, 3/2,1/2,2)) 1 sage: clebsch_gordan(1.5,0.5,1, 1.5,0.5,1) 1/2*sqrt(3) sage: racah(3,3,3,3,3,3) 1/14 sage: gaunt(1,0,1,1,0,1) 1/2/sqrt(pi) sage: gaunt(12,15,5,2,3,5) 91/124062*sqrt(36890)/sqrt(pi) sage: gaunt(1000,1000,1200,9,3,12).n(64) 0.00689500421922113448
Combinatorics
 Optimize the words library code (Vincent Delecroix, Sébastien Labbé, Franco Saliola) #6519 — An enhancement of the words library code in sage/combinat/words to improve its efficiency and reorganize the code. The efficiency gain for creating small words can be up to 6x:
# BEFORE sage: %timeit Word() 10000 loops, best of 3: 46.6 µs per loop sage: %timeit Word("abbabaab") 10000 loops, best of 3: 62 µs per loop sage: %timeit Word([0,1,1,0,1,0,0,1]) 10000 loops, best of 3: 59.4 µs per loop # AFTER sage: %timeit Word() 100000 loops, best of 3: 6.85 µs per loop sage: %timeit Word("abbabaab") 100000 loops, best of 3: 11.8 µs per loop sage: %timeit Word([0,1,1,0,1,0,0,1]) 100000 loops, best of 3: 10.6 µs per loop
For the creation of large words, the improvement can be from between 8000x up to 39000x:
# BEFORE sage: t = words.ThueMorseWord() sage: w = list(t[:1000000]) sage: %timeit Word(w) 10 loops, best of 3: 792 ms per loop sage: u = "".join(map(str, list(t[:1000000]))) sage: %timeit Word(u) 10 loops, best of 3: 777 ms per loop sage: %timeit Words("01")(u) 10 loops, best of 3: 748 ms per loop # AFTER sage: t = words.ThueMorseWord() sage: w = list(t[:1000000]) sage: %timeit Word(w) 10000 loops, best of 3: 20.3 µs per loop sage: u = "".join(map(str, list(t[:1000000]))) sage: %timeit Word(u) 10000 loops, best of 3: 21.9 µs per loop sage: %timeit Words("01")(u) 10000 loops, best of 3: 84.3 µs per loop
All of the above timing statistics were obtained using the machine sage.math. Further timing comparisons can be found at the Sage wiki page.
 Improve the speed of Permutation.inverse() (Anders Claesson) #6621 — In some cases, the speed gain is up to 11x. The following timing statistics were obtained using the machine sage.math:
# BEFORE sage: p = Permutation([6, 7, 8, 9, 4, 2, 3, 1, 5]) sage: %timeit p.inverse() 10000 loops, best of 3: 67.1 µs per loop sage: p = Permutation([19, 5, 13, 8, 7, 15, 9, 10, 16, 3, 12, 6, 2, 20, 18, 11, 14, 4, 17, 1]) sage: %timeit p.inverse() 1000 loops, best of 3: 240 µs per loop sage: p = Permutation([14, 17, 1, 24, 16, 34, 19, 9, 20, 18, 36, 5, 22, 2, 27, 40, 37, 15, 3, 35, 10, 25, 21, 8, 13, 26, 12, 32, 23, 38, 11, 4, 6, 39, 31, 28, 29, 7, 30, 33]) sage: %timeit p.inverse() 1000 loops, best of 3: 857 µs per loop # AFTER sage: p = Permutation([6, 7, 8, 9, 4, 2, 3, 1, 5]) sage: %timeit p.inverse() 10000 loops, best of 3: 24.6 µs per loop sage: p = Permutation([19, 5, 13, 8, 7, 15, 9, 10, 16, 3, 12, 6, 2, 20, 18, 11, 14, 4, 17, 1]) sage: %timeit p.inverse() 10000 loops, best of 3: 41.4 µs per loop sage: p = Permutation([14, 17, 1, 24, 16, 34, 19, 9, 20, 18, 36, 5, 22, 2, 27, 40, 37, 15, 3, 35, 10, 25, 21, 8, 13, 26, 12, 32, 23, 38, 11, 4, 6, 39, 31, 28, 29, 7, 30, 33]) sage: %timeit p.inverse() 10000 loops, best of 3: 72.4 µs per loop
 Updating some quirks in sage/combinat/partition.py (Andrew Mathas) #5790 — The functions r_core(), r_quotient(), k_core(), and partition_sign() are now deprecated. These are replaced with core(), quotient(), and sign() respectively. The rewrite of the function Partition() deprecated the argument core_and_quotient. The core and the quotient can be passed as keywords of Partition().
sage: Partition(core_and_quotient=([2,1], [[2,1],[3],[1,1,1]])) /home/mvngu/.sage/temp/sage.math.washington.edu/9221/_home_mvngu__sage_init_sage_0.py:1: DeprecationWarning: "core_and_quotient=(*)" is deprecated. Use "core=[*], quotient=[*]" instead. # * coding: utf8 * [11, 5, 5, 3, 2, 2, 2] sage: Partition(core=[2,1], quotient=[[2,1],[3],[1,1,1]]) [11, 5, 5, 3, 2, 2, 2] sage: Partition([6,3,2,2]).r_quotient(3) /home/mvngu/.sage/temp/sage.math.washington.edu/9221/_home_mvngu__sage_init_sage_0.py:1: DeprecationWarning: r_quotient is deprecated. Please use quotient instead. # * coding: utf8 * [[], [], [2, 1]] sage: Partition([6,3,2,2]).quotient(3) [[], [], [2, 1]] sage: partition_sign([5,1,1,1,1,1]) /home/mvngu/.sage/temp/sage.math.washington.edu/9221/_home_mvngu__sage_init_sage_0.py:1: DeprecationWarning: "partition_sign deprecated. Use Partition(pi).sign() instead # * coding: utf8 * 1 sage: Partition([5,1,1,1,1,1]).sign() 1
Cryptography
 Improve Sbox linear and differences matrices computation (Yann LaigleChapuy) #6454 — Speed up the functions difference_distribution_matrix() and linear_approximation_matrix() of the class SBox in the module sage/crypto/mq/sbox.py. The function linear_approximation_matrix() now uses the Walsh transform. The efficiency of difference_distribution_matrix() can be up to 277x, while that for linear_approximation_matrix() can be up to 132x. The following timing statistics were obtained using the machine sage.math:
# BEFORE sage: S = mq.SR(1,4,4,8).sbox() sage: %time S.difference_distribution_matrix(); CPU times: user 77.73 s, sys: 0.00 s, total: 77.73 s Wall time: 77.73 s sage: %time S.linear_approximation_matrix(); CPU times: user 132.96 s, sys: 0.00 s, total: 132.96 s Wall time: 132.96 s # AFTER sage: S = mq.SR(1,4,4,8).sbox() sage: %time S.difference_distribution_matrix(); CPU times: user 0.28 s, sys: 0.01 s, total: 0.29 s Wall time: 0.28 s sage: %time S.linear_approximation_matrix(); CPU times: user 1.01 s, sys: 0.00 s, total: 1.01 s Wall time: 1.01 s
Elliptic Curves
 Allow the method integral_points() to handle elliptic curves with large ranks (John Cremona) #6381 — A rewrite of the method integral_x_coords_in_interval() in the class EllipticCurve_rational_field belonging to the module sage/schemes/elliptic_curves/ell_rational_field.py. The rewrite allows the method integral_points() to compute the integral points of elliptic curves with large ranks. For example, previously the following code would result in an OverflowError:
sage: D = 6611719866 sage: E = EllipticCurve([0, 0, 0, D^2, 0]) sage: E.integral_points();
 Multiplicationbyn method on elliptic curve formal groups uses the doubleandadd algorithm (Hamish IveyLaw, Tom Boothby) #6407 — Previously, the method EllipticCurveFormalGroup.mult_by_n() was implemented by applying the group law to itself n times. However, when working over a field of characteristic zero, a faster algorithm would be used instead. The linear algorithm is now replaced with the logarithmic doubleandadd algorithm, i.e. the additive version of the standard squareandmultiply algorithm. In some cases, the efficiency gain can range from 3% up to 29%. The following timing statistics were obtained using the machine sage.math:
# BEFORE sage: F = EllipticCurve(GF(101), [1, 1]).formal_group() sage: %time F.mult_by_n(100, 20); CPU times: user 0.98 s, sys: 0.00 s, total: 0.98 s Wall time: 0.98 s sage: F = EllipticCurve("37a").formal_group() sage: %time F.mult_by_n(1000000, 20); CPU times: user 0.38 s, sys: 0.00 s, total: 0.38 s Wall time: 0.38 s sage: %time F.mult_by_n(100000000, 20); CPU times: user 0.55 s, sys: 0.03 s, total: 0.58 s Wall time: 0.58 s # AFTER sage: F = EllipticCurve(GF(101), [1, 1]).formal_group() sage: %time F.mult_by_n(100, 20); CPU times: user 0.96 s, sys: 0.00 s, total: 0.96 s Wall time: 0.95 s sage: F = EllipticCurve("37a").formal_group() sage: %time F.mult_by_n(1000000, 20); CPU times: user 0.44 s, sys: 0.01 s, total: 0.45 s Wall time: 0.45 s sage: %time F.mult_by_n(100000000, 20); CPU times: user 0.40 s, sys: 0.01 s, total: 0.41 s Wall time: 0.41 s
Graphics
 Plotting 3D Bezier paths (Emily Kirkman) #6098 — New function bezier3d() for plotting a 3dimensional Bezier path. Here are some examples for working with this function:
sage: bezier3d([[(0,0,0), (1,0,0), (0,1,0), (0,1,1)]]).show(zoom=1.2)
sage: path = [[(0,0,0),(.5,.1,.2),(.75,3,1),(1,1,0)],[(.5,1,.2),(1,.5,0)],[(.7,.2,.5)]] sage: bezier3d(path, color='green').show(zoom=1.2)
 Passing extra options to show() (Bill Cauchois) #5651 — Extra optional arguments to plotting functions can now be passed on to the function show(). This passing of optional arguments is implemented for the following plotting modules:
 sage/plot/arrow.py
 sage/plot/bar_chart.py
 sage/plot/bezier_path.py
 sage/plot/circle.py
 sage/plot/complex_plot.pyx
 sage/plot/contour_plot.py
 sage/plot/density_plot.py
 sage/plot/disk.py
 sage/plot/line.py
 sage/plot/matrix_plot.py
 sage/plot/plot.py
 sage/plot/plot_field.py
 sage/plot/point.py
 sage/plot/polygon.py
 sage/plot/scatter_plot.py
 sage/plot/text.py
Each of the following examples demonstrates equivalent code to obtain a plot:
sage: arrow((2, 2), (7,1), frame=True) sage: arrow((2, 2), (7,1)).show(frame=True)
sage: bar_chart([2,8,7,3], rgbcolor=(1,0,0), axes=False) sage: bar_chart([2,8,7,3], rgbcolor=(1,0,0)).show(axes=False)
sage: bezier_path([[(0,1),(.5,0),(1,1)]], fontsize=20) sage: bezier_path([[(0,1),(.5,0),(1,1)]]).show(fontsize=20)
sage: complex_plot(lambda z: z, (3, 3), (3, 3), figsize=[5,5]) sage: complex_plot(lambda z: z, (3, 3), (3, 3)).show(figsize=[5,5])
Graph Theory
 Cliquer as a standard package (Nathann Cohen) #6355 — Cliquer is a set of C routines for finding cliques in an arbitrary weighted graph. It uses an exact branchandbound algorithm recently developed by Patric Ostergard and mainly written by Sampo Niskanen. It is published under the GPL license. Here are some examples for working with the new cliquer spkg:
sage: max_clique(graphs.PetersenGraph()) [7, 9] sage: all_max_clique(graphs.PetersenGraph()) [[2, 7], [7, 9], [6, 8], [6, 9], [0, 4], [4, 9], [5, 7], [0, 5], [5, 8], [3, 4], [2, 3], [3, 8], [1, 6], [0, 1], [1, 2]] sage: clique_number(Graph("DJ{")) 4 sage: clique_number(Graph({0:[1,2,3], 1:[2], 3:[0,1]})) 3 sage: list_composition([1,3,'a'], {'a':'b', 1:2, 2:3, 3:4}) [2, 4, 'b']
 Faster algorithm to compute maximum cliques (Nathann Cohen) #5793 — With the inclusion of cliquer as a standard spkg, the following functions can now use the cliquer algorithm:
 Graph.max_clique() — Returns the vertex set of a maximum complete subgraph.
 Graph.cliques_maximum() — Returns a list of all maximum cliques, with each clique represented by a list of vertices. A clique is an induced complete subgraph and a maximal clique is one of maximal order.
 Graph.clique_number() — Returns the size of the largest clique of the graph.
 Graph.cliques_vertex_clique_number() — Returns a list of sizes of the largest maximal cliques containing each vertex. This returns a single value if there is only one input vertex.
 Graph.independent_set() — Returns a maximal independent set, which is a set of vertices which induces an empty subgraph.
These functions already exist in Sage. Cliquer does not bring to Sage any new feature, but a huge efficiency improvement in computing clique numbers. The NetworkX 0.36 algorithm is very slow in its computation of these functions, even though it remains faster than cliquer for the computation of Graph.cliques_vertex_clique_number(). The algorithms in the cliquer spkg scale very well as the number of vertices in a graph increases. Here is a comparison between the implementation of NetworkX 0.36 and cliquer on computing the clique number of a graph. Timing statistics were obtained using the machine sage.math:
sage: g = graphs.RandomGNP(100, 0.4) sage: %time g.clique_number(algorithm="networkx"); CPU times: user 0.64 s, sys: 0.01 s, total: 0.65 s Wall time: 0.65 s sage: %time g.clique_number(algorithm="cliquer"); CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s Wall time: 0.02 s sage: g = graphs.RandomGNP(200, 0.4) sage: %time g.clique_number(algorithm="networkx"); CPU times: user 9.68 s, sys: 0.01 s, total: 9.69 s Wall time: 9.68 s sage: %time g.clique_number(algorithm="cliquer"); CPU times: user 0.09 s, sys: 0.00 s, total: 0.09 s Wall time: 0.09 s sage: g = graphs.RandomGNP(300, 0.4) sage: %time g.clique_number(algorithm="networkx"); CPU times: user 69.98 s, sys: 0.10 s, total: 70.08 s Wall time: 70.09 s sage: %time g.clique_number(algorithm="cliquer"); CPU times: user 0.23 s, sys: 0.00 s, total: 0.23 s Wall time: 0.23 s sage: g = graphs.RandomGNP(400, 0.4) sage: %time g.clique_number(algorithm="networkx"); CPU times: user 299.32 s, sys: 0.29 s, total: 299.61 s Wall time: 299.64 s sage: %time g.clique_number(algorithm="cliquer"); CPU times: user 0.54 s, sys: 0.00 s, total: 0.54 s Wall time: 0.53 s sage: g = graphs.RandomGNP(500, 0.4) sage: %time g.clique_number(algorithm="networkx"); CPU times: user 1178.85 s, sys: 1.30 s, total: 1180.15 s Wall time: 1180.16 s sage: %time g.clique_number(algorithm="cliquer"); CPU times: user 1.09 s, sys: 0.00 s, total: 1.09 s Wall time: 1.09 s
 Support the syntax g.add_edge((u,v), label=l) for C graphs (Robert Miller) #6540 — The following syntax is supported. However, note that the label keyword must be used:
sage: G = Graph() sage: G.add_edge((1,2), label="my label") sage: G.edges() [(1, 2, 'my label')] sage: G = Graph() sage: G.add_edge((1,2), "label") sage: G.edges() [((1, 2), 'label', None)]
 Fast subgraphs by building the graph instead of deleting things (Jason Grout) #6578 — Subgraphs can now be constructed by building a new graph from a number of vertices and edges. This is in contrast to the previous default algorithm where subgraphs were constructed by deleting edges and vertices. In some cases, the efficiency gain of the new subgraph construction implementation can be up to 17x. The following timing statistics were obtained using the machine sage.math:
# BEFORE sage: g = graphs.PathGraph(Integer(10e4)) sage: %time g.subgraph(range(20)); CPU times: user 1.89 s, sys: 0.03 s, total: 1.92 s Wall time: 1.92 s sage: g = graphs.PathGraph(Integer(10e4) * 5) sage: %time g.subgraph(range(20)); CPU times: user 14.92 s, sys: 0.05 s, total: 14.97 s Wall time: 14.97 s sage: g = graphs.PathGraph(Integer(10e5)) sage: %time g.subgraph(range(20)); CPU times: user 47.77 s, sys: 0.29 s, total: 48.06 s Wall time: 48.06 s # AFTER sage: g = graphs.PathGraph(Integer(10e4)) sage: %time g.subgraph(range(20)); CPU times: user 0.27 s, sys: 0.01 s, total: 0.28 s Wall time: 0.28 s sage: g = graphs.PathGraph(Integer(10e4) * 5) sage: %time g.subgraph(range(20)); CPU times: user 1.34 s, sys: 0.03 s, total: 1.37 s Wall time: 1.37 s sage: g = graphs.PathGraph(Integer(10e5)) sage: %time g.subgraph(range(20)); CPU times: user 2.66 s, sys: 0.04 s, total: 2.70 s Wall time: 2.70 s
Interfaces
 Magma interface: make magma_colon_equals() mode work in both command line and notebook (William Stein) #6395 — Exposes the magma_colon_equals() option in the notebook. For example, one can now do the following in the notebook:
sage: magma._preparse_colon_equals = False sage: magma._preparse('a = 5') 'a = 5' sage: magma._preparse_colon_equals = True sage: magma._preparse('a = 5') 'a := 5' sage: magma._preparse('a = 5; b := 7; c =a+b;') 'a := 5; b := 7; c :=a+b;'
 Viewing a Sage object with view(object, viewer=’pdf’) (Nicolas M. Thiéry) #6591 — Typical uses include:
 you prefer your PDF browser to your DVI browser
 you want to view snippets which are not displayed well in DVI viewers or jsMath, e.g. images produced by tikzpicture.
Linear Algebra
 Make NumPy play nice with Sage types (Robert Bradshaw) #5081 — This improves data conversion between NumPy and Sage. For example, one can now do this:
sage: from scipy import stats sage: stats.uniform(0,15).ppf([0.5,0.7]) array([ 7.5, 10.5])
And this:
sage: from scipy import * sage: from pylab import * sage: sample_rate = 1000.0 sage: t = r_[0:0.6:1/sample_rate] sage: N = len(t) sage: s = [sin(2*pi*50*elem) + sin(2*pi*70*elem + (pi/4)) for elem in t] sage: S = fft(s) sage: f = sample_rate*r_[0:(N/2)] / N sage: n = len(f) sage: line(zip(f, abs(S[0:n]) / N))
 Fast slicing of sparse matrices (Jason Grout) #6553 — The efficiency gain for slicing sparse matrices can range from 10x up to 147x. The following timing statistics were obtained using the machine sage.math:
# BEFORE sage: A = random_matrix(ZZ, 100000, density=0.00005, sparse=True) sage: %time A[50000:,:50000]; CPU times: user 298.84 s, sys: 0.05 s, total: 298.89 s Wall time: 298.95 s sage: A = random_matrix(ZZ, 10000, density=0.00005, sparse=True) sage: %time A[5000:,:5000]; CPU times: user 2.50 s, sys: 0.00 s, total: 2.50 s Wall time: 2.50 s # AFTER sage: A = random_matrix(ZZ, 100000, density=0.00005, sparse=True) sage: %time A[50000:,:50000]; CPU times: user 1.91 s, sys: 0.09 s, total: 2.00 s Wall time: 2.02 s sage: A = random_matrix(ZZ, 10000, density=0.00005, sparse=True) sage: %time A[5000:,:5000]; CPU times: user 0.23 s, sys: 0.00 s, total: 0.23 s Wall time: 0.24 s
 Plotting sparse matrices efficiently (Jason Grout) #6554 — Previously, plotting a sparse matrix would convert the matrix to a dense matrix, resulting in the whole process taking increasingly longer time as the dimensions of the matrix increase. Where a matrix is sparse, the matrix plotting function now uses SciPy’s sparse matrix functionalities, which can handle large matrices. In some cases, the performance improvement can range from 380x up to 98000x. The following timing statistics were obtained using the machine mod.math:
# BEFORE sage: A = random_matrix(ZZ, 5000, density=0.00001, sparse=True) sage: %time matrix_plot(A, marker=','); CPU times: user 60.25 s, sys: 0.69 s, total: 60.94 s Wall time: 60.94 s sage: A = random_matrix(ZZ, 10000, density=0.00001, sparse=True) sage: %time matrix_plot(A, marker=','); CPU times: user 241.31 s, sys: 3.03 s, total: 244.34 s Wall time: 244.35 s sage: A = random_matrix(ZZ, 15000, density=0.00001, sparse=True) sage: %time matrix_plot(A, marker=','); CPU times: user 544.02 s, sys: 6.85 s, total: 550.87 s Wall time: 550.86 s sage: A = random_matrix(ZZ, 20000, density=0.00001, sparse=True) sage: %time matrix_plot(A, marker=','); CPU times: user 972.85 s, sys: 13.36 s, total: 986.21 s Wall time: 986.21 s # AFTER sage: A = random_matrix(ZZ, 5000, density=0.00001, sparse=True) sage: %time matrix_plot(A, marker=','); CPU times: user 0.05 s, sys: 0.04 s, total: 0.09 s Wall time: 0.16 s sage: A = random_matrix(ZZ, 10000, density=0.00001, sparse=True) sage: %time matrix_plot(A, marker=','); CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s Wall time: 0.01 s sage: A = random_matrix(ZZ, 15000, density=0.00001, sparse=True) sage: %time matrix_plot(A, marker=','); CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s Wall time: 0.01 s sage: A = random_matrix(ZZ, 20000, density=0.00001, sparse=True) sage: %time matrix_plot(A, marker=','); CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s Wall time: 0.01 s
In Sage 4.1, the following would quickly consume gigabytes of RAM on a system and may result in a MemoryError:
sage: A = random_matrix(ZZ, 100000, density=0.00001, sparse=True) sage: %time matrix_plot(A, marker=','); CPU times: user 0.63 s, sys: 0.01 s, total: 0.64 s Wall time: 0.63 s sage: A = random_matrix(ZZ, 1000000, density=0.00001, sparse=True) sage: %time matrix_plot(A, marker=','); CPU times: user 1933.41 s, sys: 2.97 s, total: 1936.38 s Wall time: 1937.31 s
 Elementwise (Hadamard) product of matrices (Rob Beezer) #6301 — Given matrices A and B of the same size, C = A.elementwise_product(B) creates the new matrix C, of the same size, with entries given by C[i,j] = A[i,j] * B[i,j]. The multiplication occurs in a ring defined by Sage’s coercion model, as appropriate for the base rings of A and B (or an error is raised if there is no sensible common ring). In particular, if A and B are defined over a noncommutative ring, the operation is also noncommutative. The implementation is different for dense matrices versus sparse matrices, but there are probably further optimizations available for specific rings. This operation is often called the Hadamard product. Here is an example on using elementwise matrix product:
sage: G = matrix(GF(3), 2, [0,1,2,2]) sage: H = matrix(ZZ, 2, [1,2,3,4]) sage: J = G.elementwise_product(H); J [0 2] [0 2] sage: J.parent() Full MatrixSpace of 2 by 2 dense matrices over Finite Field of size 3
Modular Forms
 Efficient implementation of index for Gamma(N) (Simon Morris) #6606 — The new implementation provides massive speedup for the function Gamma(N). The following statistics were obtained using the machine mod.math:
# BEFORE sage: %time [Gamma(n).index() for n in [1..19]]; CPU times: user 14369.53 s, sys: 75.18 s, total: 14444.71 s Wall time: 14445.22 s sage: %time Gamma(32041).index(); # hangs for hours # AFTER sage: %time [Gamma(n).index() for n in [1..19]]; CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s Wall time: 0.00 s sage: timeit("[Gamma(n).index() for n in [1..19]]") 125 loops, best of 3: 2.27 ms per loop sage: %time Gamma(32041).index(); CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s sage: %timeit Gamma(32041).index() 10000 loops, best of 3: 110 µs per loop
 Weight 1 Eisenstein series (David Loeffler) #6071 — Add support for computing weight 1 Eisenstein series. Here’s an example:
sage: M = ModularForms(DirichletGroup(13).0, 1) sage: M.eisenstein_series() [ 1/13*zeta12^3 + 6/13*zeta12^2 + 4/13*zeta12 + 2/13 + q + (zeta12 + 1)*q^2 + zeta12^2*q^3 + (zeta12^2 + zeta12 + 1)*q^4 + (zeta12^3 + 1)*q^5 + O(q^6) ]
 Efficient calculation of Jacobi sums (David Loeffler) #6534 — For small primes, calculating Jacobi sums using the definition directly can result in an efficiency improvement of up to 624x. The following timing statistics were obtained using the machine mod.math:
# BEFORE sage: chi = DirichletGroup(67).0 sage: psi = chi**3 sage: time chi.jacobi_sum(psi); CPU times: user 6.24 s, sys: 0.00 s, total: 6.24 s Wall time: 6.24 s # AFTER sage: chi = DirichletGroup(67).0 sage: psi = chi**3 sage: time chi.jacobi_sum(psi); CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s Wall time: 0.01 s
There is also support for computing a Jacobi sum with values in a finite field:
sage: g = DirichletGroup(17, GF(9,'a')).0 sage: g.jacobi_sum(g**2) 2*a
Notebook
 Display docstrings in the notebook using HTML and jsMath (Tom Boothby, Evan Fosmark, John Palmieri, Mitesh Patel) #5653 — When viewing docstrings using the notebook, these are presented using HTML and jsMath. For example, if one does any of the following
identity_matrix([TAB] identity_matrix?[SHIFTRETURN] identity_matrix?[TAB]
then the docstring for the function identity_matrix() would be presented as in this figure:
Number Theory
 Intersection of ideals in a number field (David Loeffler) #6457 — New function intersection() of the class NumberFieldIdeal in the module sage/rings/number_field/number_field_ideal.py for computing the ideals in a number field. Here are some examples on using intersection():
sage: K.<a> = QuadraticField(11) sage: p = K.ideal((a + 1)/2); q = K.ideal((a + 3)/2) sage: p.intersection(q) == q.intersection(p) == K.ideal(a2) True sage: # An example with nonprincipal ideals sage: L.<a> = NumberField(x^3  7) sage: p = L.ideal(a^2 + a + 1, 2) sage: q = L.ideal(a+1) sage: p.intersection(q) == L.ideal(8, 2*a + 2) True sage: # A relative example sage: L.<a,b> = NumberField([x^2 + 11, x^2  5]) sage: A = L.ideal([15, (3/2*b + 7/2)*a  8]) sage: B = L.ideal([6, (1/2*b + 1)*a  b  5/2]) sage: A.intersection(B) == L.ideal(1/2*a  3/2*b  1) True
 Computing Heegner points (Robert Bradshaw) #6045 — Adds a Heegner point method to elliptic curves over . The new method is heegner_point() which can be found in the class EllipticCurve_rational_field of the module sage/schemes/elliptic_curves/ell_rational_field.py. Here are some examples on using heegner_point():
sage: E = EllipticCurve('37a') sage: E.heegner_discriminants_list(10) [7, 11, 40, 47, 67, 71, 83, 84, 95, 104] sage: E.heegner_point(7) (0 : 0 : 1) sage: P = E.heegner_point(40); P (a : a + 1 : 1) sage: P = E.heegner_point(47); P (a : a^4  a : 1) sage: P[0].parent() Number Field in a with defining polynomial x^5  x^4 + x^3 + x^2  2*x + 1 sage: # Working out the details manually sage: P = E.heegner_point(47, prec=200) sage: f = algdep(P[0], 5); f x^5  x^4 + x^3 + x^2  2*x + 1 sage: f.discriminant().factor() 47^2
 Support primes_of_degree_one() for relative extensions (David Loeffler) #6396 — For example, one can now do this:
sage: N.<a,b> = NumberField([x^2 + 1, x^2  5]) sage: ids = N.primes_of_degree_one_list(10); ids [Fractional ideal (2*a + 1/2*b  1/2), Fractional ideal ((1/2*b  1/2)*a  b), Fractional ideal (b*a + 1/2*b + 3/2), Fractional ideal ((1/2*b  3/2)*a + b  1), Fractional ideal ((b + 1)*a + b), Fractional ideal (3*a + 1/2*b  1/2), Fractional ideal ((1/2*b  1/2)*a + 3/2*b  1/2), Fractional ideal ((1/2*b  5/2)*a  b + 1), Fractional ideal (2*a  3/2*b  1/2), Fractional ideal (3*a + 1/2*b + 5/2)] sage: [x.absolute_norm() for x in ids] [29, 41, 61, 89, 101, 109, 149, 181, 229, 241] sage: ids[9] == N.ideal(3*a + 1/2*b + 5/2) True
 Inverse modulo an ideal in a relative number field (David Loeffler) #6458 — Support for computing the inverse modulo an ideal in the ring of integers of a relative field. Here’s an example:
sage: K.<a,b> = NumberField([x^2 + 1, x^2  3]) sage: I = K.ideal(17*b  3*a) sage: x = I.integral_basis(); x [438, b*a + 309, 219*a  219*b, 156*a  154*b] sage: V, _, phi = K.absolute_vector_space() sage: V.span([phi(u) for u in x], ZZ) == I.free_module() True
Numerical
 Further NumPy type conversions (Robert Bradshaw, Jason Grout) #6506 — Improved handling of , , and between NumPy and Sage. Here are some examples:
sage: import numpy sage: numpy.array([1.0, 2.5j]) array([ 1.+0.j , 0.+2.5j]) sage: numpy.array([1.0, 2.5j]).dtype dtype('complex128') sage: numpy.array([1.000000000000000000000000000000000000j]).dtype dtype('object') sage: numpy.array([1, 2, 3]) array([1, 2, 3]) sage: numpy.array([1, 2, 3]).dtype dtype('int64') sage: numpy.array(2**40).dtype dtype('int64') sage: numpy.array(2**400).dtype dtype('object') sage: numpy.array([1,2,3,0.1]).dtype dtype('float64') sage: numpy.array(QQ(2**40)).dtype dtype('int64') sage: numpy.array(QQ(2**400)).dtype dtype('object') sage: numpy.array([1, 1/2, 3/4]) array([ 1. , 0.5 , 0.75])
Packages
 Update the ATLAS spkg to version 3.8.3.p7 (David Kirkby, Minh Van Nguyen) #6558 #6738 — This adds support for building ATLAS under Solaris on a Sun SPARC processor.
 Update the NTL spkg to version 5.4.2.p9 (David Kirkby) #6380 — This adds support for building NTL under Solaris on a Sun SPARC processor.
 Update the zn_poly spkg to version 0.9.p1 (David Kirkby) #6443 — This adds support for building zn_poly under Solaris on a Sun SPARC processor.
 Update the Pari/GP spkg to version 2.3.3.p1 (David Kirkby) #6445 — This adds support for building Pari under Solaris on a Sun SPARC processor.
 Update the FLINT spkg to version 1.3.0.p2 (David Kirkby) #6451 — This fixes a Solaris specific bug in FLINT.
 Update the MPFR spkg to version 2.4.1.p0 (Paul Zimmermann, David Kirkby) #6453 — This fixes a number of test failures under Solaris on a Sun SPARC processor.
 Update the PolyBoRi spkg to version 0.5rc.p9 (David Kirkby) #6528 — This fixes a Solaris specific bug in compiling PolyBoRi with the Sun compiler.
 Upgrade tinyMCE to version 3.2.4.1 upstream release (Jason Grout) #6143 — This version of tinyMCE has many fixes for Safari and a greatly improved pastefromword functionality.
 Upgrade Cython to version 0.11.2.1 latest upstream release (Robert Bradshaw) #6438.
 Update the NumPy spkg to version 1.3.0.p1 (William Stein) #6493 — This fixes a bug in compiling NumPy under 64bit OS X.
 Upgrade Singular to version singular310220090620.p0 (David Kirkby) #6563 — This fixes a Solaris specific bug when compiling Singular under Solaris on a Sun SPARC processor.
 New optional spkg GLPK version 4.38 (Nathann Cohen) #6602 — GLPK is a linear program solver that can also solve mixed integer programs.
 New optional spkg OpenOpt version 0.24 (William Stein) #6302 — OpenOpt is a numerical optimization package with various solvers.
 New optional package p_group_cohomology version 1.0.2 (Simon A. King, David J. Green) #6491 — The package p_group_cohomology can compute the cohomology ring of a group with coefficients in a finite field of order p. Its features include:
 Compute the cohomology ring with coefficients in for any finite group, in terms of a minimal generating set and a minimal set of algebraic relations. We use Benson’s criterion to prove the completeness of the ring structure.
 Compute depth, dimension, Poincare series and invariants of the cohomology rings.
 Compute the nil radical.
 Construct induced homomorphisms.
 The package includes a list of cohomology rings for all groups of order 64.
 With the package, the cohomology for all groups of order 128 and for the Sylow 2subgroup of the third Conway group (order 1024) was computed for the first time. The result of these and many other computations (e.g., all but 6 groups of order 243) is accessible in a repository on sage.math.
Here some examples. Data that are included with the package:
sage: from pGroupCohomology import CohomologyRing sage: H = CohomologyRing(64,132) # this is included in the package, hence, the ring structure is already there sage: print H Cohomology ring of Small Group number 132 of order 64 with coefficients in GF(2) Computation complete Minimal list of generators: [a_2_4, a 2Cochain in H^*(SmallGroup(64,132); GF(2)), c_2_5, a 2Cochain in H^*(SmallGroup(64,132); GF(2)), c_4_12, a 4Cochain in H^*(SmallGroup(64,132); GF(2)), a_1_0, a 1Cochain in H^*(SmallGroup(64,132); GF(2)), a_1_1, a 1Cochain in H^*(SmallGroup(64,132); GF(2)), b_1_2, a 1Cochain in H^*(SmallGroup(64,132); GF(2))] Minimal list of algebraic relations: [a_1_0*a_1_1, a_1_0*b_1_2, a_1_1^3+a_1_0^3, a_2_4*a_1_0, a_1_1^2*b_1_2^2+a_2_4*a_1_1*b_1_2+a_2_4^2+c_2_5*a_1_1^2] sage: H.depth() 2 sage: H.a_invariants() [Infinity, Infinity, 3, 3] sage: H.poincare_series() (t^2  t  1)/(t^6  2*t^5 + t^4  t^2 + 2*t  1) sage: H.nil_radical() a_1_0, a_1_1, a_2_4
Data from the repository on sage.math:
sage: H = CohomologyRing(128,562) # if there is internet connection, the ring data are downloaded behind the scenes sage: len(H.gens()) 35 sage: len(H.rels()) 486 sage: H.depth() 1 sage: H.a_invariants() [Infinity, 4, 3, 3] sage: H.poincare_series() (t^14  2*t^13 + 2*t^12  t^11  t^10 + t^9  2*t^8 + 2*t^7  2*t^6 + 2*t^5  2*t^4 + t^3  t^2  1)/(t^17  3*t^16 + 4*t^15  4*t^14 + 4*t^13  4*t^12 + 4*t^11  4*t^10 + 4*t^9  4*t^8 + 4*t^7  4*t^6 + 4*t^5  4*t^4 + 4*t^3  4*t^2 + 3*t  1)
Some computation from scratch, involving different ring presentations and induced maps:
sage: tmp_root = tmp_filename() sage: CohomologyRing.set_user_db(tmp_root) sage: H0 = CohomologyRing.user_db(8,3,websource=False) sage: print H0 Cohomology ring of Dihedral group of order 8 with coefficients in GF(2) Computed up to degree 0 Minimal list of generators: [] Minimal list of algebraic relations: [] sage: H0.make() sage: print H0 Cohomology ring of Dihedral group of order 8 with coefficients in GF(2) Computation complete Minimal list of generators: [c_2_2, a 2Cochain in H^*(D8; GF(2)), b_1_0, a 1Cochain in H^*(D8; GF(2)), b_1_1, a 1Cochain in H^*(D8; GF(2))] Minimal list of algebraic relations: [b_1_0*b_1_1] sage: G = gap('DihedralGroup(8)') sage: H1 = CohomologyRing.user_db(G,GroupName='GapD8',websource=False) sage: H1.make() sage: print H1 # the ring presentation is different ... Cohomology ring of GapD8 with coefficients in GF(2) Computation complete Minimal list of generators: [c_2_2, a 2Cochain in H^*(GapD8; GF(2)), b_1_0, a 1Cochain in H^*(GapD8; GF(2)), b_1_1, a 1Cochain in H^*(GapD8; GF(2))] Minimal list of algebraic relations: [b_1_1^2+b_1_0*b_1_1] sage: phi = G.IsomorphismGroups(H0.group()) sage: phi_star = H0.hom(phi,H1) sage: phi_star_inv = phi_star^(1) # ... but the rings are isomorphic sage: [X==phi_star_inv(phi_star(X)) for X in H0.gens()] [True, True, True, True] sage: [X==phi_star(phi_star_inv(X)) for X in H1.gens()] [True, True, True, True]
An example with an odd prime:
sage: H = CohomologyRing(81,8) # this needs to be computed from scratch sage: H.make() sage: H.gens() [1, a_2_1, a 2Cochain in H^*(SmallGroup(81,8); GF(3)), a_2_2, a 2Cochain in H^*(SmallGroup(81,8); GF(3)), b_2_0, a 2Cochain in H^*(SmallGroup(81,8); GF(3)), a_4_1, a 4Cochain in H^*(SmallGroup(81,8); GF(3)), b_4_2, a 4Cochain in H^*(SmallGroup(81,8); GF(3)), b_6_3, a 6Cochain in H^*(SmallGroup(81,8); GF(3)), c_6_4, a 6Cochain in H^*(SmallGroup(81,8); GF(3)), a_1_0, a 1Cochain in H^*(SmallGroup(81,8); GF(3)), a_1_1, a 1Cochain in H^*(SmallGroup(81,8); GF(3)), a_3_2, a 3Cochain in H^*(SmallGroup(81,8); GF(3)), a_5_2, a 5Cochain in H^*(SmallGroup(81,8); GF(3)), a_5_3, a 5Cochain in H^*(SmallGroup(81,8); GF(3)), a_7_5, a 7Cochain in H^*(SmallGroup(81,8); GF(3))] sage: len(H.rels()) 59 sage: H.depth() 1 sage: H.a_invariants() [Infinity, 3, 2] sage: H.poincare_series() (t^4  t^3 + t^2 + 1)/(t^6  2*t^5 + 2*t^4  2*t^3 + 2*t^2  2*t + 1) sage: H.nil_radical() a_1_0, a_1_1, a_2_1, a_2_2, a_3_2, a_4_1, a_5_2, a_5_3, b_2_0*b_4_2, a_7_5, b_2_0*b_6_3, b_6_3^2+b_4_2^3
Rob Beezer, Nathann Cohen, John Cremona, Simon King, Sébastien Labbé, and Jens Rasch contributed to writing this release tour. A big thank you to all the Sage bug report/patch authors who made my life as a release tour author easier through your comprehensive and concise documentation. There are too many to list here; you know who you are. A release tour can also be found on the Sage wiki.

7 October 2010 at 8:42 amCompile Sage 4.1 in 64bit mode on OS X 10.5.8 « mvngu