Differences between revisions 16 and 17
Revision 16 as of 2009-08-20 15:54:54
Size: 15592
Editor: jrasch
Comment:
Revision 17 as of 2009-08-21 14:07:48
Size: 16901
Editor: Minh Nguyen
Comment: Summarize #5996
Deletions are marked like this. Additions are marked like this.
Line 73: Line 73:
 * [[http://trac.sagemath.org/sage_trac/ticket/5996|#5996]]

Collection of functions for calculating Wigner 3j, 6j, 9j,
Clebsch-Gordan, Racah as well as Gaunt coefficients exactly, all
evaluating to a rational number times the square root of a rational
number.
 * Wigner `3j`, `6j`, `9j`, Clebsch-Gordan, Racah and Gaunt coefficients (Jens Rasch) [[http://trac.sagemath.org/sage_trac/ticket/5996|#5996]] --- A collection of functions for exactly calculating Wigner [[http://en.wikipedia.org/wiki/3-jm_symbol|`3j`]], [[http://en.wikipedia.org/wiki/6-j_symbol|`6j`]], [[http://en.wikipedia.org/wiki/9-j_symbol|`9j`]], [[http://en.wikipedia.org/wiki/Clebsch-Gordan_coefficients|Clebsch-Gordan]], [[http://en.wikipedia.org/wiki/Racah_W-coefficient|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:
 {{{#!python numbers=off
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 Clebsch-Gordan, Racah and Gaunt coefficients can be computed as follows:
 {{{#!python numbers=off
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
 }}}

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:

    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 Clebsch-Gordan, 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

  • FIXME: summarize #6519. Many BEFORE-AFTER examples are available a the bottom of WordDesign page. Those could be copy and pasted here.

  • FIXME: summarize #6621

  • FIXME: summarize #5790

Cryptography

Documentation

Elliptic Curves

  • #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.

Graphics

Graph Theory

  • Inclusion of Cliquer as a standard package (Trac#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.

  • FIXME: summarize #6540

  • FIXME: summarize #6552

  • FIXME: summarize #6578

  • New algorithm for all Graph functions related to the computation of maximum Cliques (Trac #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

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

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

Symbolics

ReleaseTours/sage-4.1.1 (last edited 2019-11-14 21:03:14 by chapoton)