Commits

Volker Braun  committed 1816343

more patches

  • Participants
  • Parent commits b24c44b

Comments (0)

Files changed (19)

File m4rie_new_version.patch

+# HG changeset patch
+# User Martin Albrecht <martinralbrecht@googlemail.com>
+# Date 1366293864 -3600
+# Node ID c6b62368932f124230cc408ee26db69bc9ead518
+# Parent  32d2e829ed7c52175c00d8f874b3e952748ba129
+update M4RIE interface to newest upstream release (#14336)
+
+diff --git a/module_list.py b/module_list.py
+--- a/module_list.py
++++ b/module_list.py
+@@ -50,12 +50,12 @@
+ #########################################################
+ 
+ import ast
+-m4ri_extra_compile_args = []
++m4ri_extra_compile_args = ["-std=c99"]
+ for line in open(SAGE_INC + "/m4ri/m4ri_config.h"):
+     if not line.startswith("#define __M4RI_SIMD_CFLAGS"):
+         continue
+     m4ri_sse2_cflags = ast.literal_eval(line[len("#define __M4RI_SIMD_CFLAGS"):].strip())
+-    m4ri_extra_compile_args = [flag.strip() for flag in m4ri_sse2_cflags.split(" ") if flag.strip()]
++    m4ri_extra_compile_args.extend( [flag.strip() for flag in m4ri_sse2_cflags.split(" ") if flag.strip()] )
+     break
+ 
+ singular_libs = ['m', 'readline', 'singular', 'givaro', 'ntl', 'gmpxx', 'gmp']
+@@ -1011,7 +1011,7 @@
+     # TODO -- change to use BLAS at some point.
+     Extension('sage.matrix.matrix_integer_dense',
+               sources = ['sage/matrix/matrix_integer_dense.pyx'],
+-              extra_compile_args = ['-std=c99'] + m4ri_extra_compile_args,
++              extra_compile_args = m4ri_extra_compile_args,
+               depends = [SAGE_INC + '/m4ri/m4ri.h'],
+               # order matters for cygwin!!
+               libraries = ['iml', 'pari', 'gmp', 'm', BLAS, BLAS2]),
+@@ -1023,16 +1023,16 @@
+     Extension('sage.matrix.matrix_mod2_dense',
+               sources = ['sage/matrix/matrix_mod2_dense.pyx'],
+               libraries = ['gmp','m4ri', 'gd', 'png12', 'z'],
+-              extra_compile_args = ['-std=c99'] + m4ri_extra_compile_args,
++              extra_compile_args = m4ri_extra_compile_args,
+               depends = [SAGE_INC + "/png.h", SAGE_INC + "/m4ri/m4ri.h"]),
+ 
+     Extension('sage.matrix.matrix_mod2e_dense',
+               sources = ['sage/matrix/matrix_mod2e_dense.pyx'],
+-              libraries = ['m4rie', 'm4ri', 'givaro', 'ntl', 'gmpxx', 'gmp', 'm', 'stdc++'],
++              libraries = ['m4rie', 'm4ri', 'm'],
+               depends = [SAGE_INC + "/m4rie/m4rie.h"],
+               include_dirs = [SAGE_INC + '/m4rie'],
+-              extra_compile_args = m4ri_extra_compile_args + givaro_extra_compile_args,
+-              language="c++"),
++              extra_compile_args = m4ri_extra_compile_args,
++              language="c"),
+ 
+     Extension('sage.matrix.matrix_modn_dense',
+               sources = ['sage/matrix/matrix_modn_dense.pyx'],
+@@ -1285,7 +1285,7 @@
+     Extension('sage.modules.vector_mod2_dense',
+               sources = ['sage/modules/vector_mod2_dense.pyx'],
+               libraries = ['gmp','m4ri', 'png12', 'gd'],
+-              extra_compile_args = ['-std=c99'] + m4ri_extra_compile_args,
++              extra_compile_args = m4ri_extra_compile_args,
+               depends = [SAGE_INC + "/png.h", SAGE_INC + "/m4ri/m4ri.h"]),
+     
+     Extension('sage.modules.vector_rational_dense',
+diff --git a/sage/crypto/mq/sr.py b/sage/crypto/mq/sr.py
+--- a/sage/crypto/mq/sr.py
++++ b/sage/crypto/mq/sr.py
+@@ -1056,8 +1056,8 @@
+         
+             sage: sr = mq.SR(2, 2, 2, 4)
+             sage: sr.random_state_array()
+-            [      a^2 + 1 a^3 + a^2 + a]
+-            [  a^3 + a + 1         a + 1]
++            [              a^2       a^3 + a + 1]
++            [a^3 + a^2 + a + 1             a + 1]
+         """
+         return random_matrix(self.base_ring(), self._r, self._c, *args, **kwds)
+ 
+@@ -1070,22 +1070,22 @@
+         
+             sage: sr = mq.SR(2, 2, 2, 4)
+             sage: sr.random_vector()
+-            [      a^2 + 1]
+-            [            a]
+-            [          a^2]
+-            [        a + 1]
+-            [  a^3 + a + 1]
+-            [      a^3 + 1]
+-            [a^3 + a^2 + 1]
+-            [a^3 + a^2 + a]
+-            [a^3 + a^2 + a]
+-            [  a^3 + a + 1]
+-            [      a^3 + 1]
+-            [a^3 + a^2 + 1]
+-            [        a + 1]
+-            [      a^2 + 1]
+-            [            a]
+-            [          a^2]
++            [              a^2]
++            [            a + 1]
++            [          a^2 + 1]
++            [                a]
++            [a^3 + a^2 + a + 1]
++            [          a^3 + a]
++            [              a^3]
++            [        a^3 + a^2]
++            [      a^3 + a + 1]
++            [          a^3 + 1]
++            [    a^3 + a^2 + 1]
++            [    a^3 + a^2 + a]
++            [            a + 1]
++            [          a^2 + 1]
++            [                a]
++            [              a^2]
+         
+         .. note::
+ 
+@@ -1109,12 +1109,12 @@
+         
+             sage: sr = mq.SR()
+             sage: sr.random_element()
++            [    a^2]
++            [  a + 1]
+             [a^2 + 1]
+             [      a]
+-            [    a^2]
+-            [  a + 1]
+             sage: sr.random_element('state_array')
+-            [a^3 + 1]
++            [a^3 + a + 1]
+ 
+         Passes extra positional or keyword arguments through::
+ 
+@@ -2033,7 +2033,7 @@
+             sage: P = sr.vars("P",0)
+             sage: F,s = sr.polynomial_system(P=P,C=C)
+             sage: [(k,v) for k,v in sorted(s.iteritems())] # this can be ignored
+-            [(k003, 1), (k002, 0), (k001, 0), (k000, 1)]
++            [(k003, 1), (k002, 1), (k001, 0), (k000, 1)]
+             sage: F
+             Polynomial Sequence with 36 Polynomials in 28 Variables
+             sage: F.part(0)
+@@ -2220,7 +2220,7 @@
+             sage: sr = mq.SR()
+             sage: A = sr.random_state_array()
+             sage: A
+-            [a^2 + 1]
++            [a^2]
+             sage: sr.antiphi(sr.phi(A)) == A
+             True
+         """
+@@ -2625,7 +2625,7 @@
+             sage: sr = mq.SR(gf2=True)
+             sage: A = sr.random_state_array()
+             sage: A
+-            [a^2 + 1]
++            [a^2]
+             sage: sr.antiphi(sr.phi(A)) == A
+             True
+         """
+diff --git a/sage/libs/m4rie.pxd b/sage/libs/m4rie.pxd
+--- a/sage/libs/m4rie.pxd
++++ b/sage/libs/m4rie.pxd
+@@ -11,11 +11,16 @@
+ 
+ cdef extern from "m4rie/m4rie.h":
+     ctypedef struct gf2e:
+-        m4ri_word **mul
+-        m4ri_word *inv
+-        size_t degree
++        int degree
+         m4ri_word minpoly
+ 
++        m4ri_word *pow_gen
++        m4ri_word *red
++
++        m4ri_word (*inv)(gf2e *ff, m4ri_word a)
++        m4ri_word (*mul)(gf2e *ff, m4ri_word a, m4ri_word b)
++
++    gf2e *gf2e_init(m4ri_word minpoly)
+     void gf2e_free(gf2e *ff)
+ 
+ #cdef extern from "m4rie/mzed.h":
+@@ -52,9 +57,9 @@
+ 
+     void mzed_add_elem(mzed_t *a, const_size_t row, const_size_t col, const_int elem)
+ 
+-    void mzed_add_multiple_of_row(mzed_t *A, size_t ar, mzed_t *B, size_t br, m4ri_word *X, size_t start_col)
++    void mzed_add_multiple_of_row(mzed_t *A, size_t ar, mzed_t *B, size_t br, m4ri_word x, size_t start_col)
+ 
+-    void mzed_rescale_row(mzed_t *A, size_t r, size_t c, m4ri_word *X)
++    void mzed_rescale_row(mzed_t *A, size_t r, size_t c, m4ri_word x)
+ 
+     void mzed_row_swap(mzed_t *M, const_size_t rowa, const_size_t rowb)
+ 
+@@ -159,7 +164,7 @@
+ 
+     int mzd_slice_is_zero(mzd_slice_t *A)
+ 
+-    void mzd_slice_rescale_row(mzd_slice_t *A, size_t r, size_t c, m4ri_word *X)
++    void mzd_slice_rescale_row(mzd_slice_t *A, size_t r, size_t c, m4ri_word x)
+ 
+     void mzd_slice_row_swap(mzd_slice_t *A, size_t rowa, size_t rowb)
+ 
+@@ -197,15 +202,3 @@
+     mzd_slice_t *_mzd_slice_mul_karatsuba2(mzd_slice_t *C, mzd_slice_t *A, mzd_slice_t *B)
+ 
+     mzd_slice_t *_mzd_slice_mul_karatsuba3(mzd_slice_t *C, mzd_slice_t *A, mzd_slice_t *B)
+-
+-cdef extern from "m4rie/finite_field_givaro.h":
+-    ctypedef struct M4RIE__FiniteField "M4RIE::FiniteField":
+-        int (* pol2log)(int r)
+-        int (* log2pol)(int r)
+-        
+-    gf2e *gf2e_init_givgfq(M4RIE__FiniteField *givgfq)
+-
+-    int mzed_read_elem_log(const_mzed_t *a, const_size_t row, const_size_t col, M4RIE__FiniteField *ff)
+-    void mzed_write_elem_log(mzed_t *a, const_size_t row, const_size_t col, const_int elem, M4RIE__FiniteField *ff)
+-    void mzed_add_elem_log(mzed_t *a, const_size_t row, const_size_t col, const_int elem, M4RIE__FiniteField *ff)
+-        
+diff --git a/sage/matrix/matrix_mod2e_dense.pxd b/sage/matrix/matrix_mod2e_dense.pxd
+--- a/sage/matrix/matrix_mod2e_dense.pxd
++++ b/sage/matrix/matrix_mod2e_dense.pxd
+@@ -1,14 +1,11 @@
+ # choose: dense or sparse
+ 
+-from sage.rings.finite_rings.element_givaro cimport GivaroGfq, Cache_givaro
+-
+ from sage.libs.m4rie cimport mzed_t
+ 
+ cimport matrix_dense 
+ 
+ cdef class Matrix_mod2e_dense(matrix_dense.Matrix_dense):
+     cdef mzed_t *_entries
+-    cdef Cache_givaro cc
+     cdef object _one
+     cdef object _zero
+ 
+diff --git a/sage/matrix/matrix_mod2e_dense.pyx b/sage/matrix/matrix_mod2e_dense.pyx
+--- a/sage/matrix/matrix_mod2e_dense.pyx
++++ b/sage/matrix/matrix_mod2e_dense.pyx
+@@ -35,14 +35,14 @@
+     sage: K.<a> = GF(2^8)
+     sage: A = random_matrix(K, 3,4)
+     sage: A
+-    [                  a^3 + a^2 + 1         a^7 + a^5 + a^4 + a + 1                       a^7 + a^3                   a^6 + a^4 + a]
+-    [      a^5 + a^4 + a^3 + a^2 + 1 a^7 + a^6 + a^5 + a^4 + a^3 + a             a^5 + a^4 + a^3 + a             a^6 + a^4 + a^2 + 1]
+-    [  a^6 + a^5 + a^4 + a^2 + a + 1   a^7 + a^5 + a^3 + a^2 + a + 1       a^7 + a^6 + a^3 + a^2 + a             a^7 + a^5 + a^3 + a]
++    [          a^6 + a^5 + a^4 + a^2               a^6 + a^3 + a + 1         a^5 + a^3 + a^2 + a + 1               a^7 + a^6 + a + 1]
++    [                a^7 + a^6 + a^3             a^7 + a^6 + a^5 + 1         a^5 + a^4 + a^3 + a + 1 a^6 + a^5 + a^4 + a^3 + a^2 + 1]
++    [              a^6 + a^5 + a + 1                   a^7 + a^3 + 1               a^7 + a^3 + a + 1   a^7 + a^6 + a^3 + a^2 + a + 1]
+ 
+     sage: A.echelon_form()
+-    [                        1                         0                         0       a^7 + a^6 + a^2 + a]
+-    [                        0                         1                         0     a^6 + a^4 + a^3 + a^2]
+-    [                        0                         0                         1 a^6 + a^4 + a^3 + a^2 + a]
++    [                        1                         0                         0     a^6 + a^5 + a^4 + a^2]
++    [                        0                         1                         0   a^7 + a^5 + a^3 + a + 1]
++    [                        0                         0                         1 a^6 + a^4 + a^3 + a^2 + 1]
+ 
+ AUTHOR:
+ 
+@@ -61,8 +61,7 @@
+ REFERENCES:
+ 
+ .. [BB09] Tomas J. Boothby and Robert W. Bradshaw. *Bitslicing
+-and the Method of Four Russians Over Larger Finite
+-Fields*. arXiv:0901.1413v1,
++   and the Method of Four Russians Over Larger Finite Fields*. arXiv:0901.1413v1,
+ 2009. http://arxiv.org/abs/0901.1413
+ """
+ 
+@@ -76,21 +75,20 @@
+ from sage.structure.element cimport ModuleElement, Element, RingElement
+ 
+ from sage.rings.all import FiniteField as GF
+-from sage.rings.finite_rings.element_givaro cimport FiniteField_givaroElement, GivRandom, GivRandomSeeded
+ from sage.misc.randstate cimport randstate, current_randstate
+ 
+ from sage.matrix.matrix_mod2_dense cimport Matrix_mod2_dense
+ 
+ from sage.libs.m4ri cimport m4ri_word, mzd_copy, mzd_init
+ from sage.libs.m4rie cimport *
+-from sage.libs.m4rie cimport mzed_t, M4RIE__FiniteField
++from sage.libs.m4rie cimport mzed_t
+ 
+ 
+ # we must keep a copy of the internal finite field representation
+ # around to avoid re-creating it over and over again. Furthermore,
+ # M4RIE assumes pointer equivalence of identical fields.
+ 
+-_givaro_cache = {}
++_m4rie_finite_field_cache = {}
+ 
+ cdef class M4RIE_finite_field:
+     """
+@@ -121,6 +119,12 @@
+         if self.ff:
+             gf2e_free(self.ff)
+ 
++cdef m4ri_word poly_to_word(f):
++    return f.integer_representation()
++
++cdef object word_to_poly(w, F):
++    return F.fetch_int(w)
++
+ cdef class Matrix_mod2e_dense(matrix_dense.Matrix_dense): 
+     ########################################################################
+     # LEVEL 1 functionality
+@@ -146,9 +150,9 @@
+             [0 0 0 0]
+ 
+             sage: A.randomize(); A 
+-            [      a^2 + 1 a^3 + a^2 + a   a^3 + a + 1         a + 1]
+-            [        a + 1         a + 1       a^3 + a     a^3 + a^2]
+-            [a^3 + a^2 + a             a             1   a^3 + a + 1]
++            [              a^2       a^3 + a + 1 a^3 + a^2 + a + 1             a + 1]
++            [              a^3                 1       a^3 + a + 1     a^3 + a^2 + 1]
++            [            a + 1           a^3 + 1       a^3 + a + 1 a^3 + a^2 + a + 1]
+ 
+             sage: K.<a> = GF(2^3)
+             sage: A = Matrix(K,3,4); A
+@@ -157,9 +161,9 @@
+             [0 0 0 0]
+ 
+             sage: A.randomize(); A
+-            [a^2 + 1       0   a + 1       0]
+-            [      a       a   a + 1       a]
+-            [      1     a^2 a^2 + a       0]
++            [    a^2 + a     a^2 + 1     a^2 + a     a^2 + a]
++            [    a^2 + 1 a^2 + a + 1     a^2 + 1         a^2]
++            [    a^2 + a     a^2 + 1 a^2 + a + 1       a + 1]
+         """
+         matrix_dense.Matrix_dense.__init__(self, parent)
+ 
+@@ -167,16 +171,17 @@
+ 
+         R = parent.base_ring()
+ 
+-        self.cc = <Cache_givaro>R._cache
++        f = R.polynomial()
++        cdef m4ri_word poly = sum(int(c)*2**i for i,c in enumerate(f))
+         
+         if alloc and self._nrows and self._ncols:
+-            if self.cc in _givaro_cache:
+-                self._entries = mzed_init((<M4RIE_finite_field>_givaro_cache[self.cc]).ff, self._nrows, self._ncols)
++            if poly in _m4rie_finite_field_cache:
++                self._entries = mzed_init((<M4RIE_finite_field>_m4rie_finite_field_cache[poly]).ff, self._nrows, self._ncols)
+             else:
+                 FF = PY_NEW(M4RIE_finite_field)
+-                FF.ff = gf2e_init_givgfq(<M4RIE__FiniteField*>self.cc.objectptr)
++                FF.ff = gf2e_init(poly)
+                 self._entries = mzed_init(FF.ff, self._nrows, self._ncols)
+-                _givaro_cache[self.cc] = FF
++                _m4rie_finite_field_cache[poly] = FF
+ 
+         # cache elements
+         self._zero = self._base_ring(0)
+@@ -230,7 +235,6 @@
+             [0 0 a]
+         """
+         cdef int i,j
+-        cdef FiniteField_givaroElement e
+ 
+         if entries is None:
+             return
+@@ -256,8 +260,7 @@
+             if PyErr_CheckSignals(): raise KeyboardInterrupt
+             for j from 0 <= j < self._ncols:
+                 e = R(entries[k])
+-                
+-                mzed_write_elem_log(self._entries,i,j, e.element, <M4RIE__FiniteField*>self.cc.objectptr)
++                mzed_write_elem(self._entries, i, j, poly_to_word(e))
+                 k = k + 1
+             
+     cdef set_unsafe(self, Py_ssize_t i, Py_ssize_t j, value):
+@@ -283,7 +286,7 @@
+             [          a a^3 + a + 1       a + 1       a + 1]
+             [        a^2 a^3 + a + 1     a^3 + a     a^3 + a]
+         """
+-        mzed_write_elem_log(self._entries, i, j, (<FiniteField_givaroElement>value).element, <M4RIE__FiniteField*>self.cc.objectptr)
++        mzed_write_elem(self._entries, i, j, poly_to_word(value))
+ 
+     cdef get_unsafe(self, Py_ssize_t i, Py_ssize_t j):
+         """
+@@ -298,16 +301,16 @@
+             sage: K.<a> = GF(2^4)
+             sage: A = random_matrix(K,3,4)
+             sage: A[2,3]                         # indirect doctest
+-            a^3 + a + 1
++            a^3 + a^2 + a + 1
+             sage: K.<a> = GF(2^3)
+             sage: m,n  = 3, 4
+             sage: A = random_matrix(K,3,4); A
+-            [a^2 + 1       0   a + 1       0]
+-            [      a       a   a + 1       a]
+-            [      1     a^2 a^2 + a       0]
++            [    a^2 + a     a^2 + 1     a^2 + a     a^2 + a]
++            [    a^2 + 1 a^2 + a + 1     a^2 + 1         a^2]
++            [    a^2 + a     a^2 + 1 a^2 + a + 1       a + 1]
+         """
+-        cdef int r = mzed_read_elem_log(self._entries, i, j, <M4RIE__FiniteField*>self.cc.objectptr)
+-        return self.cc._new_c(r)
++        cdef int r = mzed_read_elem(self._entries, i, j)
++        return word_to_poly(r, self._base_ring)
+ 
+     cpdef ModuleElement _add_(self, ModuleElement right):
+         """
+@@ -321,19 +324,19 @@
+         
+             sage: K.<a> = GF(2^4)
+             sage: A = random_matrix(K,3,4); A
+-            [      a^2 + 1 a^3 + a^2 + a   a^3 + a + 1         a + 1]
+-            [        a + 1         a + 1       a^3 + a     a^3 + a^2]
+-            [a^3 + a^2 + a             a             1   a^3 + a + 1]
++            [              a^2       a^3 + a + 1 a^3 + a^2 + a + 1             a + 1]
++            [              a^3                 1       a^3 + a + 1     a^3 + a^2 + 1]
++            [            a + 1           a^3 + 1       a^3 + a + 1 a^3 + a^2 + a + 1]
+             
+             sage: B = random_matrix(K,3,4); B
+-            [          a^3 + 1                 0               a^3                 0]
+-            [          a^3 + a                 a     a^3 + a^2 + a           a^3 + a]
+-            [      a^3 + a + 1               a^2 a^3 + a^2 + a + 1           a^2 + 1]
++            [          a^2 + a           a^2 + 1           a^2 + a     a^3 + a^2 + a]
++            [          a^2 + 1 a^3 + a^2 + a + 1           a^2 + 1               a^2]
++            [    a^3 + a^2 + a           a^2 + 1       a^2 + a + 1       a^3 + a + 1]
+ 
+             sage: C = A + B; C # indirect doctest
+-            [    a^3 + a^2 a^3 + a^2 + a         a + 1         a + 1]
+-            [      a^3 + 1             1           a^2       a^2 + a]
+-            [      a^2 + 1       a^2 + a a^3 + a^2 + a a^3 + a^2 + a]
++            [            a a^3 + a^2 + a       a^3 + 1 a^3 + a^2 + 1]
++            [a^3 + a^2 + 1 a^3 + a^2 + a a^3 + a^2 + a       a^3 + 1]
++            [a^3 + a^2 + 1     a^3 + a^2     a^3 + a^2           a^2]
+         """
+         cdef Matrix_mod2e_dense A
+         A = Matrix_mod2e_dense.__new__(Matrix_mod2e_dense, self._parent, 0, 0, 0, alloc=False)
+@@ -352,19 +355,19 @@
+             sage: m,n  = 3, 4
+             sage: MS = MatrixSpace(K,m,n)
+             sage: A = random_matrix(K,3,4); A
+-            [      a^2 + 1 a^3 + a^2 + a   a^3 + a + 1         a + 1]
+-            [        a + 1         a + 1       a^3 + a     a^3 + a^2]
+-            [a^3 + a^2 + a             a             1   a^3 + a + 1]
++            [              a^2       a^3 + a + 1 a^3 + a^2 + a + 1             a + 1]
++            [              a^3                 1       a^3 + a + 1     a^3 + a^2 + 1]
++            [            a + 1           a^3 + 1       a^3 + a + 1 a^3 + a^2 + a + 1]
+ 
+             sage: B = random_matrix(K,3,4); B
+-            [          a^3 + 1                 0               a^3                 0]
+-            [          a^3 + a                 a     a^3 + a^2 + a           a^3 + a]
+-            [      a^3 + a + 1               a^2 a^3 + a^2 + a + 1           a^2 + 1]
++            [          a^2 + a           a^2 + 1           a^2 + a     a^3 + a^2 + a]
++            [          a^2 + 1 a^3 + a^2 + a + 1           a^2 + 1               a^2]
++            [    a^3 + a^2 + a           a^2 + 1       a^2 + a + 1       a^3 + a + 1]
+ 
+             sage: C = A - B; C  # indirect doctest
+-            [    a^3 + a^2 a^3 + a^2 + a         a + 1         a + 1]
+-            [      a^3 + 1             1           a^2       a^2 + a]
+-            [      a^2 + 1       a^2 + a a^3 + a^2 + a a^3 + a^2 + a]
++            [            a a^3 + a^2 + a       a^3 + 1 a^3 + a^2 + 1]
++            [a^3 + a^2 + 1 a^3 + a^2 + a a^3 + a^2 + a       a^3 + 1]
++            [a^3 + a^2 + 1     a^3 + a^2     a^3 + a^2           a^2]
+         """
+         return self._add_(right)
+ 
+@@ -548,22 +551,15 @@
+             sage: A._multiply_karatsuba(B) == A._multiply_classical(B)
+             True
+ 
+-        TESTS::
+-
+             sage: K.<a> = GF(2^10)
+             sage: A = random_matrix(K, 50, 50)
+             sage: B = random_matrix(K, 50, 50)
+             sage: A._multiply_karatsuba(B) == A._multiply_classical(B)
+-            Traceback (most recent call last):
+-            ...
+-            NotImplementedError: Karatsuba multiplication is only implemented for matrices over GF(2^e) with e <= 8.
++            True
+         """
+         if self._ncols != right._nrows:
+             raise ArithmeticError("left ncols must match right nrows")
+ 
+-        if self._entries.finite_field.degree > __M4RIE_MAX_KARATSUBA_DEGREE:
+-            raise NotImplementedError("Karatsuba multiplication is only implemented for matrices over GF(2^e) with e <= %d."%__M4RIE_MAX_KARATSUBA_DEGREE)
+-
+         cdef Matrix_mod2e_dense ans
+         
+         ans = self.new_matrix(nrows = self.nrows(), ncols = right.ncols())
+@@ -642,34 +638,31 @@
+              sage: K.<a> = GF(4)
+              sage: A = random_matrix(K,10,10)
+              sage: A
+-             [    0     1     1     0     0     0     a a + 1     1     a]
+-             [    1     1 a + 1     a a + 1     0     1     1     1 a + 1]
+-             [    1     0     a     1     1 a + 1     a     1 a + 1 a + 1]
+-             [    0     a     a     a     0     1     1     1     0     1]
+-             [    1     1     a     a     a a + 1 a + 1 a + 1     1     0]
+-             [a + 1 a + 1     a     a     0 a + 1     0     a     1     1]
+-             [a + 1 a + 1     0 a + 1     0 a + 1 a + 1     a     a     a]
+-             [    0     1     a     0     1     a a + 1 a + 1     a a + 1]
+-             [    0     1     a     1     1 a + 1     1 a + 1     a     a]
+-             [a + 1     a     0     a     a     a     0     a     0 a + 1]
++             [    0 a + 1 a + 1 a + 1     0     1 a + 1     1 a + 1     1]
++             [a + 1 a + 1     a     1     a     a     1 a + 1     1     0]
++             [    a     1 a + 1 a + 1     0 a + 1     a     1     a     a]
++             [a + 1     a     0     0     1 a + 1 a + 1     0 a + 1     1]
++             [    a     0 a + 1     a     a     0 a + 1     a     1 a + 1]
++             [    a     0     a a + 1     a     1 a + 1     a     a     a]
++             [a + 1     a     0     1     0 a + 1 a + 1     a     0 a + 1]
++             [a + 1 a + 1     0 a + 1     a     1 a + 1 a + 1 a + 1     0]
++             [    0     0     0 a + 1     1 a + 1     0 a + 1     1     0]
++             [    1 a + 1     0     1     a     0     0     a a + 1     a]
+              
+              sage: a*A # indirect doctest
+-             [    0     a     a     0     0     0 a + 1     1     a a + 1]
+-             [    a     a     1 a + 1     1     0     a     a     a     1]
+-             [    a     0 a + 1     a     a     1 a + 1     a     1     1]
+-             [    0 a + 1 a + 1 a + 1     0     a     a     a     0     a]
+-             [    a     a a + 1 a + 1 a + 1     1     1     1     a     0]
+-             [    1     1 a + 1 a + 1     0     1     0 a + 1     a     a]
+-             [    1     1     0     1     0     1     1 a + 1 a + 1 a + 1]
+-             [    0     a a + 1     0     a a + 1     1     1 a + 1     1]
+-             [    0     a a + 1     a     a     1     a     1 a + 1 a + 1]
+-             [    1 a + 1     0 a + 1 a + 1 a + 1     0 a + 1     0     1]
++             [    0     1     1     1     0     a     1     a     1     a]
++             [    1     1 a + 1     a a + 1 a + 1     a     1     a     0]
++             [a + 1     a     1     1     0     1 a + 1     a a + 1 a + 1]
++             [    1 a + 1     0     0     a     1     1     0     1     a]
++             [a + 1     0     1 a + 1 a + 1     0     1 a + 1     a     1]
++             [a + 1     0 a + 1     1 a + 1     a     1 a + 1 a + 1 a + 1]
++             [    1 a + 1     0     a     0     1     1 a + 1     0     1]
++             [    1     1     0     1 a + 1     a     1     1     1     0]
++             [    0     0     0     1     a     1     0     1     a     0]
++             [    a     1     0     a a + 1     0     0 a + 1     1 a + 1]
+         """
+-        if not isinstance(right, FiniteField_givaroElement):
+-            raise TypeError("right must be element of type 'FiniteField_givaroElement'")
+-
++        cdef m4ri_word a = poly_to_word(right)
+         cdef Matrix_mod2e_dense C = Matrix_mod2e_dense.__new__(Matrix_mod2e_dense, self._parent, 0, 0, 0)
+-        cdef m4ri_word a = <m4ri_word>(<M4RIE__FiniteField*>self.cc.objectptr).log2pol((<FiniteField_givaroElement>right).element)
+         mzed_mul_scalar(C._entries, a, self._entries)
+         return C
+ 
+@@ -679,14 +672,14 @@
+         
+             sage: K.<a> = GF(2^4)
+             sage: A = random_matrix(K, 3, 4); A
+-            [      a^2 + 1 a^3 + a^2 + a   a^3 + a + 1         a + 1]
+-            [        a + 1         a + 1       a^3 + a     a^3 + a^2]
+-            [a^3 + a^2 + a             a             1   a^3 + a + 1]
++            [              a^2       a^3 + a + 1 a^3 + a^2 + a + 1             a + 1]
++            [              a^3                 1       a^3 + a + 1     a^3 + a^2 + 1]
++            [            a + 1           a^3 + 1       a^3 + a + 1 a^3 + a^2 + a + 1]
+ 
+             sage: -A
+-            [      a^2 + 1 a^3 + a^2 + a   a^3 + a + 1         a + 1]
+-            [        a + 1         a + 1       a^3 + a     a^3 + a^2]
+-            [a^3 + a^2 + a             a             1   a^3 + a + 1]
++            [              a^2       a^3 + a + 1 a^3 + a^2 + a + 1             a + 1]
++            [              a^3                 1       a^3 + a + 1     a^3 + a^2 + 1]
++            [            a + 1           a^3 + 1       a^3 + a + 1 a^3 + a^2 + a + 1]
+         """
+         return self.__copy__()
+ 
+@@ -717,18 +710,18 @@
+             sage: K.<a> = GF(2^4)
+             sage: m,n  = 3, 4
+             sage: A = random_matrix(K,3,4); A
+-            [      a^2 + 1 a^3 + a^2 + a   a^3 + a + 1         a + 1]
+-            [        a + 1         a + 1       a^3 + a     a^3 + a^2]
+-            [a^3 + a^2 + a             a             1   a^3 + a + 1]
++            [              a^2       a^3 + a + 1 a^3 + a^2 + a + 1             a + 1]
++            [              a^3                 1       a^3 + a + 1     a^3 + a^2 + 1]
++            [            a + 1           a^3 + 1       a^3 + a + 1 a^3 + a^2 + a + 1]
+ 
+             sage: A2 = copy(A); A2
+-            [      a^2 + 1 a^3 + a^2 + a   a^3 + a + 1         a + 1]
+-            [        a + 1         a + 1       a^3 + a     a^3 + a^2]
+-            [a^3 + a^2 + a             a             1   a^3 + a + 1]
++            [              a^2       a^3 + a + 1 a^3 + a^2 + a + 1             a + 1]
++            [              a^3                 1       a^3 + a + 1     a^3 + a^2 + 1]
++            [            a + 1           a^3 + 1       a^3 + a + 1 a^3 + a^2 + a + 1]
+ 
+             sage: A[0,0] = 1
+             sage: A2[0,0]
+-            a^2 + 1
++            a^2
+         """
+         cdef Matrix_mod2e_dense A
+         A = Matrix_mod2e_dense.__new__(Matrix_mod2e_dense, self._parent, 0, 0, 0)
+@@ -745,12 +738,12 @@
+             sage: K.<a> = GF(2^4)
+             sage: m,n  = 3, 4
+             sage: A = random_matrix(K,3,4); A
+-            [      a^2 + 1 a^3 + a^2 + a   a^3 + a + 1         a + 1]
+-            [        a + 1         a + 1       a^3 + a     a^3 + a^2]
+-            [a^3 + a^2 + a             a             1   a^3 + a + 1]
++            [              a^2       a^3 + a + 1 a^3 + a^2 + a + 1             a + 1]
++            [              a^3                 1       a^3 + a + 1     a^3 + a^2 + 1]
++            [            a + 1           a^3 + 1       a^3 + a + 1 a^3 + a^2 + a + 1]
+ 
+             sage: A.list() # indirect doctest
+-            [a^2 + 1, a^3 + a^2 + a, a^3 + a + 1, a + 1, a + 1, a + 1, a^3 + a, a^3 + a^2, a^3 + a^2 + a, a, 1, a^3 + a + 1]
++            [a^2, a^3 + a + 1, a^3 + a^2 + a + 1, a + 1, a^3, 1, a^3 + a + 1, a^3 + a^2 + 1, a + 1, a^3 + 1, a^3 + a + 1, a^3 + a^2 + a + 1]
+         """
+         cdef int i,j
+         l = []
+@@ -781,14 +774,14 @@
+             sage: A = Matrix(K,3,3)
+ 
+             sage: A.randomize(); A
+-            [      a^2 + 1 a^3 + a^2 + a   a^3 + a + 1]
+-            [        a + 1         a + 1         a + 1]
+-            [      a^3 + a     a^3 + a^2 a^3 + a^2 + a]
++            [              a^2       a^3 + a + 1 a^3 + a^2 + a + 1]
++            [            a + 1               a^3                 1]
++            [      a^3 + a + 1     a^3 + a^2 + 1             a + 1]
+ 
+             sage: K.<a> = GF(2^4)
+             sage: A = random_matrix(K,1000,1000,density=0.1)
+             sage: float(A.density())
+-            0.099739...
++            0.0999...
+ 
+             sage: A = random_matrix(K,1000,1000,density=1.0)
+             sage: float(A.density())
+@@ -796,7 +789,7 @@
+ 
+             sage: A = random_matrix(K,1000,1000,density=0.5)
+             sage: float(A.density())
+-            0.49976...
++            0.4996...
+ 
+         Note, that the matrix is updated and not zero-ed out before
+         being randomized::
+@@ -804,24 +797,23 @@
+             sage: A = matrix(K,1000,1000)
+             sage: A.randomize(nonzero=False, density=0.1)
+             sage: float(A.density())
+-            0.0937679...
++            0.0936...
+             
+             sage: A.randomize(nonzero=False, density=0.05)
+             sage: float(A.density())
+-            0.13626...
++            0.1358539...
+         """
+         if self._ncols == 0 or self._nrows == 0:
+             return
+         
+         cdef Py_ssize_t i,j
+-        cdef int seed = current_randstate().c_random()
+-        cdef GivRandom generator = GivRandomSeeded(seed)
+-        cdef int tmp
+-
+         self.check_mutability()
+         self.clear_cache()
+ 
++        cdef m4ri_word mask = (1<<(self._parent.base_ring().degree())) - 1
++
+         cdef randstate rstate = current_randstate()
++        K = self._parent.base_ring()
+ 
+         if self._ncols == 0 or self._nrows == 0:
+             return
+@@ -837,17 +829,17 @@
+                 sig_on()
+                 for i in range(self._nrows):
+                     for j in range(self._ncols):
+-                        tmp = self.cc.objectptr.random(generator, tmp)
+-                        mzed_write_elem_log(self._entries, i, j, tmp, <M4RIE__FiniteField*>self.cc.objectptr)
++                        tmp = rstate.c_random() & mask
++                        mzed_write_elem(self._entries, i, j, tmp)
+                 sig_off()
+             else:
+                 sig_on()
+                 for i in range(self._nrows):
+                     for j in range(self._ncols):
+-                        tmp = self.cc.objectptr.random(generator,tmp)
+-                        while self.cc.objectptr.isZero(tmp):
+-                            tmp = self.cc.objectptr.random(generator,tmp)
+-                        mzed_write_elem_log(self._entries, i, j, tmp, <M4RIE__FiniteField*>self.cc.objectptr)
++                        tmp = rstate.c_random() & mask
++                        while tmp == 0:
++                            tmp = rstate.c_random() & mask
++                        mzed_write_elem(self._entries, i, j, tmp)
+                 sig_off()
+         else:
+             if nonzero == False:
+@@ -855,18 +847,18 @@
+                 for i in range(self._nrows):
+                     for j in range(self._ncols):
+                         if rstate.c_rand_double() <= _density:
+-                            tmp = self.cc.objectptr.random(generator, tmp)
+-                            mzed_write_elem_log(self._entries, i, j, tmp, <M4RIE__FiniteField*>self.cc.objectptr)
++                            tmp = rstate.c_random() & mask
++                            mzed_write_elem(self._entries, i, j, tmp)
+                 sig_off()
+             else:
+                 sig_on()
+                 for i in range(self._nrows):
+                     for j in range(self._ncols):
+                         if rstate.c_rand_double() <= _density:
+-                            tmp = self.cc.objectptr.random(generator,tmp)
+-                            while self.cc.objectptr.isZero(tmp):
+-                                tmp = self.cc.objectptr.random(generator,tmp)
+-                            mzed_write_elem_log(self._entries, i, j, tmp, <M4RIE__FiniteField*>self.cc.objectptr)
++                            tmp = rstate.c_random() & mask
++                            while tmp == 0:
++                                tmp = rstate.c_random() & mask
++                            mzed_write_elem(self._entries, i, j, tmp)
+                 sig_off()
+ 
+     def echelonize(self, algorithm='heuristic', reduced=True, **kwds):
+@@ -890,14 +882,14 @@
+             sage: K.<a> = GF(2^4)
+             sage: m,n  = 3, 5
+             sage: A = random_matrix(K, 3, 5); A
+-            [      a^2 + 1 a^3 + a^2 + a   a^3 + a + 1         a + 1         a + 1]
+-            [        a + 1       a^3 + a     a^3 + a^2 a^3 + a^2 + a             a]
+-            [            1   a^3 + a + 1     a^3 + a^2 a^3 + a^2 + 1           a^2]
++            [              a^2       a^3 + a + 1 a^3 + a^2 + a + 1             a + 1               a^3]
++            [                1       a^3 + a + 1     a^3 + a^2 + 1             a + 1           a^3 + 1]
++            [      a^3 + a + 1 a^3 + a^2 + a + 1           a^2 + a           a^2 + 1           a^2 + a]
+ 
+             sage: A.echelonize(); A
+-            [            1             0             0             a             a]
+-            [            0             1             0   a^2 + a + 1             a]
+-            [            0             0             1             a a^3 + a^2 + 1]
++            [            1             0             0         a + 1       a^2 + 1]
++            [            0             1             0           a^2         a + 1]
++            [            0             0             1 a^3 + a^2 + a           a^3]
+ 
+             sage: K.<a> = GF(2^3)
+             sage: m,n  = 3, 5
+@@ -905,19 +897,19 @@
+             sage: A = random_matrix(K, 3, 5)
+ 
+             sage: copy(A).echelon_form('newton_john')
+-            [          1           0           0         a^2     a^2 + 1]
+-            [          0           1           0         a^2           1]
+-            [          0           0           1 a^2 + a + 1       a + 1]
++            [          1           0       a + 1           0     a^2 + 1]
++            [          0           1 a^2 + a + 1           0           a]
++            [          0           0           0           1 a^2 + a + 1]
+             
+             sage: copy(A).echelon_form('naive');
+-            [          1           0           0         a^2     a^2 + 1]
+-            [          0           1           0         a^2           1]
+-            [          0           0           1 a^2 + a + 1       a + 1]
++            [          1           0       a + 1           0     a^2 + 1]
++            [          0           1 a^2 + a + 1           0           a]
++            [          0           0           0           1 a^2 + a + 1]
+ 
+             sage: copy(A).echelon_form('builtin');
+-            [          1           0           0         a^2     a^2 + 1]
+-            [          0           1           0         a^2           1]
+-            [          0           0           1 a^2 + a + 1       a + 1]
++            [          1           0       a + 1           0     a^2 + 1]
++            [          0           1 a^2 + a + 1           0           a]
++            [          0           0           0           1 a^2 + a + 1]
+         """
+         if self._nrows == 0 or self._ncols == 0:
+             self.cache('in_echelon_form',True)
+@@ -996,14 +988,14 @@
+ 
+             sage: K.<a> = GF(2^3)
+             sage: A = random_matrix(K,3,3); A
+-            [      0   a + 1       1]
+-            [a^2 + a a^2 + a a^2 + a]
+-            [      a a^2 + 1   a + 1]
++            [        a^2       a + 1 a^2 + a + 1]
++            [      a + 1           0           1]
++            [      a + 1     a^2 + 1       a + 1]
+ 
+             sage: B = ~A; B
+-            [        a^2           0     a^2 + 1]
+-            [a^2 + a + 1         a^2 a^2 + a + 1]
+-            [      a + 1 a^2 + a + 1           a]
++            [a^2 + a + 1         a^2         a^2]
++            [      a + 1 a^2 + a + 1       a + 1]
++            [          a     a^2 + a a^2 + a + 1]
+             
+             sage: A*B
+             [1 0 0]
+@@ -1032,23 +1024,22 @@
+ 
+             sage: K.<a> = GF(2^3)
+             sage: A = random_matrix(K,3,3); A
+-            [      0   a + 1       1]
+-            [a^2 + a a^2 + a a^2 + a]
+-            [      a a^2 + 1   a + 1]
++            [        a^2       a + 1 a^2 + a + 1]
++            [      a + 1           0           1]
++            [      a + 1     a^2 + 1       a + 1]
+ 
+             sage: A.rescale_row(0, a , 0); A
+-            [      0 a^2 + a       a]
+-            [a^2 + a a^2 + a a^2 + a]
+-            [      a a^2 + 1   a + 1]
++            [  a + 1 a^2 + a a^2 + 1]
++            [  a + 1       0       1]
++            [  a + 1 a^2 + 1   a + 1]
+ 
+             sage: A.rescale_row(0,0,0); A
+             [      0       0       0]
+-            [a^2 + a a^2 + a a^2 + a]
+-            [      a a^2 + 1   a + 1]
++            [  a + 1       0       1]
++            [  a + 1 a^2 + 1   a + 1]
+         """        
+-        cdef m4ri_word x = <m4ri_word>(<M4RIE__FiniteField*>self.cc.objectptr).log2pol((<FiniteField_givaroElement>multiple).element)
+-        cdef m4ri_word *X = self._entries.finite_field.mul[x]
+-        mzed_rescale_row(self._entries, row, start_col, X) 
++        cdef m4ri_word x = poly_to_word(multiple)
++        mzed_rescale_row(self._entries, row, start_col, x)
+ 
+ 
+     cdef add_multiple_of_row_c(self,  Py_ssize_t row_to, Py_ssize_t row_from, multiple, Py_ssize_t start_col):
+@@ -1066,19 +1057,18 @@
+ 
+             sage: K.<a> = GF(2^3)
+             sage: A = random_matrix(K,3,3); A
+-            [      0   a + 1       1]
+-            [a^2 + a a^2 + a a^2 + a]
+-            [      a a^2 + 1   a + 1]
++            [        a^2       a + 1 a^2 + a + 1]
++            [      a + 1           0           1]
++            [      a + 1     a^2 + 1       a + 1]
+ 
+             sage: A.add_multiple_of_row(0,1,a,0); A
+-            [a^2 + a + 1         a^2     a^2 + a]
+-            [    a^2 + a     a^2 + a     a^2 + a]
+-            [          a     a^2 + 1       a + 1]
++            [      a   a + 1 a^2 + 1]
++            [  a + 1       0       1]
++            [  a + 1 a^2 + 1   a + 1]
+         """
+         
+-        cdef m4ri_word x = <m4ri_word>(<M4RIE__FiniteField*>self.cc.objectptr).log2pol((<FiniteField_givaroElement>multiple).element)
+-        cdef m4ri_word *X = self._entries.finite_field.mul[x]
+-        mzed_add_multiple_of_row(self._entries, row_to, self._entries, row_from, X, start_col)
++        cdef m4ri_word x = poly_to_word(multiple)
++        mzed_add_multiple_of_row(self._entries, row_to, self._entries, row_from, x, start_col)
+ 
+ 
+     cdef swap_rows_c(self, Py_ssize_t row1, Py_ssize_t row2):
+@@ -1095,14 +1085,14 @@
+             sage: K.<a> = GF(2^3)
+             sage: A = random_matrix(K,3,3)
+             sage: A
+-            [      0   a + 1       1]
+-            [a^2 + a a^2 + a a^2 + a]
+-            [      a a^2 + 1   a + 1]
++            [        a^2       a + 1 a^2 + a + 1]
++            [      a + 1           0           1]
++            [      a + 1     a^2 + 1       a + 1]
+ 
+             sage: A.swap_rows(0,1); A
+-            [a^2 + a a^2 + a a^2 + a]
+-            [      0   a + 1       1]
+-            [      a a^2 + 1   a + 1]
++            [      a + 1           0           1]
++            [        a^2       a + 1 a^2 + a + 1]
++            [      a + 1     a^2 + 1       a + 1]
+ 
+         """
+         mzed_row_swap(self._entries, row1, row2)
+@@ -1121,14 +1111,14 @@
+             sage: K.<a> = GF(2^3)
+             sage: A = random_matrix(K,3,3)
+             sage: A
+-            [      0   a + 1       1]
+-            [a^2 + a a^2 + a a^2 + a]
+-            [      a a^2 + 1   a + 1]
++            [        a^2       a + 1 a^2 + a + 1]
++            [      a + 1           0           1]
++            [      a + 1     a^2 + 1       a + 1]
+ 
+             sage: A.swap_columns(0,1); A
+-            [  a + 1       0       1]
+-            [a^2 + a a^2 + a a^2 + a]
+-            [a^2 + 1       a   a + 1]
++            [      a + 1         a^2 a^2 + a + 1]
++            [          0       a + 1           1]
++            [    a^2 + 1       a + 1       a + 1]
+ 
+             sage: A = random_matrix(K,4,16)
+ 
+@@ -1161,19 +1151,19 @@
+             sage: MS = MatrixSpace(K,3,3)
+             sage: A = random_matrix(K,3,3)
+             sage: B = A.augment(MS(1)); B
+-            [      a^2 + 1 a^3 + a^2 + a   a^3 + a + 1             1             0             0]
+-            [        a + 1         a + 1         a + 1             0             1             0]
+-            [      a^3 + a     a^3 + a^2 a^3 + a^2 + a             0             0             1]
++            [              a^2       a^3 + a + 1 a^3 + a^2 + a + 1                 1                 0                 0]
++            [            a + 1               a^3                 1                 0                 1                 0]
++            [      a^3 + a + 1     a^3 + a^2 + 1             a + 1                 0                 0                 1]
+ 
+             sage: B.echelonize(); B
+-            [            1             0             0 a^3 + a^2 + 1 a^3 + a^2 + 1       a^2 + a]
+-            [            0             1             0       a^3 + 1       a^2 + 1       a^2 + 1]
+-            [            0             0             1           a^2       a^2 + a         a + 1]
++            [                1                 0                 0           a^2 + a           a^3 + 1           a^3 + a]
++            [                0                 1                 0     a^3 + a^2 + a a^3 + a^2 + a + 1           a^2 + a]
++            [                0                 0                 1             a + 1               a^3               a^3]
+ 
+             sage: C = B.matrix_from_columns([3,4,5]); C
+-            [a^3 + a^2 + 1 a^3 + a^2 + 1       a^2 + a]
+-            [      a^3 + 1       a^2 + 1       a^2 + 1]
+-            [          a^2       a^2 + a         a + 1]
++            [          a^2 + a           a^3 + 1           a^3 + a]
++            [    a^3 + a^2 + a a^3 + a^2 + a + 1           a^2 + a]
++            [            a + 1               a^3               a^3]
+ 
+             sage: C == ~A
+             True
+@@ -1187,12 +1177,12 @@
+             sage: A = random_matrix(K,2,3)
+             sage: B = random_matrix(K,2,0)
+             sage: A.augment(B)
+-            [a^3 + 1       0     a^3]
+-            [      0 a^3 + a       a]
++            [          a^3 + 1       a^3 + a + 1 a^3 + a^2 + a + 1]
++            [          a^2 + a           a^2 + 1           a^2 + a]
+ 
+             sage: B.augment(A)
+-            [a^3 + 1       0     a^3]
+-            [      0 a^3 + a       a]
++            [          a^3 + 1       a^3 + a + 1 a^3 + a^2 + a + 1]
++            [          a^2 + a           a^2 + 1           a^2 + a]
+ 
+             sage: M = Matrix(K, 0, 0, 0)
+             sage: N = Matrix(K, 0, 19, 0)
+@@ -1233,38 +1223,38 @@
+ 
+             sage: K.<a> = GF(2^4)
+             sage: A = random_matrix(K,2,2); A
+-            [      a^2 + 1 a^3 + a^2 + a]
+-            [  a^3 + a + 1         a + 1]
++            [              a^2       a^3 + a + 1]
++            [a^3 + a^2 + a + 1             a + 1]
+             
+             sage: B = random_matrix(K,2,2); B
+-            [a^3 + 1       0]
+-            [    a^3       0]
++            [          a^3             1]
++            [  a^3 + a + 1 a^3 + a^2 + 1]
+ 
+             sage: A.stack(B)
+-            [      a^2 + 1 a^3 + a^2 + a]
+-            [  a^3 + a + 1         a + 1]
+-            [      a^3 + 1             0]
+-            [          a^3             0]
++            [              a^2       a^3 + a + 1]
++            [a^3 + a^2 + a + 1             a + 1]
++            [              a^3                 1]
++            [      a^3 + a + 1     a^3 + a^2 + 1]
+ 
+             sage: B.stack(A)
+-            [      a^3 + 1             0]
+-            [          a^3             0]
+-            [      a^2 + 1 a^3 + a^2 + a]
+-            [  a^3 + a + 1         a + 1]
++            [              a^3                 1]
++            [      a^3 + a + 1     a^3 + a^2 + 1]
++            [              a^2       a^3 + a + 1]
++            [a^3 + a^2 + a + 1             a + 1]
+ 
+         TESTS::
+ 
+             sage: A = random_matrix(K,0,3)
+             sage: B = random_matrix(K,3,3)
+             sage: A.stack(B)
+-            [                0     a^3 + a^2 + a     a^3 + a^2 + a]
+-            [    a^3 + a^2 + a         a^3 + a^2       a^3 + a + 1]
+-            [a^3 + a^2 + a + 1               a^3               a^2]
++            [            a + 1           a^3 + 1       a^3 + a + 1]
++            [a^3 + a^2 + a + 1           a^2 + a           a^2 + 1]
++            [          a^2 + a     a^3 + a^2 + a           a^2 + 1]
+ 
+             sage: B.stack(A)
+-            [                0     a^3 + a^2 + a     a^3 + a^2 + a]
+-            [    a^3 + a^2 + a         a^3 + a^2       a^3 + a + 1]
+-            [a^3 + a^2 + a + 1               a^3               a^2]
++            [            a + 1           a^3 + 1       a^3 + a + 1]
++            [a^3 + a^2 + a + 1           a^2 + a           a^2 + 1]
++            [          a^2 + a     a^3 + a^2 + a           a^2 + 1]
+ 
+             sage: M = Matrix(K, 0, 0, 0)
+             sage: N = Matrix(K, 19, 0, 0)
+@@ -1419,45 +1409,45 @@
+         
+             sage: K.<a> = GF(2^2)
+             sage: A = random_matrix(K, 5, 5); A
+-            [    0     1     1     0     0]
+-            [    0     a a + 1     1     a]
+-            [    1     1 a + 1     a a + 1]
+-            [    0     1     1     1 a + 1]
+-            [    1     0     a     1     1]
++            [    0 a + 1 a + 1 a + 1     0]
++            [    1 a + 1     1 a + 1     1]
++            [a + 1 a + 1     a     1     a]
++            [    a     1 a + 1     1     0]
++            [    a     1 a + 1 a + 1     0]
+ 
+             sage: A1,A0 = A.slice()
+             sage: A0
+-            [0 0 0 0 0]
+-            [0 1 1 0 1]
+-            [0 0 1 1 1]
+-            [0 0 0 0 1]
+-            [0 0 1 0 0]
++            [0 1 1 1 0]
++            [0 1 0 1 0]
++            [1 1 1 0 1]
++            [1 0 1 0 0]
++            [1 0 1 1 0]
+ 
+             sage: A1
+-            [0 1 1 0 0]
+-            [0 0 1 1 0]
+-            [1 1 1 0 1]
+-            [0 1 1 1 1]
+-            [1 0 0 1 1]
++            [0 1 1 1 0]
++            [1 1 1 1 1]
++            [1 1 0 1 0]
++            [0 1 1 1 0]
++            [0 1 1 1 0]
+ 
+             sage: A0[2,4]*a + A1[2,4], A[2,4]
+-            (a + 1, a + 1)
++            (a, a)
+ 
+             sage: K.<a> = GF(2^3)
+             sage: A = random_matrix(K, 5, 5); A
+-            [    a^2 + 1           0       a + 1           0           a]
+-            [          a       a + 1           a           1         a^2]
+-            [    a^2 + a           0           0     a^2 + 1       a + 1]
+-            [    a^2 + 1           0     a^2 + 1       a + 1           1]
+-            [a^2 + a + 1           1 a^2 + a + 1           0     a^2 + 1]
++            [      a + 1     a^2 + a           1           a     a^2 + a]
++            [      a + 1     a^2 + a         a^2         a^2     a^2 + 1]
++            [a^2 + a + 1 a^2 + a + 1           0 a^2 + a + 1     a^2 + 1]
++            [    a^2 + a           0 a^2 + a + 1           a           a]
++            [        a^2       a + 1           a     a^2 + 1 a^2 + a + 1]
+ 
+             sage: A0,A1,A2 = A.slice()
+             sage: A0
+             [1 0 1 0 0]
+-            [0 1 0 1 0]
+-            [0 0 0 1 1]
+-            [1 0 1 1 1]
+-            [1 1 1 0 1]
++            [1 0 0 0 1]
++            [1 1 0 1 1]
++            [0 0 1 0 0]
++            [0 1 0 1 1]
+ 
+         Slicing and clinging are inverse operations::
+ 
+diff --git a/sage/matrix/matrix_space.py b/sage/matrix/matrix_space.py
+--- a/sage/matrix/matrix_space.py
++++ b/sage/matrix/matrix_space.py
+@@ -962,7 +962,7 @@
+                 # elif R.order() < matrix_modn_dense.MAX_MODULUS:
+                 #     return matrix_modn_dense.Matrix_modn_dense
+                 return matrix_generic_dense.Matrix_generic_dense
+-            elif sage.rings.finite_rings.all.is_FiniteField(R) and R.characteristic() == 2 and R.order() <= 1024:
++            elif sage.rings.finite_rings.all.is_FiniteField(R) and R.characteristic() == 2 and R.order() <= 65536:
+                 return matrix_mod2e_dense.Matrix_mod2e_dense
+             elif sage.rings.polynomial.multi_polynomial_ring_generic.is_MPolynomialRing(R) and R.base_ring() in _Fields:
+                 return matrix_mpolynomial_dense.Matrix_mpolynomial_dense
+diff --git a/sage/rings/polynomial/multi_polynomial_sequence.py b/sage/rings/polynomial/multi_polynomial_sequence.py
+--- a/sage/rings/polynomial/multi_polynomial_sequence.py
++++ b/sage/rings/polynomial/multi_polynomial_sequence.py
+@@ -130,7 +130,7 @@
+     sage: A.rank()
+     4056
+     sage: A[4055]*v
+-    (k001*k002 + k001*k003)
++    (k001*k003)
+ 
+ TEST::
+ 
+@@ -447,17 +447,15 @@
+             sage: P = F.ring()
+             sage: I = F.ideal()
+             sage: I.elimination_ideal(P('s000*s001*s002*s003*w100*w101*w102*w103*x100*x101*x102*x103'))
+-            Ideal (k002 + (a^3 + a^2 + 1)*k003 + (a^3), 
+-                   k001 + (a^3 + a^2 + a + 1)*k003 + (a^3 + a^2 + a), 
+-                   k000 + (a + 1)*k003 + (a^2 + a + 1), 
+-                   k103 + (a^3 + a)*k003 + (a^3 + a), 
+-                   k102 + (a^2 + a + 1)*k003 + (a^3 + a^2 + a), 
+-                   k101 + (a^3)*k003 + (a^3), 
+-                   k100 + (a^3 + a + 1)*k003 + (a^2 + 1), 
+-                   k003^2 + (a + 1)*k003 + (a^2 + a + 1)) 
+-            of Multivariate Polynomial Ring in 
+-            k100, k101, k102, k103, x100, x101, x102, x103, w100, w101, w102, w103, 
+-            s000, s001, s002, s003, k000, k001, k002, k003 over Finite Field in a of size 2^4
++            Ideal (k002 + (a^3 + a + 1)*k003 + (a^2 + 1),
++                   k001 + (a^3)*k003, k000 + (a)*k003 + (a^2),
++                   k103 + k003 + (a^2 + a + 1),
++                   k102 + (a^3 + a + 1)*k003 + (a + 1),
++                   k101 + (a^3)*k003 + (a^2 + a + 1),
++                   k100 + (a)*k003 + (a),
++                   k003^2 + (a)*k003 + (a^2))
++            of Multivariate Polynomial Ring in k100, k101, k102, k103, x100, x101, x102, x103,
++            w100, w101, w102, w103, s000, s001, s002, s003, k000, k001, k002, k003 over Finite Field in a of size 2^4
+         """
+         return self._ring.ideal(tuple(self))
+ 
+diff --git a/sage/rings/polynomial/pbori.pyx b/sage/rings/polynomial/pbori.pyx
+--- a/sage/rings/polynomial/pbori.pyx
++++ b/sage/rings/polynomial/pbori.pyx
+@@ -5040,7 +5040,7 @@
+             sage: F,s = sr.polynomial_system()
+             sage: I = F.ideal()
+             sage: I.groebner_basis()
+-            Polynomial Sequence with 35 Polynomials in 36 Variables
++            Polynomial Sequence with 36 Polynomials in 36 Variables
+ 
+         TESTS:
+ 
+@@ -5231,20 +5231,7 @@
+             sage: F,s = sr.polynomial_system()
+             sage: I = F.ideal()
+             sage: I.interreduced_basis()
+-            [k100 + k003, 
+-            k101 + k003, 
+-            k102 + k003 + 1, 
+-            k103, x100 + k003, 
+-            x101, x102 + 1, 
+-            x103, w100 + 1, 
+-            w101 + k003, w102, 
+-            w103 + k003 + 1, 
+-            s000 + k003 + 1, 
+-            s001, s002 + 1, 
+-            s003, 
+-            k000 + 1, 
+-            k001 + k003 + 1, 
+-            k002]
++            [k100 + 1, k101 + k001 + 1, k102, k103 + 1, x100 + k001 + 1, x101 + k001, x102, x103 + k001, w100 + 1, w101 + k001 + 1, w102 + 1, w103 + 1, s000 + k001, s001 + k001 + 1, s002, s003 + k001 + 1, k000 + 1, k002 + 1, k003 + 1]
+         """
+         R = self.ring()
+ 
-trac_14353_fan_morphism_factoring.patch   
-trac_14353_auxiliary_methods.patch        
-trac_14353_toric_morphism_factoring.patch 
-trac_14291-v2.patch
-trac_14291_reviewer.patch
 trac_14319.patch
 trac_14319-from_list_to_domain.patch
 trac_14319_fix_fan_isomorphism.patch
 trac_14319-empty.patch
-13614_grouptable.patch
+m4rie_new_version.patch
+trac_14203_doctest.patch
+trac_14466_fix_type_repr.patch
 trac_14423_python_274.patch
-14426_doctest.patch
-14055_cleaner_sagelib.patch
-14055_simplify_env.patch
-trac_14371_dont_catch_runtimeerror.patch
+trac_14159_weak_value_triple_dict.patch
+trac_14159_use_cdef_get.patch
+trac_14486_set_coercion.patch
+trac_14479_cdd_error.patch
+trac_10037_polyhedron_bug.patch
+trac_12781_remove_cruft.patch
+trac14477.2.patch
+trac_14469_repr_graphics.patch
 trac_14394_face_fan_bug.patch
 trac_14394_reviewer.patch
 trac_14375_ansi_escapes_indication.2.patch
 trac_14014_parents_for_matrix_groups.patch
 trac_14014_parents_group_dependents.patch
 trac_14014_iterator.patch
-trac_12892_orbit_closure_morphism.patch     #+test
-trac_12892_toric_morphism_fibers.patch      #+test
-trac_12892_toric_morphism_divisors.patch    #+test
+trac_12892_orbit_closure_morphism.patch
+trac_12892_toric_morphism_fibers.patch
+trac_12892_toric_morphism_divisors.patch
+trac_14353_fan_morphism_factoring.patch   
+trac_14353_auxiliary_methods.patch        
+trac_14353_toric_morphism_factoring.patch 
 trac_12900_Demazure_roots.patch
 trac_xxxx_fiber_divisor_graph.patch
 trac_14357_lazy_everywhere.patch
 trac_3416_elliptic_curve_from_cubic_vb.patch
 trac_3416_jacobians.patch
 trac_3416_fixes.patch
-trac_13826_star_imports_race.patch
 trac_14201_ppl_doctest_fixes.patch
 trac_14015_affine_group.patch
 trac_x_matrix_groups.patch

File trac14477.2.patch

+# HG changeset patch
+# User R. Andrew Ohana <andrew.ohana@gmail.com>
+# Date 1366714685 25200
+# Node ID 0feb76b9914e1275bc798a4f8c04bd35d9d85e71
+# Parent  c8ae9724d3cfad1837a130d50ac5c83a811ec221
+sort graph database queries by graph6 column
+
+diff --git a/sage/graphs/graph_database.py b/sage/graphs/graph_database.py
+--- a/sage/graphs/graph_database.py
++++ b/sage/graphs/graph_database.py
+@@ -342,39 +342,39 @@
+             ------------------------------------------------------------
+             A_                   2                    [1, 1]              
+             BW                   3                    [1, 1, 2]           
++            CF                   4                    [1, 1, 1, 3]
+             CK                   4                    [1, 1, 1, 1]        
+-            CF                   4                    [1, 1, 1, 3]        
+             CL                   4                    [1, 1, 2, 2]        
+             CN                   4                    [1, 2, 2, 3]        
+-            D_K                  5                    [1, 1, 1, 1, 2]     
+             D?{                  5                    [1, 1, 1, 1, 4]     
+             D@s                  5                    [1, 1, 1, 2, 3]     
++            D@{                  5                    [1, 1, 2, 2, 4]
+             DBg                  5                    [1, 1, 2, 2, 2]     
++            DBk                  5                    [1, 1, 2, 3, 3]
++            DIk                  5                    [1, 2, 2, 2, 3]
++            DK[                  5                    [1, 2, 2, 2, 3]
++            D_K                  5                    [1, 1, 1, 1, 2]
+             D`K                  5                    [1, 1, 2, 2, 2]     
+-            D@{                  5                    [1, 1, 2, 2, 4]     
+-            DIk                  5                    [1, 2, 2, 2, 3]     
+-            DBk                  5                    [1, 1, 2, 3, 3]     
+-            DK[                  5                    [1, 2, 2, 2, 3]     
+-            E@Q?                 6                    [1, 1, 1, 1, 1, 1]  
+-            E_?w                 6                    [1, 1, 1, 1, 1, 3]  
+-            E?N?                 6                    [1, 1, 1, 1, 2, 2]  
+-            E_Cg                 6                    [1, 1, 1, 1, 2, 2]  
+             E?Bw                 6                    [1, 1, 1, 1, 1, 5]  
+             E?Fg                 6                    [1, 1, 1, 1, 2, 4]  
++            E?N?                 6                    [1, 1, 1, 1, 2, 2]
++            E?NG                 6                    [1, 1, 1, 1, 3, 3]
+             E@FG                 6                    [1, 1, 1, 2, 2, 3]  
+-            E?NG                 6                    [1, 1, 1, 1, 3, 3]  
+             E@N?                 6                    [1, 1, 2, 2, 2, 2]  
++            E@Q?                 6                    [1, 1, 1, 1, 1, 1]
++            E@QW                 6                    [1, 1, 1, 2, 2, 3]
+             E@YO                 6                    [1, 1, 2, 2, 2, 2]  
+-            E@QW                 6                    [1, 1, 1, 2, 2, 3]  
++            E_?w                 6                    [1, 1, 1, 1, 1, 3]
++            E_Cg                 6                    [1, 1, 1, 1, 2, 2]
+             E_Cw                 6                    [1, 1, 1, 2, 2, 3]  
+             E_Ko                 6                    [1, 1, 2, 2, 2, 2]  
++            F??^?                7                    [1, 1, 1, 1, 1, 2, 3]
++            F?LCG                7                    [1, 1, 1, 1, 2, 2, 2]
+             FK??W                7                    [1, 1, 1, 1, 1, 1, 2]
++            FK?GW                7                    [1, 1, 1, 1, 2, 2, 2]
+             F_?@w                7                    [1, 1, 1, 1, 1, 1, 4]
+-            F??^?                7                    [1, 1, 1, 1, 1, 2, 3]
+             F_?Hg                7                    [1, 1, 1, 1, 1, 2, 3]
+-            F?LCG                7                    [1, 1, 1, 1, 2, 2, 2]
+             F_?XO                7                    [1, 1, 1, 1, 2, 2, 2]
+-            FK?GW                7                    [1, 1, 1, 1, 2, 2, 2]
+         """
+         if graph_db == None: graph_db = GraphDatabase()
+         if query_dict is not None:
+@@ -475,6 +475,7 @@
+                                 # substitue disp_str and join_str back into self's query string
+                                 self.__query_string__ = re.sub('SELECT.*WHERE ', disp_str + join_str + \
+                                                                                                 'WHERE ', self.__query_string__)
++                                self.__query_string__ += ' ORDER BY graph_data.graph6'
+     
+     def query_iterator(self):
+         """
+@@ -485,31 +486,29 @@
+             sage: Q = GraphQuery(display_cols=['graph6'],num_vertices=7, diameter=5)
+             sage: for g in Q:
+             ...     print g.graph6_string()
++            F?`po
++            F?gqg
+             F@?]O
+             F@OKg
+-            F?`po
+-            F?gqg
+-            FIAHo
+             F@R@o
+             FA_pW
++            FEOhW
+             FGC{o
+-            FEOhW
+-        
++            FIAHo
+             sage: Q = GraphQuery(display_cols=['graph6'],num_vertices=7, diameter=5)
+             sage: it = iter(Q)
+             sage: while True:
+             ...     try: print it.next().graph6_string()
+             ...     except StopIteration: break 
++            F?`po
++            F?gqg
+             F@?]O
+             F@OKg
+-            F?`po
+-            F?gqg
+-            FIAHo
+             F@R@o
+             FA_pW
++            FEOhW
+             FGC{o
+-            FEOhW
+-
++            FIAHo
+         """
+         return iter(self.get_graphs_list())
+         
+@@ -549,9 +548,9 @@
+             C?                   4                    [0, 0, 0, 0]        
+             C@                   4                    [0, 0, 1, 1]        
+             CB                   4                    [0, 1, 1, 2]        
+-            CK                   4                    [1, 1, 1, 1]        
+             CF                   4                    [1, 1, 1, 3]        
+             CJ                   4                    [0, 2, 2, 2]        
++            CK                   4                    [1, 1, 1, 1]
+             CL                   4                    [1, 1, 2, 2]        
+             CN                   4                    [1, 2, 2, 3]        
+             C]                   4                    [2, 2, 2, 2]        
+@@ -574,9 +573,9 @@
+             C?                   24
+             C@                   4
+             CB                   2
+-            CK                   8
+             CF                   6
+             CJ                   6
++            CK                   8
+             CL                   2
+             CN                   2
+             C]                   8
+@@ -942,9 +941,9 @@
+             C?                   4                    [0, 0, 0, 0]        
+             C@                   4                    [0, 0, 1, 1]        
+             CB                   4                    [0, 1, 1, 2]        
+-            CK                   4                    [1, 1, 1, 1]        
+             CF                   4                    [1, 1, 1, 3]        
+             CJ                   4                    [0, 2, 2, 2]        
++            CK                   4                    [1, 1, 1, 1]
+             CL                   4                    [1, 1, 2, 2]        
+             CN                   4                    [1, 2, 2, 3]        
+             C]                   4                    [2, 2, 2, 2]        
+@@ -952,96 +951,96 @@
+             D??                  5                    [0, 0, 0, 0, 0]     
+             D?C                  5                    [0, 0, 0, 1, 1]     
+             D?K                  5                    [0, 0, 1, 1, 2]     
++            D?[                  5                    [0, 1, 1, 1, 3]
++            D?{                  5                    [1, 1, 1, 1, 4]
++            D@K                  5                    [0, 0, 2, 2, 2]
+             D@O                  5                    [0, 1, 1, 1, 1]     
+-            D?[                  5                    [0, 1, 1, 1, 3]     
+-            D@K                  5                    [0, 0, 2, 2, 2]     
+-            D_K                  5                    [1, 1, 1, 1, 2]     
+             D@S                  5                    [0, 1, 1, 2, 2]     
+-            D?{                  5                    [1, 1, 1, 1, 4]     
+             D@[                  5                    [0, 1, 2, 2, 3]     
+             D@s                  5                    [1, 1, 1, 2, 3]     
++            D@{                  5                    [1, 1, 2, 2, 4]
++            DBW                  5                    [0, 2, 2, 2, 2]
++            DB[                  5                    [0, 2, 2, 3, 3]
+             DBg                  5                    [1, 1, 2, 2, 2]     
+-            DBW                  5                    [0, 2, 2, 2, 2]     
+-            D`K                  5                    [1, 1, 2, 2, 2]     
+-            D@{                  5                    [1, 1, 2, 2, 4]     
+-            DB[                  5                    [0, 2, 2, 3, 3]     
++            DBk                  5                    [1, 1, 2, 3, 3]
+             DIk                  5                    [1, 2, 2, 2, 3]     
+-            DBk                  5                    [1, 1, 2, 3, 3]     
+             DK[                  5                    [1, 2, 2, 2, 3]     
+             DLo                  5                    [2, 2, 2, 2, 2]     
++            D_K                  5                    [1, 1, 1, 1, 2]
++            D`K                  5                    [1, 1, 2, 2, 2]
+             E???                 6                    [0, 0, 0, 0, 0, 0]  
+             E??G                 6                    [0, 0, 0, 0, 1, 1]  
+             E??W                 6                    [0, 0, 0, 1, 1, 2]  
++            E??w                 6                    [0, 0, 1, 1, 1, 3]
++            E?@w                 6                    [0, 1, 1, 1, 1, 4]
++            E?Bw                 6                    [1, 1, 1, 1, 1, 5]
++            E?CW                 6                    [0, 0, 0, 2, 2, 2]
+             E?C_                 6                    [0, 0, 1, 1, 1, 1]  
+-            E??w                 6                    [0, 0, 1, 1, 1, 3]  
+-            E?CW                 6                    [0, 0, 0, 2, 2, 2]  
+-            EG?W                 6                    [0, 1, 1, 1, 1, 2]  
+             E?Cg                 6                    [0, 0, 1, 1, 2, 2]  
+-            E@Q?                 6                    [1, 1, 1, 1, 1, 1]  
+-            E?@w                 6                    [0, 1, 1, 1, 1, 4]  
+             E?Cw                 6                    [0, 0, 1, 2, 2, 3]  
+             E?Dg                 6                    [0, 1, 1, 1, 2, 3]  
+-            E_?w                 6                    [1, 1, 1, 1, 1, 3]  
+-            E?LO                 6                    [0, 1, 1, 2, 2, 2]  
+-            E?N?                 6                    [1, 1, 1, 1, 2, 2]  
+-            E?Ko                 6                    [0, 0, 2, 2, 2, 2]  
+-            EGCW                 6                    [0, 1, 1, 2, 2, 2]  
+-            E_Cg                 6                    [1, 1, 1, 1, 2, 2]  
+-            E?Bw                 6                    [1, 1, 1, 1, 1, 5]  
+             E?Dw                 6                    [0, 1, 1, 2, 2, 4]  
+             E?Fg                 6                    [1, 1, 1, 1, 2, 4]  
++            E?Ko                 6                    [0, 0, 2, 2, 2, 2]
+             E?Kw                 6                    [0, 0, 2, 2, 3, 3]  
++            E?LO                 6                    [0, 1, 1, 2, 2, 2]
++            E?LW                 6                    [0, 1, 1, 2, 3, 3]
++            E?N?                 6                    [1, 1, 1, 1, 2, 2]
++            E?NG                 6                    [1, 1, 1, 1, 3, 3]
++            E@FG                 6                    [1, 1, 1, 2, 2, 3]
+             E@HW                 6                    [0, 1, 2, 2, 2, 3]  
+-            E@FG                 6                    [1, 1, 1, 2, 2, 3]  
+-            E?LW                 6                    [0, 1, 1, 2, 3, 3]  
+-            E?NG                 6                    [1, 1, 1, 1, 3, 3]  
+             E@N?                 6                    [1, 1, 2, 2, 2, 2]  
++            E@Ow                 6                    [0, 1, 2, 2, 2, 3]
++            E@Q?                 6                    [1, 1, 1, 1, 1, 1]
++            E@QW                 6                    [1, 1, 1, 2, 2, 3]
++            E@T_                 6                    [0, 2, 2, 2, 2, 2]
+             E@YO                 6                    [1, 1, 2, 2, 2, 2]  
+-            E@QW                 6                    [1, 1, 1, 2, 2, 3]  
+-            E@Ow                 6                    [0, 1, 2, 2, 2, 3]  
++            EG?W                 6                    [0, 1, 1, 1, 1, 2]
++            EGCW                 6                    [0, 1, 1, 2, 2, 2]
++            E_?w                 6                    [1, 1, 1, 1, 1, 3]
++            E_Cg                 6                    [1, 1, 1, 1, 2, 2]
+             E_Cw                 6                    [1, 1, 1, 2, 2, 3]  
+-            E@T_                 6                    [0, 2, 2, 2, 2, 2]  
+             E_Ko                 6                    [1, 1, 2, 2, 2, 2]  
+             F????                7                    [0, 0, 0, 0, 0, 0, 0]
+             F???G                7                    [0, 0, 0, 0, 0, 1, 1]
+             F???W                7                    [0, 0, 0, 0, 1, 1, 2]
++            F???w                7                    [0, 0, 0, 1, 1, 1, 3]
++            F??@w                7                    [0, 0, 1, 1, 1, 1, 4]
++            F??Bw                7                    [0, 1, 1, 1, 1, 1, 5]
++            F??GW                7                    [0, 0, 0, 0, 2, 2, 2]
+             F??G_                7                    [0, 0, 0, 1, 1, 1, 1]
+-            F???w                7                    [0, 0, 0, 1, 1, 1, 3]
+-            F??GW                7                    [0, 0, 0, 0, 2, 2, 2]
+-            F@??W                7                    [0, 0, 1, 1, 1, 1, 2]
+             F??Gg                7                    [0, 0, 0, 1, 1, 2, 2]
+-            F?Ca?                7                    [0, 1, 1, 1, 1, 1, 1]
+-            F??@w                7                    [0, 0, 1, 1, 1, 1, 4]
+             F??Gw                7                    [0, 0, 0, 1, 2, 2, 3]
+             F??Hg                7                    [0, 0, 1, 1, 1, 2, 3]
+-            FG??w                7                    [0, 1, 1, 1, 1, 1, 3]
+-            F??XO                7                    [0, 0, 1, 1, 2, 2, 2]
+-            F??Z?                7                    [0, 1, 1, 1, 1, 2, 2]
+-            F??Wo                7                    [0, 0, 0, 2, 2, 2, 2]
+-            F@?GW                7                    [0, 0, 1, 1, 2, 2, 2]
+-            FK??W                7                    [1, 1, 1, 1, 1, 1, 2]
+-            FG?Gg                7                    [0, 1, 1, 1, 1, 2, 2]
+-            F??Bw                7                    [0, 1, 1, 1, 1, 1, 5]
+             F??Hw                7                    [0, 0, 1, 1, 2, 2, 4]
+             F??Jg                7                    [0, 1, 1, 1, 1, 2, 4]
++            F??Wo                7                    [0, 0, 0, 2, 2, 2, 2]
++            F??Ww                7                    [0, 0, 0, 2, 2, 3, 3]
++            F??XO                7                    [0, 0, 1, 1, 2, 2, 2]
++            F??XW                7                    [0, 0, 1, 1, 2, 3, 3]
++            F??Z?                7                    [0, 1, 1, 1, 1, 2, 2]
++            F??ZG                7                    [0, 1, 1, 1, 1, 3, 3]
++            F??^?                7                    [1, 1, 1, 1, 1, 2, 3]
++            F?CJG                7                    [0, 1, 1, 1, 2, 2, 3]
++            F?CPW                7                    [0, 0, 1, 2, 2, 2, 3]
++            F?CZ?                7                    [0, 1, 1, 2, 2, 2, 2]
++            F?C_w                7                    [0, 0, 1, 2, 2, 2, 3]
++            F?Ca?                7                    [0, 1, 1, 1, 1, 1, 1]
++            F?CaW                7                    [0, 1, 1, 1, 2, 2, 3]
++            F?Ch_                7                    [0, 0, 2, 2, 2, 2, 2]
++            F?CqO                7                    [0, 1, 1, 2, 2, 2, 2]
++            F?LCG                7                    [1, 1, 1, 1, 2, 2, 2]
++            F@??W                7                    [0, 0, 1, 1, 1, 1, 2]
++            F@?GW                7                    [0, 0, 1, 1, 2, 2, 2]
++            FG??w                7                    [0, 1, 1, 1, 1, 1, 3]
++            FG?Gg                7                    [0, 1, 1, 1, 1, 2, 2]
++            FG?Gw                7                    [0, 1, 1, 1, 2, 2, 3]
++            FG?Wo                7                    [0, 1, 1, 2, 2, 2, 2]
++            FK??W                7                    [1, 1, 1, 1, 1, 1, 2]
++            FK?GW                7                    [1, 1, 1, 1, 2, 2, 2]
+             F_?@w                7                    [1, 1, 1, 1, 1, 1, 4]
+-            F??Ww                7                    [0, 0, 0, 2, 2, 3, 3]
+-            F?CPW                7                    [0, 0, 1, 2, 2, 2, 3]
+-            F?CJG                7                    [0, 1, 1, 1, 2, 2, 3]
+-            F??^?                7                    [1, 1, 1, 1, 1, 2, 3]
+-            F??XW                7                    [0, 0, 1, 1, 2, 3, 3]
+-            F??ZG                7                    [0, 1, 1, 1, 1, 3, 3]
+-            F?CZ?                7                    [0, 1, 1, 2, 2, 2, 2]
+             F_?Hg                7                    [1, 1, 1, 1, 1, 2, 3]
+-            F?CqO                7                    [0, 1, 1, 2, 2, 2, 2]
+-            F?CaW                7                    [0, 1, 1, 1, 2, 2, 3]
+-            F?LCG                7                    [1, 1, 1, 1, 2, 2, 2]
+-            F?C_w                7                    [0, 0, 1, 2, 2, 2, 3]
+-            FG?Gw                7                    [0, 1, 1, 1, 2, 2, 3]
+-            F?Ch_                7                    [0, 0, 2, 2, 2, 2, 2]
+-            FG?Wo                7                    [0, 1, 1, 2, 2, 2, 2]
+             F_?XO                7                    [1, 1, 1, 1, 2, 2, 2]
+-            FK?GW                7                    [1, 1, 1, 1, 2, 2, 2]
+         """
+         return GraphQuery(self, query_dict, display_cols, **kwds)
+         

File trac_10037_polyhedron_bug.patch

+# HG changeset patch
+# Parent 8b94030815e437644bfaae8bb1f825c7b352cfc1
+
+Add missing import statement
+
+diff --git a/sage/geometry/polyhedron/plot.py b/sage/geometry/polyhedron/plot.py
+--- a/sage/geometry/polyhedron/plot.py
++++ b/sage/geometry/polyhedron/plot.py
+@@ -596,6 +596,11 @@
+             sage: Projection(cube4).schlegel([1,0,0,0])
+             The projection of a polyhedron into 3 dimensions
+             sage: _.show()
++
++        TESTS::
++
++            sage: Projection(cube4).schlegel()
++            The projection of a polyhedron into 3 dimensions
+         """
+         if projection_direction == None:
+             for poly in self.polygons:
+@@ -605,6 +610,7 @@
+                     projection_direction = center
+                     break
+         if projection_direction == None:
++            from sage.rings.arith import primes_first_n
+             projection_direction = primes_first_n(self.polyhedron_ambient_dim)
+         return self.__call__(ProjectionFuncSchlegel(projection_direction, height = height))
+ 

File trac_12781_remove_cruft.patch

+# HG changeset patch
+# Parent 8b94030815e437644bfaae8bb1f825c7b352cfc1
+
+Remove some cruft
+
+diff --git a/sage/misc/sage_extension.py b/sage/misc/sage_extension.py
+--- a/sage/misc/sage_extension.py
++++ b/sage/misc/sage_extension.py
+@@ -397,10 +397,6 @@
+         # about a bad memory access in the pari_close() function.
+         #self.set_quit_hook()
+ 
+-        # These are things I'm not sure that we need to do anymore
+-        #self.deprecated()
+-
+-
+         if os.environ.get('SAGE_IMPORTALL', 'yes') != 'yes':
+             return
+ 
+@@ -486,13 +482,6 @@
+ 
+         preparser(True)
+ 
+-    def deprecated(self):
+-        """
+-        These are things I don't think we need to do anymore; are they used?
+-        """
+-        # I'm not sure this is ever needed; when would this not be ''?
+-        if sys.path[0]!='':
+-            sys.path.insert(0, '')
+ 
+ # from http://stackoverflow.com/questions/4103773/efficient-way-of-having-a-function-only-execute-once-in-a-loop
+ from functools import wraps

File trac_13826_star_imports_race.patch

-# HG changeset patch
-# Parent 00b3012077ca50e517bc175c0a568ad1c8b4ae4f
-
-Fix race condition when moving the star import cache
-
-diff --git a/sage/all.py b/sage/all.py
---- a/sage/all.py
-+++ b/sage/all.py
-@@ -63,6 +63,7 @@
- 
- from time                import sleep
- 
-+import sage.misc.lazy_import
- from sage.misc.all       import *         # takes a while
- 
- from sage.misc.sh import sh
-@@ -138,7 +139,7 @@
- from sage.ext.fast_callable  import fast_callable
- from sage.ext.fast_eval      import fast_float
- 
--from sage.sandpiles.all import *
-+sage.misc.lazy_import.lazy_import('sage.sandpiles.all', '*', globals())
- 
- from sage.tensor.all     import *
- 
-@@ -291,7 +292,6 @@
- #sage.structure.sage_object.register_unpickle_override('sage.categories.category_types', '', )
- 
- # Cache the contents of star imports.
--import sage.misc.lazy_import
- sage.misc.lazy_import.save_cache_file()
- 
- 
-diff --git a/sage/misc/lazy_import.pyx b/sage/misc/lazy_import.pyx
---- a/sage/misc/lazy_import.pyx
-+++ b/sage/misc/lazy_import.pyx
-@@ -39,7 +39,7 @@
- cdef extern from *:
-     cdef int Py_LT, Py_LE, Py_EQ, Py_NE, Py_GT, Py_GE
- 
--import os, shutil, tempfile, cPickle as pickle, operator
-+import os, tempfile, cPickle as pickle, operator
- import inspect
- import sageinspect
- 
-@@ -869,16 +869,25 @@
-     global star_imports
-     if star_imports is None:
-         star_imports = {}
--    _, tmp_file = tempfile.mkstemp()
--    pickle.dump(star_imports, open(tmp_file, "w"))
--    cache_dir = os.path.dirname(get_cache_file())
-+    cache_file = get_cache_file()
-+    cache_dir = os.path.dirname(cache_file)
-     try:
-         os.makedirs(cache_dir)
-     except OSError:
--        # Probably failed because directory already exists, but we make sure.
--        if not os.path.isdir(cache_dir):
-+        if not os.path.isdir(cache_dir): 
-             raise
--    shutil.move(tmp_file, get_cache_file())
-+    try:
-+        os.unlink(cache_file)
-+    except OSError:
-+        pass   # cache_file does not exist, fine
-+    # important: create temp dir in cache_dir (trac #13826) to move atomically
-+    _, tmp_file = tempfile.mkstemp(dir=cache_dir)
-+    with open(tmp_file, "w") as tmp:
-+        pickle.dump(star_imports, tmp)
-+    try:
-+        os.rename(tmp_file, cache_file)
-+    except OSError:
-+        pass   # Windows can end up here, ignore
- 
- def get_star_imports(module_name):
-     """
-@@ -892,14 +901,33 @@
-         True
-         sage: 'EllipticCurve' in get_star_imports('sage.schemes.all')
-         True
-+
-+    TESTS::
-+
-+        sage: import os, tempfile
-+        sage: fd, cache_file = tempfile.mkstemp()
-+        sage: os.write(fd, 'invalid')
-+        7
-+        sage: os.close(fd)
-+        sage: import sage.misc.lazy_import as lazy
-+        sage: lazy.get_cache_file = (lambda: cache_file)
-+        sage: lazy.star_imports = None
-+        sage: lazy.get_star_imports('sage.schemes.all')
-+        doctest:...: UserWarning: star_imports cache is corrupted
-+        [...]
-+        sage: os.remove(cache_file)
-     """
-     global star_imports
-     if star_imports is None:
--        cache_file = get_cache_file()
--        if os.path.exists(cache_file):
--            star_imports = pickle.load(open(cache_file))
--        else:
--            star_imports = {}
-+        try:
-+            with open(get_cache_file()) as cache_file:
-+                star_imports = pickle.load(cache_file)
-+        except IOError:        # file does not exist
-+            pass
-+        except Exception:  # unpickling failed
-+            import warnings
-+            warnings.warn('star_imports cache is corrupted')
-+        star_imports = {}
-     try:
-         return star_imports[module_name]
-     except KeyError:

File trac_14159_use_cdef_get.patch

+# HG changeset patch
+# User Simon King <simon.king@uni-jena.de>
+# Date 1362123171 -3600
+# Node ID 4ed99b32fd05bb4becf3535ce4a4a5444f817d59
+# Parent  1cc6aad13f0d62690736b2e6320880b0c858dcbc
+#14159: Use cdef methods to get faster access to values of a TripleDict
+
+diff --git a/sage/structure/parent_old.pyx b/sage/structure/parent_old.pyx
+--- a/sage/structure/parent_old.pyx
++++ b/sage/structure/parent_old.pyx
+@@ -129,7 +129,7 @@
+             self.init_coerce()
+         cdef object ret
+         try:
+-            ret = PyObject_GetItem(self._coerce_from_hash,S)
++            ret = self._coerce_from_hash.get(S)
+             return ret
+         except KeyError:
+             pass
+@@ -158,7 +158,7 @@
+                 mor = mor * sage_type.coerce_map_from(S)
+             
+         if mor is not None:
+-            self._coerce_from_hash[S] = mor # TODO: if this is None, could it be non-None in the future?
++            self._coerce_from_hash.set(S, mor) # TODO: if this is None, could it be non-None in the future?
+             
+         return mor
+         
+@@ -204,7 +204,7 @@
+         try:
+             if self._action_hash is None: # this is because parent.__init__() does not always get called
+                 self.init_coerce()
+-            return self._action_hash[S, op, self_on_left]
++            return self._action_hash.get(S, op, self_on_left)
+         except KeyError:
+             pass
+         if HAS_DICTIONARY(self):
+@@ -215,7 +215,7 @@
+             from sage.categories.action import Action
+             if not isinstance(action, Action):
+                 raise TypeError, "get_action_impl must return None or an Action"
+-            self._action_hash[S, op, self_on_left] = action
++            self._action_hash.set(S, op, self_on_left, action)
+         return action
+         
+     def get_action_impl(self, S, op, self_on_left):
+@@ -326,14 +326,14 @@
+             self._has_coerce_map_from = MonoDict(23)
+         else:
+             try:
+-                return self._has_coerce_map_from[S]
++                return self._has_coerce_map_from.get(S)
+             except KeyError:
+                 pass
+         if HAS_DICTIONARY(self):
+             x = self.has_coerce_map_from_impl(S)
+         else:
+             x = self.has_coerce_map_from_c_impl(S)
+-        self._has_coerce_map_from[S] = x
++        self._has_coerce_map_from.set(S, x)
+         return x
+ 
+     def has_coerce_map_from_impl(self, S):

File trac_14159_weak_value_triple_dict.patch

+# HG changeset patch
+# User Simon King <simon.king@uni-jena.de>
+# Date 1363025892 -3600
+# Node ID d10aa3f464c3f9f878e7e8f7e7a7cacfa9ab944b
+# Parent  02fbdf47d9b8c6d6bad9256009a28ce1965e99c2
+#14159: Optional support for weak values in Triple- and MonoDict. Safer callback.
+
+diff --git a/sage/categories/homset.py b/sage/categories/homset.py
+--- a/sage/categories/homset.py
++++ b/sage/categories/homset.py
+@@ -74,10 +74,11 @@
+ ###################################
+ # Use the weak "triple" dictionary
+ # introduced in trac ticket #715
++# with weak values, as introduced in
++# trac ticket #14159
+ 
+-from weakref import KeyedRef
+-from sage.structure.coerce_dict import signed_id, TripleDict
+-_cache = TripleDict(53)
++from sage.structure.coerce_dict import TripleDict
++_cache = TripleDict(53, weak_values=True)
+ 
+ def Hom(X, Y, category=None):
+     """
+@@ -216,7 +217,7 @@
+     global _cache
+     key = (X,Y,category)
+     try:
+-        H = _cache[key]()
++        H = _cache[key]
+     except KeyError:
+         H = None
+     if H is not None:
+@@ -244,7 +245,7 @@
+     # Now, as the category may have changed, we try to find the hom set in the cache, again:
+     key = (X,Y,category)
+     try:
+-        H = _cache[key]()
++        H = _cache[key]
+     except KeyError:
+         H = None
+     if H is not None:
+@@ -263,7 +264,7 @@
+     H = category.hom_category().parent_class(X, Y, category = category)
+             
+     ##_cache[key] = weakref.ref(H)
+-    _cache[key] = KeyedRef(H, _cache.eraser, (signed_id(X),signed_id(Y),signed_id(category)))
++    _cache[key] = H
+     return H
+ 
+ def hom(X, Y, f):
+diff --git a/sage/structure/coerce_dict.pxd b/sage/structure/coerce_dict.pxd
+--- a/sage/structure/coerce_dict.pxd
++++ b/sage/structure/coerce_dict.pxd
+@@ -2,6 +2,7 @@
+     cdef __weakref__
+     cdef Py_ssize_t _size
+     cdef buckets
++    cdef bint weak_values
+     cdef double threshold
+     cdef public MonoDictEraser eraser
+     cdef get(self, object k)
+@@ -14,6 +15,7 @@
+     cdef __weakref__
+     cdef Py_ssize_t _size
+     cdef buckets
++    cdef bint weak_values
+     cdef double threshold
+     cdef public TripleDictEraser eraser
+     cdef get(self, object k1, object k2, object k3)
+diff --git a/sage/structure/coerce_dict.pyx b/sage/structure/coerce_dict.pyx
+--- a/sage/structure/coerce_dict.pyx
++++ b/sage/structure/coerce_dict.pyx
+@@ -10,11 +10,12 @@
+ Containers for storing coercion data
+ 
+ This module provides :class:`TripleDict` and :class:`MonoDict`. These are
+-structures similar to ``WeakKeyDictionary`` in Python's weakref module,
+-and are optimized for lookup speed. The keys for :class:`TripleDict` consist
+-of triples (k1,k2,k3) and are looked up by identity rather than equality. The
+-keys are stored by weakrefs if possible. If any one of the components k1, k2,
+-k3 gets garbage collected, then the entry is removed from the :class:`TripleDict`.
++structures similar to :class:`~weakref.WeakKeyDictionary` in Python's weakref
++module, and are optimized for lookup speed. The keys for :class:`TripleDict`
++consist of triples (k1,k2,k3) and are looked up by identity rather than
++equality. The keys are stored by weakrefs if possible. If any one of the
++components k1, k2, k3 gets garbage collected, then the entry is removed from
++the :class:`TripleDict`.
+ 
+ Key components that do not allow for weakrefs are stored via a normal
+ refcounted reference. That means that any entry stored using a triple
+@@ -22,18 +23,21 @@
+ as an entry in a normal dictionary: Its existence in :class:`TripleDict`
+ prevents it from being garbage collected.
+ 
+-That container currently is used to store coercion and conversion maps
+-between two parents (:trac:`715`) and to store homsets of pairs of objects
+-of a category (:trac:`11521`). In both cases, it is essential that the parent
+-structures remain garbage collectable, it is essential that the data access
+-is faster than with a usual ``WeakKeyDictionary``, and we enforce the "unique
+-parent condition" in Sage (parent structures should be identical if they are
+-equal).
++That container currently is used to store coercion and conversion maps between
++two parents (:trac:`715`) and to store homsets of pairs of objects of a
++category (:trac:`11521`). In both cases, it is essential that the parent
++structures remain garbage collectable, it is essential that the data access is
++faster than with a usual :class:`~weakref.WeakKeyDictionary`, and we enforce
++the "unique parent condition" in Sage (parent structures should be identical
++if they are equal).
+ 
+ :class:`MonoDict` behaves similarly, but it takes a single item as a key. It
+ is used for caching the parents which allow a coercion map into a fixed other
+ parent (:trac:`12313`).
+ 
++By :trac:`14159`, :class:`MonoDict` and :class:`TripleDict` can be optionally
++used with weak references on the values.
++
+ """
+ include "../ext/python_list.pxi"
+ 
+@@ -178,14 +182,19 @@
+         cdef list buckets = D.buckets
+         if buckets is None:
+             return
+-        cdef Py_ssize_t h = r.key
++        cdef Py_ssize_t h
++        cdef int offset
++        h,offset = r.key
+         cdef list bucket = <object>PyList_GET_ITEM(buckets, (<size_t>h) % PyList_GET_SIZE(buckets))
+         cdef Py_ssize_t i
+         for i from 0 <= i < PyList_GET_SIZE(bucket) by 3:
+             if PyInt_AsSsize_t(PyList_GET_ITEM(bucket,i))==h:
+-                del bucket[i:i+3]
+-                D._size -= 1
+-                break
++                if PyList_GET_ITEM(bucket,i+offset)==<void *>r:
++                    del bucket[i:i+3]
++                    D._size -= 1
++                    break
++                else:
++                    break
+ 
+ cdef class TripleDictEraser:
+     """
+@@ -278,7 +287,8 @@
+         # stored key of the unique triple r() had been part of.
+         # We remove that unique triple from self.D
+         cdef Py_ssize_t k1,k2,k3
+-        k1,k2,k3 = r.key
++        cdef int offset
++        k1,k2,k3,offset = r.key
+         cdef Py_ssize_t h = (k1 + 13*k2 ^ 503*k3)
+         cdef list bucket = <object>PyList_GET_ITEM(buckets, (<size_t>h) % PyList_GET_SIZE(buckets))
+         cdef Py_ssize_t i
+@@ -286,9 +296,12 @@
+             if PyInt_AsSsize_t(PyList_GET_ITEM(bucket, i))==k1 and \
+                PyInt_AsSsize_t(PyList_GET_ITEM(bucket, i+1))==k2 and \
+                PyInt_AsSsize_t(PyList_GET_ITEM(bucket, i+2))==k3:
+-                del bucket[i:i+7]
+-                D._size -= 1
+-                break
++                if PyList_GET_ITEM(bucket, i+offset)==<void *>r:
++                    del bucket[i:i+7]
++                    D._size -= 1
++                    break
++                else:
++                    break
+ 
+ cdef class MonoDict:
+     """
+@@ -306,6 +319,8 @@
+     It is bare-bones in the sense that not all dictionary methods are
+     implemented.
+ 
++    IMPLEMENTATION:
++
+     It is implemented as a list of lists (hereafter called buckets). The bucket
+     is chosen according to a very simple hash based on the object pointer,
+     and each bucket is of the form [id(k1), r1, value1, id(k2), r2, value2, ...],
+@@ -317,8 +332,16 @@
+     In the latter case the presence of the key in the dictionary prevents it from
+     being garbage collected.
+ 
+-    To spread objects evenly, the size should ideally be a prime, and certainly
+-    not divisible by 2.
++    INPUT:
++
++    - ``size`` -- an integer, the initial number of buckets. To spread objects
++      evenly, the size should ideally be a prime, and certainly not divisible
++      by 2.
++    - ``data`` -- optional iterable defining initial data.
++    - ``threshold`` -- optional number, default `0.7`. It determines how frequently
++      the dictionary will be resized (large threshold implies rare resizing).
++    - ``weak_values`` -- optional bool (default False). If it is true, weak references
++      to the values in this dictionary will be used, when possible.
+ 
+     EXAMPLES::
+ 
+@@ -346,7 +369,7 @@
+     Not all features of Python dictionaries are available, but iteration over
+     the dictionary items is possible::
+ 
+-        sage: # for some reason the following fails in "make ptest"
++        sage: # for some reason the following failed in "make ptest"
+         sage: # on some installations, see #12313 for details
+         sage: sorted(L.iteritems()) # random layout
+         [(-15, 3), ('a', 1), ('ab', 2)]
+@@ -410,12 +433,57 @@
+         sage: len(LE)    # indirect doctest
+         1
+ 
+-    AUTHOR:
++    TESTS:
++
++    Here, we demonstrate the use of weak values.
++    ::
++
++        sage: M = MonoDict(13)
++        sage: MW = MonoDict(13, weak_values=True)
++        sage: class Foo: pass
++        sage: a = Foo()
++        sage: b = Foo()
++        sage: k = 1
++        sage: M[k] = a
++        sage: MW[k] = b
++        sage: M[k] is a
++        True
++        sage: MW[k] is b
++        True
++        sage: k in M
++        True
++        sage: k in MW
++        True
++
++    While ``M`` uses a strong reference to ``a``, ``MW`` uses a *weak*
++    reference to ``b``, and after deleting ``b``, the corresponding item of
++    ``MW`` will be removed during the next garbage collection::
++
++        sage: import gc
++        sage: del a,b
++        sage: _ = gc.collect()
++        sage: k in M
++        True
++        sage: k in MW
++        False
++        sage: len(MW)
++        0
++        sage: len(M)
++        1
++
++   Note that ``MW`` also accepts values that do not allow for weak references::
++
++        sage: MW[k] = int(5)
++        sage: MW[k]
++        5
++
++    AUTHORS:
+ 
+     - Simon King (2012-01)
+     - Nils Bruin (2012-08)
++    - Simon King (2013-02)
+     """
+-    def __init__(self, size, data=None, threshold=0.7):
++    def __init__(self, size, data=None, threshold=0.7, weak_values=False):
+         """
+         Create a special dict using singletons for keys.
+ 
+@@ -432,6 +500,7 @@
+         self.threshold = threshold
+         self.buckets = [[] for i from 0 <= i < size]
+         self._size = 0
++        self.weak_values = weak_values
+         self.eraser = MonoDictEraser(self)
+         if data is not None:
+             for k, v in data.iteritems():
+@@ -563,7 +632,7 @@