16901
Comment: Summarize #5996
|
27705
Python syntax highlighting
|
Deletions are marked like this. | Additions are marked like this. |
Line 108: | Line 108: |
* FIXME: summarize [[http://trac.sagemath.org/sage_trac/ticket/6519|#6519]]. Many BEFORE-AFTER examples are available a the bottom of [[http://wiki.sagemath.org/WordDesign|WordDesign]] page. Those could be copy and pasted here. * FIXME: summarize [[http://trac.sagemath.org/sage_trac/ticket/6621|#6621]] * FIXME: summarize [[http://trac.sagemath.org/sage_trac/ticket/5790|#5790]] |
* Optimize the words library code (Vincent Delecroix, Sébastien Labbé, Franco Saliola) [[http://trac.sagemath.org/sage_trac/ticket/6519|#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: {{{#!python numbers=off # 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: {{{#!python numbers=off # 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 [[http://wiki.sagemath.org/WordDesign|wiki page]]. * Improve the speed of `Permutation.inverse()` (Anders Claesson) [[http://trac.sagemath.org/sage_trac/ticket/6621|#6621]] --- In some cases, the speed gain is up to 11x. The following timing statistics were obtained using the machine sage.math: {{{#!python numbers=off # 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) [[http://trac.sagemath.org/sage_trac/ticket/5790|#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()`. {{{#!python numbers=off 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: utf-8 -*- [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: utf-8 -*- [[], [], [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: utf-8 -*- 1 sage: Partition([5,1,1,1,1,1]).sign() 1 }}} |
Line 120: | Line 216: |
* FIXME: summarize [[http://trac.sagemath.org/sage_trac/ticket/6454|#6454]] == Documentation == * FIXME: summarize [[http://trac.sagemath.org/sage_trac/ticket/4460|#4460]] |
* Improve S-box linear and differences matrices computation (Yann Laigle-Chapuy) [[http://trac.sagemath.org/sage_trac/ticket/6454|#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: {{{#!python numbers=off # 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 }}} |
Line 132: | Line 244: |
* [[http://trac.sagemath.org/sage_trac/ticket/6381|#6381]] (bug in integral_points when rank is large): The function integral_x_coords_in_interval() for finding all integral points on an elliptic curve defined over the rationals whose x-coordinate lies in an interval is now more efficient when the interval is large. * FIXME: summarize [[http://trac.sagemath.org/sage_trac/ticket/6407|#6407]] |
* Allow the method `integral_points()` to handle elliptic curves with large ranks (John Cremona) [[http://trac.sagemath.org/sage_trac/ticket/6381|#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`: {{{#!python numbers=off sage: D = 6611719866 sage: E = EllipticCurve([0, 0, 0, -D^2, 0]) sage: E.integral_points(); }}} * Multiplication-by-n method on elliptic curve formal groups uses the double-and-add algorithm (Hamish Ivey-Law, Tom Boothby) [[http://trac.sagemath.org/sage_trac/ticket/6407|#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 double-and-add algorithm, i.e. the additive version of the standard square-and-multiply 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: {{{#!python numbers=off # 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 }}} |
Line 154: | Line 300: |
* Inclusion of Cliquer as a standard package (Trac[[http://trac.sagemath.org/sage_trac/ticket/6355|#6355]]) [[http://users.tkk.fi/pat/cliquer.html|Cliquer]] is a set of C routines for finding cliques in an arbitrary weighted graph. It uses an exact branch-and-bound algorithm recently developed by Patric Ostergard and mainly written by Sampo Niskanen. It is published under the GPL license. * FIXME: summarize [[http://trac.sagemath.org/sage_trac/ticket/6540|#6540]] * FIXME: summarize [[http://trac.sagemath.org/sage_trac/ticket/6552|#6552]] * FIXME: summarize [[http://trac.sagemath.org/sage_trac/ticket/6578|#6578]] * New algorithm for all Graph functions related to the computation of maximum Cliques (Trac [[http://trac.sagemath.org/sage_trac/ticket/5793|#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 the 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. (Returns a single value if 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 existed in Sage : Cliquer does not bring to SAGE any new feature, but a huge improvement of its efficiency in the computation of clique number. The previous NetworkX algorithm was very slow in its computations of these functions, even though it remains faster than Cliquer for the computation of Graph.cliques_vertex_clique_number(). Here is what happens when comparing Cliquer to NetworkX {{{ sage: g=graphs.RandomGNP(200,.4) sage: time g.clique_number(algorithm="networkx") CPU times: user 14.63 s, sys: 0.04 s, total: 14.68 s Wall time: 14.68 s 9 sage: time g.clique_number(algorithm="cliquer") CPU times: user 0.11 s, sys: 0.00 s, total: 0.11 s Wall time: 0.11 s 9 }}} |
* Cliquer as a standard package (Nathann Cohen) [[http://trac.sagemath.org/sage_trac/ticket/6355|#6355]] --- [[http://users.tkk.fi/pat/cliquer.html|Cliquer]] is a set of C routines for finding cliques in an arbitrary weighted graph. It uses an exact branch-and-bound 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: {{{#!python numbers=off 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) [[http://trac.sagemath.org/sage_trac/ticket/5793|#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 the 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: {{{#!python numbers=off 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) [[http://trac.sagemath.org/sage_trac/ticket/6540|#6540]] --- The following syntax is supported. However, note that the `label` keyword must be used: {{{#!python numbers=off 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) [[http://trac.sagemath.org/sage_trac/ticket/6578|#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 contructed 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: {{{#!python numbers=off # 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 }}} |
Sage 4.1.1 Release Tour
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 non-trivial:
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 built-in 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.<x,y> = 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, Clebsch-Gordan, Racah and Gaunt coefficients (Jens Rasch) #5996 --- A collection of functions for exactly calculating Wigner `3j`, `6j`, `9j`, Clebsch-Gordan, 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:
The Clebsch-Gordan, Racah and Gaunt coefficients can be computed as follows: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
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:
For the creation of large words, the improvement can be from between 8000x up to 39000x:# 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
# 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: utf-8 -*- [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: utf-8 -*- [[], [], [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: utf-8 -*- 1 sage: Partition([5,1,1,1,1,1]).sign() 1
Cryptography
Improve S-box linear and differences matrices computation (Yann Laigle-Chapuy) #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();
Multiplication-by-n method on elliptic curve formal groups uses the double-and-add algorithm (Hamish Ivey-Law, 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 double-and-add algorithm, i.e. the additive version of the standard square-and-multiply 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
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 branch-and-bound 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 the 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 contructed 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
Linear Algebra
FIXME: summarize #5081
FIXME: summarize #6553
FIXME: summarize #6554
Elementwise (Hadamard) product of matrices (Rob Beezer) (Trac #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, then 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 call the Hadamard 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) sage: J [0 2] [0 2] sage: J.parent() Full MatrixSpace of 2 by 2 dense matrices over Finite Field of size
Modular Forms
Notebook
FIXME: summarize #5653
Number Theory
#6457 (Intersection of ideals in a number field)
Intersection of ideals in number fields is now implemented.
Numerical
Packages
FIXME: summarize #6558
FIXME: summarize #6380
FIXME: summarize #6443
FIXME: summarize #6445
FIXME: summarize #6451
FIXME: summarize #6453
FIXME: summarize #6528
FIXME: summarize #6143
FIXME: summarize #6438
FIXME: summarize #6493
FIXME: summarize #6563
FIXME: summarize #6602
FIXME: summarize #6302
new optional package p_group_cohomology (Simon A. King, David J. Green)
- Compute the cohomology ring with coefficients in GF(p) for any finite p-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 a-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 2-subgroup 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.
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 2-Cochain in H^*(SmallGroup(64,132); GF(2)), c_2_5, a 2-Cochain in H^*(SmallGroup(64,132); GF(2)), c_4_12, a 4-Cochain in H^*(SmallGroup(64,132); GF(2)), a_1_0, a 1-Cochain in H^*(SmallGroup(64,132); GF(2)), a_1_1, a 1-Cochain in H^*(SmallGroup(64,132); GF(2)), b_1_2, a 1-Cochain 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 2-Cochain in H^*(D8; GF(2)), b_1_0, a 1-Cochain in H^*(D8; GF(2)), b_1_1, a 1-Cochain 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 2-Cochain in H^*(GapD8; GF(2)), b_1_0, a 1-Cochain in H^*(GapD8; GF(2)), b_1_1, a 1-Cochain 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 2-Cochain in H^*(SmallGroup(81,8); GF(3)), a_2_2, a 2-Cochain in H^*(SmallGroup(81,8); GF(3)), b_2_0, a 2-Cochain in H^*(SmallGroup(81,8); GF(3)), a_4_1, a 4-Cochain in H^*(SmallGroup(81,8); GF(3)), b_4_2, a 4-Cochain in H^*(SmallGroup(81,8); GF(3)), b_6_3, a 6-Cochain in H^*(SmallGroup(81,8); GF(3)), c_6_4, a 6-Cochain in H^*(SmallGroup(81,8); GF(3)), a_1_0, a 1-Cochain in H^*(SmallGroup(81,8); GF(3)), a_1_1, a 1-Cochain in H^*(SmallGroup(81,8); GF(3)), a_3_2, a 3-Cochain in H^*(SmallGroup(81,8); GF(3)), a_5_2, a 5-Cochain in H^*(SmallGroup(81,8); GF(3)), a_5_3, a 5-Cochain in H^*(SmallGroup(81,8); GF(3)), a_7_5, a 7-Cochain 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