Trac #15668: implement the fixed complex of automorphisms of simplicial complexes

This is a useful tool to have, I think.

URL: http://trac.sagemath.org/15668
Reported by: chapoton
Ticket author(s): Frédéric Chapoton
Reviewer(s): Travis Scrimshaw
Trac #15762: Make R and its extensions build on ARM

Make R and its extensions build on ARM with broken regexp in libc.

URL: http://trac.sagemath.org/15762
Reported by: dimpase
Ticket author(s): Dmitrii Pasechnik
Reviewer(s): Jean-Pierre Flori
Trac #15787: Files needed in SAGE_ATLAS_LIB

Following the conversation on sage-release [1]. It looks like the files
libptcblas and libptf77blas are not actually required by Atlas. And
debian does not contain them anyway.

Nathann

[1] https://groups.google.com/d/msg/sage-release/oxGODejce_0/yuJp4ZM-
9ksJ

URL: http://trac.sagemath.org/15787
Reported by: ncohen
Ticket author(s): Nathann Cohen
Reviewer(s): Ralf Stephan
Trac #15482: Say very loud that LP variables are non-negative by default

As the title says. It has been reported once again. We make this
assumption because ALL lp solvers that we use make the same, but it does
not mean everybody knows it `T_T`

Nathann

URL: http://trac.sagemath.org/15482
Reported by: ncohen
Ticket author(s): Nathann Cohen
Reviewer(s): Punarbasu Purkayastha, Karl-Dieter Crisman, Thierry Monteil
Trac #15345: Laurent polynomial rings don't preserve coercion

{{{
sage: R = LaurentPolynomialRing(ZZ, 'x')
sage: T = LaurentPolynomialRing(QQ, 'x')
sage: R.gen() + T.gen()
------------------------------------------------------------------------
---
TypeError                                 Traceback (most recent call
last)
<ipython-input-3-dac3b0b430b6> in <module>()
----> 1 R.gen() + T.gen()

/home/darij/sage-5.13.beta0/local/lib/python2.7/site-
packages/sage/structure/element.so in
sage.structure.element.RingElement.__add__
(sage/structure/element.c:13884)()

/home/darij/sage-5.13.beta0/local/lib/python2.7/site-
packages/sage/structure/coerce.so in
sage.structure.coerce.CoercionModel_cache_maps.bin_op
(sage/structure/coerce.c:8169)()

TypeError: unsupported operand parent(s) for '+': 'Univariate Laurent
Polynomial Ring in x over Integer Ring' and 'Univariate Laurent
Polynomial Ring in x over Rational Field'
}}}
Compare with the more complicated:
{{{
sage: R = PolynomialRing(ZZ, 'x').fraction_field()
sage: T = PolynomialRing(QQ, 'x').fraction_field()
sage: R.gen() + T.gen()
2*x
}}}

URL: http://trac.sagemath.org/15345
Reported by: darij
Ticket author(s): Frédéric Chapoton, David Roe
Reviewer(s): Travis Scrimshaw
Trac #15755: Upgrade cython to version 0.20.1

Upstream tarball: [http://cython.org/release/Cython-0.20.1.tar.gz]

URL: http://trac.sagemath.org/15755
Reported by: ohanar
Ticket author(s): R. Andrew Ohana, Jeroen Demeyer
Reviewer(s): R. Andrew Ohana
Trac #9505: coeff(f,x*y) does not work

The following is ok:
{{{
sage: var('x,y,z')
sage: f=x*y*z^2
sage: f.coeff(z^2)
x*y
}}}
However the following is not:
{{{
sage: f.coeff(x*y)
0
}}}

URL: http://trac.sagemath.org/9505
Reported by: zimmerma
Ticket author(s): Paul Zimmermann
Reviewer(s): Ralf Stephan
Trac #9634: binomial does not accept variable when only in the lower argument

{{{
sage: var('k')
k
sage: binomial(x,3)
1/6*(x - 2)*(x - 1)*x
sage: binomial(3,k)
------------------------------------------------------------------------
---
TypeError: Either m or x-m must be an integer
}}}

This is a bug since
{{{
sage: binomial(x,k)
binomial(x, k)
}}}
works.

URL: http://trac.sagemath.org/9634
Reported by: Henryk.Trappmann
Ticket author(s): Burcin Erocal
Reviewer(s): Ralf Stephan
Trac #15575: Remove deprecated functions from symmetric functions

The class for each basis of the symmetric functions was deprecated from
the global name space in #5457 and the ticket was merged in sage-5.4.

The this ticket will remove the following functions:

 `kschur.py`

The way of accessing these functions since sage-5.4 is to get the basis
from within `SymmetricFunctions(R)`.

URL: http://trac.sagemath.org/15575
Reported by: zabrocki
Ticket author(s): Anne Schilling, Mike Zabrocki
Reviewer(s): Travis Scrimshaw
Trac #15827: Fast check for linear dependence

Currently I can check for linear dependence by
{{{
sage: V = QQ^4
sage: ld = lambda vecs: len(V.linear_dependence(ves) > 0
}}}
However this is relatively slow since it determines a basis of all such
linear dependencies. Also it only works for vector spaces. A faster way
to do a simple check is to construct a matrix of the vectors, echelonize
the matrix, and see if any of the resulting rows are 0.

URL: http://trac.sagemath.org/15827
Reported by: tscrim
Ticket author(s): Travis Scrimshaw
Reviewer(s): Marc Mezzarobba
Trac #15744: Speed up MPC multiplication

Add a patch from Paul Zimmermann which significantly speeds up MPC
multiplication (although it is still noticably slower than
`ComplexField` which is based on MPFR).

'''Timings''' (time in microseconds for 1 multiplication on an `Intel(R)
Core(TM) i7-2640M CPU @ 2.80GHz`):
||Prec (bits)||= `ComplexField` =||= `MPComplexField` (old)=||=
`MPComplexField` (new)=||
||53||0.53||1.09||0.81||
||128||0.56||1.18||0.90||
||360||0.77||1.47||1.12||
||1024||1.74||3.98||3.39||

URL: http://trac.sagemath.org/15744
Reported by: jdemeyer
Ticket author(s): Jeroen Demeyer
Reviewer(s): Jean-Pierre Flori
Trac #9870: Clean up Cliquer's spkg-install

The {{{spkg-install}}} file for Cliquer could do with a lot of cleaning
up. Some examples of the problems are:

 * There are flags set for the C++ and Fortran compilers, though the
code is only C.
 * There's code to check for a mix of Sun and GNU compilers, which is
pointless since there is only 1 compiler used.
 * Lots of unnecessary environment variables are set.
 * Use `make` instead of `$MAKE`.
 * Runs tests in `spkg-install` instead of `spkg-check`.

'''None of these issues are currently causing any problems, but should
be resolved at some point'''

URL: http://trac.sagemath.org/9870
Reported by: drkirkby
Ticket author(s): Jeroen Demeyer
Reviewer(s): Jean-Pierre Flori
Trac #15684: Remove support for SAGE_FORTRAN

In order to simplify the build system, let's remove support for
`SAGE_FORTRAN` and `SAGE_FORTRAN_LIB`. These environment variables have
been deprecated since Sage 5.3 (more than a year).

To remove all traces of `SAGE_FORTRAN` from the Sage sources, also #9870
and #15685 should be fixed.

URL: http://trac.sagemath.org/15684
Reported by: jdemeyer
Ticket author(s): Jeroen Demeyer
Reviewer(s): Jean-Pierre Flori
Trac #15446: GP interface confused by stack overflow when enlarging results vector

From Georgi Guninski on sage-support
(https://groups.google.com/forum/#!topic/sage-support/A_GilhiUAwM):
{{{
sage: gp("{T(n)=n+1}")
sage: for n in [ 1 .. 2**20]:
    a=gp.T(n)
    print n

#wait some time..
...
65535
65536
------------------------------------------------------------------------
---
TypeError

TypeError: Error executing code in GP:
CODE:
        sage[131074]=65537;
PARI/GP ERROR:
  ***   at top-level: sage[131074]=65537
  ***                     ^--------------
  ***   array index (131074) out of allowed range [1-131073].
}}}
after this trying:
{{{
sage: gp.T(1)
}}}
again raises exception.

After the above computation, the log file `.sage/gp-expect.log` ends
with
{{{
? sage[131070]=65535;
sage[131070]=65535;
? sage[131071]=T(sage[131070]);
sage[131071]=T(sage[131070]);
? sage=concat(sage, vector(131072,k,0));
sage=concat(sage, vector(131072,k,0));
  ***   at top-level: sage=concat(sage,vec
  ***                 ^--------------------
  ***   the PARI stack overflows !
  current stack size: 10000000 (9.537 Mbytes)
  [hint] you can increase GP stack with allocatemem()

? allocatemem()
allocatemem()
  ***   Warning: new stack size = 20000000 (19.073 Mbytes).
? sage=concat(sage, vector(131072,k,0));
sage=concat(sage, vector(131072,k,0));
? sage[131072]=65536;
sage[131072]=65536;
? sage[131073]=T(sage[131072]);
sage[131073]=T(sage[131072]);
? sage[131074]=65537;
sage[131074]=65537;
  ***   at top-level: sage[131074]=65537
  ***                     ^--------------
  ***   array index (131074) out of allowed range [1-131073].
?
}}}
It appears that the vector `sage` wasn't doubled correctly; probably it
got messed up by the failed `concat()`.

This could be related to #11017/#11018.

URL: http://trac.sagemath.org/15446
Reported by: pbruin
Ticket author(s): Peter Bruin
Reviewer(s): Alejandro Argaez
Trac #15822: Tropical semiring cannot exponentiate infinity

Just found this while experimenting with my own semirings:

{{{
sage: T = TropicalSemiring(QQ)
sage: T.infinity() ** 2
------------------------------------------------------------------------
---
TypeError                                 Traceback (most recent call
last)
<ipython-input-28-b94a4a077331> in <module>()
----> 1 T.infinity() ** Integer(2)

/scratch/sage-6.1.1/local/lib/python2.7/site-
packages/sage/rings/semirings/tropical_semiring.so in
sage.rings.semirings.tropical_semiring.TropicalSemiringElement.__pow__
(sage/rings/semirings/tropical_semiring.c:4218)()

/scratch/sage-6.1.1/local/lib/python2.7/site-
packages/sage/structure/element.so in
sage.structure.element.RingElement.__mul__
(sage/structure/element.c:14520)()

/scratch/sage-6.1.1/local/lib/python2.7/site-
packages/sage/structure/coerce.so in
sage.structure.coerce.CoercionModel_cache_maps.bin_op
(sage/structure/coerce.c:8150)()

TypeError: unsupported operand parent(s) for '*': 'Integer Ring' and
'<type 'NoneType'>'
}}}

Here is a way to solve this
(sage/rings/semirings/tropical_semiring.pyx):

{{{
    def __pow__(base, exp, dummy):
        """
        Return ``self`` to ``exp``.

        EXAMPLES::

            sage: T = TropicalSemiring(QQ)
            sage: elt = T(2)
            sage: elt**3
            6
            sage: elt**-2
            -4
            sage: elt**(3/7)
            6/7
            sage: elt**0
            0

            sage: elt = T.infinity()
            sage: elt**0
            0
            sage: elt**(1/2)
            +infinity
            sage: elt*33
            +infinity
        """
        cdef TropicalSemiringElement self, x
        self = base
        if self._val is None:
            if exp > 0:
                return self
            elif exp == 0:
                return self.parent().one()
            raise ZeroDivisionError("Tropical division by infinity")
        x = self._new()
        x._val = exp*self._val
        return x
}}}

Is this good? (I cannot upload branches from here -- "fatal: remote
error: access denied or repository not exported: /sage.git")

URL: http://trac.sagemath.org/15822
Reported by: darij
Ticket author(s): Darij Grinberg
Reviewer(s): Travis Scrimshaw
Trac #15841: sage.combinat.finite_state_machine: incorrect indent in docstring

There was an indentation error in the docstring of class
{{{sage.combinat.finite_state_machine.FiniteStateMachine}}}
starting at {{{TESTS::}}}.

URL: http://trac.sagemath.org/15841
Reported by: cheuberg
Ticket author(s): Clemens Heuberger
Reviewer(s): Daniel Krenn
Trac #5383: isinstance(PrincipalIdealDomain) should be replaced with a method .is_principal_ideal_domain()

This is the cause of things like:

{{{
sage: R.<x, y> = QQ[]
sage: M = R^2
sage: span(R, vector([1, 0]))
------------------------------------------------------------------------
---
TypeError                                 Traceback (most recent call
last)

/Users/ncalexan/.sage/temp/dhcp_v009_038.mobile.uci.edu/301/_Users_ncale
xan_Documents_School_rumely_polynomial_ring_as_module2_sage_142.py in
<module>()

/Users/ncalexan/sage-3.3.rc0/local/lib/python2.5/site-
packages/sage/modules/free_module.pyc in span(gens, base_ring, check,
already_echelonized)
    408
    409     if not isinstance(R,
principal_ideal_domain.PrincipalIdealDomain):
--> 410         raise TypeError, "The base_ring (= %s) must be a
principal ideal domain."%R
    411     if len(gens) == 0:
    412         return FreeModule(R, 0)

TypeError: The base_ring (= Multivariate Polynomial Ring in x, y over
Rational Field) must be a principal ideal domain.
}}}

Surprisingly few places where this bites us:

{{{
sage: search_src('PrincipalIdealDomain')
modules/free_module.py:        elif isinstance(base_ring,
principal_ideal_domain.PrincipalIdealDomain):
modules/free_module.py:    if not isinstance(R,
principal_ideal_domain.PrincipalIdealDomain):
modules/free_module.py:        if not isinstance(base_ring,
principal_ideal_domain.PrincipalIdealDomain):
modules/free_quadratic_module.py:    elif isinstance(base_ring,
principal_ideal_domain.PrincipalIdealDomain):
rings/all.py:from principal_ideal_domain import PrincipalIdealDomain,
is_PrincipalIdealDomain
rings/all.py:from principal_ideal_domain_element import
PrincipalIdealDomainElement, is_PrincipalIdealDomainElement
rings/ideal.py:    if isinstance(R,
sage.rings.principal_ideal_domain.PrincipalIdealDomain):
<snip>
}}}

URL: http://trac.sagemath.org/5383
Reported by: ncalexan
Ticket author(s): Mike Hansen
Reviewer(s): Ralf Stephan
Trac #10218: enhance dev manual on reviewing tickets

As the subject says. This is a follow-up to #10201. From
[https://groups.google.com/group/sage-
devel/browse_thread/thread/d83f8d87962f8a9f/ sage-devel], William Stein
announced this blog entry:

http://sagemath.blogspot.com/2010/10/how-to-referee-sage-trac-
tickets.html

It would be a shame if new developers of Sage could not easily find it.

With the switch to git, both sections on reviewing were streamlined. The
link to William's blog made in #10201 was presumably removed because it
talks about mercurial.

We make the following changes:
* add a short summary on top of the walkthrough section (see
https://en.wikipedia.org/wiki/Inverted_pyramid)
* add a paragraph about reviewer's patches to in-depth section
* refer with caveat to blog post, again, literature style

I will discuss these changes on the grounds of me having been bitten by
the absence of them.

URL: http://trac.sagemath.org/10218
Reported by: mvngu
Ticket author(s): Ralf Stephan
Reviewer(s): Jean-Pierre Flori
Trac #10095: Linear algebra with large integer matrices fails with RuntimeError

On my laptop (Ubuntu 64 bit, Intel T4400 CPU), integer matrices
(solving, calculating determinant, etc.) appear to be broken when they
get sufficiently large. I can't reproduce the problem on sage.math.

With a fresh install of the 4.5.3 release:

{{{
sage: MatrixSpace(ZZ,20,20)(1) \ MatrixSpace(ZZ,20,1).random_element()
20 x 1 dense matrix over Rational Field
sage: MatrixSpace(ZZ,200,200)(1) \
MatrixSpace(ZZ,200,1).random_element()
------------------------------------------------------------------------
---
RuntimeError                              Traceback (most recent call
last)

/home/fredrik/sage-4.5.3-linux-64bit-ubuntu_10.04.1_lts-
x86_64-Linux/<ipython console> in <module>()

/home/fredrik/sage-4.5.3-linux-64bit-ubuntu_10.04.1_lts-
x86_64-Linux/local/lib/python2.6/site-packages/sage/misc/preparser.py in
__mul__(self, right)
   1358             (0.0, 0.5, 1.0, 1.5, 2.0)
   1359         """
-> 1360         return self.left._backslash_(right)
   1361
   1362

/home/fredrik/sage-4.5.3-linux-64bit-ubuntu_10.04.1_lts-
x86_64-Linux/local/lib/python2.6/site-packages/sage/matrix/matrix2.so in
sage.matrix.matrix2.Matrix._backslash_ (sage/matrix/matrix2.c:2641)()

/home/fredrik/sage-4.5.3-linux-64bit-ubuntu_10.04.1_lts-
x86_64-Linux/local/lib/python2.6/site-packages/sage/matrix/matrix2.so in
sage.matrix.matrix2.Matrix.solve_right (sage/matrix/matrix2.c:3550)()

/home/fredrik/sage-4.5.3-linux-64bit-ubuntu_10.04.1_lts-
x86_64-Linux/local/lib/python2.6/site-
packages/sage/matrix/matrix_rational_dense.so in
sage.matrix.matrix_rational_dense.Matrix_rational_dense.rank
(sage/matrix/matrix_rational_dense.c:20600)()

/home/fredrik/sage-4.5.3-linux-64bit-ubuntu_10.04.1_lts-
x86_64-Linux/local/lib/python2.6/site-
packages/sage/matrix/matrix_integer_dense.so in
sage.matrix.matrix_integer_dense.Matrix_integer_dense.rank
(sage/matrix/matrix_integer_dense.c:24534)()

/home/fredrik/sage-4.5.3-linux-64bit-ubuntu_10.04.1_lts-
x86_64-Linux/local/lib/python2.6/site-
packages/sage/matrix/matrix_integer_dense.so in
sage.matrix.matrix_integer_dense.Matrix_integer_dense._rank_modp
(sage/matrix/matrix_integer_dense.c:24821)()

RuntimeError:
}}}

URL: http://trac.sagemath.org/10095
Reported by: fredrik.johansson
Ticket author(s): Travis Scrimshaw
Reviewer(s): Marc Mezzarobba
Trac #9494: marked mpoly_all() as not tested

Demo at SD23.5, also increases coverage!

----

Apply [attachment:trac_9494-doctest_mpoly_all.2.patch] to the Sage
library.

URL: http://trac.sagemath.org/9494
Reported by: demosd235
Ticket author(s): Robert Miller
Reviewer(s): Rob Beezer, Benjamin Jones, Ralf Stephan