Sage Days 23.5 Coding Sprint Projects

Contents

  1. Sage Days 23.5 Coding Sprint Projects
    1. Fix Sage's wrapping of Singular's Brill-Noether
    2. Python <--> Singular Linking Discussion
    3. Singular Parallel Build
    4. Doctest the Free Algebra Quotient code
    5. Letterplace
    6. error: out of memory
    7. Relative number field arithmetic
    8. Delete a function related to multivariate polynomial factorization from Sage
    9. (Done) Gröbner bases in Sage: Optional parameters
    10. extend polynomial rings mod 2^n to n > 30, and over ZZ
    11. (Done) big exponents
    12. Plural interface
    13. Multivariate GCD, factorization, etc. benchmarks
    14. Implement multivariate factorization over finite fields
    15. Fix bug(s) in Singular needed for updating the spkg
    16. (Done) Error handling in Libsingular
    17. (Done) Catch Singular error messages
  2. other stuff
    1. @fork, @parallel decorator
    2. Profiling Cython code

Fix Sage's wrapping of Singular's Brill-Noether

Python <--> Singular Linking Discussion

How: Dinner and beer.

Have a technical discussion of linking Python and Singular and Sage.

We tried to use the PSICO-approach to import sage into Singular. It failed (inifinite loop at integer.pyx), despite inidividual Cython modules can be loaded. Further investigations will follow.

Singular Parallel Build

People: Hans S. + A. Dreyer

Goals:

  1. Tell us which components of singular build in parallel via some testing.

We fixed this upstream (added dependencies to build system), Hans made anew release. The spkg was fixed by malb last night.

Doctest the Free Algebra Quotient code

People: Gabriel Pannwitz

The file SAGE_ROOT/devel/sage/sage/algebras/free_algebra_quotient.py has no doctests. Get it to 100% coverage. The point of this is that it is related to wrapping something like letterplace.

Letterplace

People: Martin Albrecht will review.

Do a very basic wrapping of letterplace for Sage. Use this to replace some of the lame old code in the SAGE_ROOT/devel/sage/sage/algebras/ directory. See here: #7797

error: out of memory

People: William Stein, Hans S.

Relative number field arithmetic

People: Mohamed, Andrew, William Stein

Goal:

  1. (done) Explain how to compute inverses.

  2. (done) Open a trac ticket about this: trac 9500

  3. (done) Post a little experimental code that indicates how fast this could be.

  4. (done) Post a patch to the above ticket.

People: William Stein

(Done) Gröbner bases in Sage: Optional parameters

People: Simon King, with a help from Martin and Hannes (more than minutes...)

extend polynomial rings mod 2^n to n > 30, and over ZZ

Rings mod 2^n are limited to n <= 30, but we'd like to have n<=62 by using longs. This would be relevant for some crypto applications.

(Done) big exponents

Provide an interface to use Singular monomials with big exponents (64-bit instead of 16-bit)

Sage Trac ticket: Trac #7795

Plural interface

Revive #4539 to provide a basic interface to Plural. This will involve writing new parent and element classes for plural at least.

This works using the libsingular interface, without inheriting from the commutative polynomial classes now: 

sage: A.<x,y,z>=FreeAlgebra(QQ,3)
sage: H=A.g_algebra({y*x:x*y-z, z*x:x*z+2*x, z*y:y*z-2*y})
sage: H.inject_variables()
Defining x, y, z
sage: z*x
x*z + 2*x
sage: z*y
y*z - 2*y
sage: I = H.ideal([y^2, x^2, z^2-H.one_element()],coerce=False)
sage: I._groebner_basis_libsingular()
[z^2 - 1, y*z - y, x*z + x, y^2, 2*x*y - z - 1, x^2]

This meant adding a lot of instances of this in the interface: 

            if PY_TYPE_CHECK(a, MPolynomialIdeal) or \
                    PY_TYPE_CHECK(a, NCPolynomialIdeal):
                ring2 = a.ring()
            elif PY_TYPE_CHECK(a, MPolynomial_libsingular) or \
                    PY_TYPE_CHECK(a, NCPolynomial_plural):
                ring2 = a.parent()
            elif PY_TYPE_CHECK(a, MPolynomialRing_libsingular) or \
                    PY_TYPE_CHECK(a, NCPolynomialRing_plural):
                ring2 = a

Michael volunteered to fix the rest of these. We also need coercion to work: 

sage: z^2-1
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
...
NotImplementedError: 
Also, please make sure you have implemented has_coerce_map_from_impl or has_coerce_map_from_c_impl (or better _an_element_c_impl or _an_element_impl if possible) for Noncommutative Multivariate Polynomial Ring in x, y, z over Rational Field

sage: z^2-H.one_element()
z^2 - 1

Multivariate GCD, factorization, etc. benchmarks

Take a look at the new code in GIAC, benchmarks posted here. Compare to improvements in Singular-Factory. See here for more gcd benchmarks and scripts.

Polynomials in Q[x,y,z]:

  1. ((1+x+y+z)20+1)*((1+x+y+z)20+2)

  2. ((1+x+y+z)30+1)*((1+x+y+z)30+2)

  3. (x+y+z2)25-(y-x+3*z-1+x2)25

  4. (x+y+z)30-1

  5. (2+x-y+z)20-220

  6. x200-1

  7. x50-250

  8. x40-(y+z)40

  9. (x+y)10-(y-z)10

  10. (1-3*x-4*y+3*z-y*z2-3*y*z3-y2*z-3*y2*z2+3*y2*z3-y3*z-2*y3*z2-3*y3*z3+3*x*z-3*x*z2+2*x*z3+x*y-3*x*y3+3*x2*z-4*x2*z2-x2*z3-x2*y+3*x2*y2-5*x2*y3-x3*z-5*x3*z2-2*x3*z3+2*x3*y+4*x3*y3-x*y2+3*x*y2*z+4*x3*y2+3*y*z-5*z3-4*y2+2*y3+2*x2*y2*z2+3*x*y3*z2+3*x*y3*z+4*x*y*z2+3*x*y3*z3-5*x*y2*z2+3*x*y*z-3*x3*y3*z-5*x2*y3*z3-5*x*y2*z3-5*x2*y*z2+3*x2*y3*z-x3*y2*z2-x3*y2*z-x3*y2*z3-4*x2*y2*z3+2*x2*y*z-4*x2*y*z3+x2*y3*z2-x2*y2*z-5*x3*y*z2-x3*y*z3-x3*y*z-5*x*y*z3-2*x2+3*x3)4-1

  11. (360-201*x+389*y+258*z-200*y*z+491*y*z2+493*y2*z+454*y2*z2-401*x*z+49*x*z2-304*x*y-484*x*y2+262*x2*z-339*x2*z2-227*x2*y-330*x2*y2+250*z2-495*y2-218*x*y*z-476*x2*y2*z2+243*x*y2*z+94*x2*y2*z+240*x*y2*z2-149*x*y*z2-321*x2*y*z-189*x2*y*z2+357*x2)4-1

  12. x800-1

  13. (101-139*x-24*y+104*z-103*y*z-451*y*z2-326*y2*z-493*y2*z2-327*x*z+439*x*z2-108*x*y+155*x*y2+121*x2*z-462*x2*z2+103*x2*y+217*x2*y2+327*z2-122*y2+344*x*y*z-262*x2*y2*z2+396*x*y2*z+8*x2*y2*z-47*x*y2*z2-314*x*y*z2+82*x2*y*z-50*x2*y*z2-424*x2)6-1

  14. (14878-22176*x+8386*y+41700*z-38290*y*z+44119*y*z2-37070*y2*z+45024*y2*z2+47986*x*z-28140*x*z2+33417*x*y-31087*x*y2+45572*x2*z-46632*x2*z2-77*x2*y-15943*x2*y2-21957*z2-14839*y2-41351*x*y*z-35985*x2*y2*z2+43811*x*y2*z-35522*x2*y2*z+23454*x*y2*z2-33462*x*y*z2-32836*x2*y*z+9538*x2*y*z2+31480*x2)6-1

  15. (-4212647-3198520*x+2950231*y -3315421*z +3701831*y*z +2351230*y*z2 +108373*y2*z +1812831*y2*z2+379586*x*z-3385311*x*z2+2453252*x*y+3838359*x*y2+2688541*x2*z+1838684*x2*z2-4852824*x2*y-4824055*x2*y2+90165*z2+651277*y2+2363714*x*y*z-4782981*x2*y2*z2-4578460*x*y2*z+4757744*x2*y2*z+681595*x*y2*z2+398600*x*y*z2+1864322*x2*y*z+1600103*x2*y*z2+2488109*x2)4-1

  16. ((x+y+z)10 - 410)5-35

  17. ((x+y+z)5 - 25)8-38

Bechmarks (someone check these, its late...).

GIAC and Singular on AMD opeteron 2800MHZ, Magma on AMD opeteron 2300MHZ (due to licence)

time in s (using timer in singular, which is probably not very excact)

Polynomial

GIAC 9.0.2

Singular 3.1.1.3

Magma

1

1

15

9

2

13

111

164

3

1

4

3

4

0

1

1

5

0

0

0

6

0

0

0

7

0

integer overflow

0

8

0

0

0

9

0

0

0

10

0

0

0

11

0

1

0

12

0

0

0

13

1

1

0

14

1

1

0

15

0

1

0

16

0

1

0

17

1

1

1

18

0

1

1

Implement multivariate factorization over finite fields

Fix bug(s) in Singular needed for updating the spkg

(Done) Error handling in Libsingular

(Done) Catch Singular error messages

People: Martin Albrecht

#9506

other stuff

@fork, @parallel decorator

Simon King mentioned that sometimes his code crashes/leaks/etc. So make it so one can do: 

@fork
def f(x,y,z,...):
    ...

and then f gets computed in a blocking forked process, and the result is returned via pickling. This is 100% to thwart mem leaks, segfaults, and guaranteed timeout possibility. This could be basically just a light wrapper around @parallel(1). Also, make a global flag to turn this off, so @fork does nothing.

Profiling Cython code

sage: gc = sage.coding.code_constructions.BinaryGolayCode()
sage: M = gc.extended_code().gen_mat()
sage: from sage.groups.perm_gps.partn_ref.refinement_binary import LinearBinaryCodeStruct
sage: from sage.coding.binary_code import BinaryCodeClassifier, BinaryCode
sage: BC = BinaryCodeClassifier()
sage: B = BinaryCode(M)
sage: BN = LinearBinaryCodeStruct(M)
sage: BN.run()
wd deg tot clock ticks 683242
     563425 calls
     1.21265829525 per call
cl deg tot clock ticks 281302
     144294 calls
     1.94950586996 per call
sage: x = BC._aut_gp_and_can_label(B)
wd deg tot clock ticks 659583
     746525 calls
     0.883537724792 per call
cl deg tot clock ticks 183800
     193324 calls
     0.950735552751 per call

days23.5/projects (last edited 2010-07-19 09:54:57 by MoritzMinzlaff)