GitLab

There are numerous `MemoryError` instances in doctesting
`gen_quadrangles_with_spread.pyx` with a final failure
{{{
----------------------------------------------------------------------
sage -t --long --warn-long 127.5 --random-seed=0
src/sage/combinat/designs/gen_quadrangles_with_spread.pyx  # Bad exit: 1
----------------------------------------------------------------------
Total time for all tests: 108.3 seconds
    cpu time: 0.0 seconds
    cumulative wall time: 0.0 seconds
}}}

See ticket #30223 for background.

URL: https://trac.sagemath.org/30517
Reported by: strogdon
Ticket author(s): Volker Braun, Frederic Chapoton
Reviewer(s): Dima Pasechnik

zlscherr ([https://gitlab.com/zlscherr @zlscherr]) opened a merge
request at sagemath/sage!51:
----
{{{
#!markdown
My system has qhull 8.0.0 installed.  Because Matplotlib
doesn't know about my system qhull it builds its own version.
This can cause runtime issues with Matplotlib trying to call
the wrong qhull library.  For example, this fixes the error that
```bash
$ ./sage -tp 8 --long src/sage/plot/plot3d/list_plot3d.py
```
produces
```bash
QH6249 qh_lib_check: Incorrect qhull library called.
Size of qhT for caller is 2896, but for library is 2792.

QH6256 qh_lib_check: Cannot continue.
Library 'qhull 7.2.0 (2015.2 2016/01/18)'
uses a static qhT (e.g., libqhull.so)
```
if the system has qhull 8.0.0 installed.
}}}

URL: https://trac.sagemath.org/31148
Reported by: galois
Ticket author(s): Zachary Scherr
Reviewer(s): Dima Pasechnik

{{{
sage: latex(EllipticCurve([0, -1, 0, -101781377,
-517919745247]).kodaira_symbol(2))
I_64^{*}
}}}

It should be `I_{64}^{*}`.

URL: https://trac.sagemath.org/31147
Reported by: roed
Ticket author(s): David Roe
Reviewer(s): Frédéric Chapoton, John Cremona, Samuel Lelièvre

fixing some lgtm warnings about mutation of default option values

plus a partial flake8 cleanup

URL: https://trac.sagemath.org/31144
Reported by: chapoton
Ticket author(s): Frédéric Chapoton
Reviewer(s): David Coudert

URL: https://trac.sagemath.org/31143
Reported by: chapoton
Ticket author(s): Frédéric Chapoton
Reviewer(s): David Coudert

URL: https://trac.sagemath.org/31140
Reported by: chapoton
Ticket author(s): Frédéric Chapoton
Reviewer(s): Travis Scrimshaw

In reponse to an [https://ask.sagemath.org/question/53294/installing-
optional-packages-infinite-loop/#54977 ask.sagemath question] about
package installation on windows, I linked to my documentation for a
from-source installation on WSL.

Emmanuel Charpentier requested that I added this to the official
documentation.

I've added a section on setting up WSL to en/installation/source.rst and
a section which covers the steps needed to launch sage in WSL from the
windows desktop or start menu to en/installation/launching.rst

URL: https://trac.sagemath.org/31138
Reported by: gh-sandyscott
Ticket author(s): Sandy Scott
Reviewer(s): Tobias Diez

Just a version bump for each of these packages.

- https://setuptools.readthedocs.io/en/latest/history.html
  - 50.0.1 added support for Python 3.10
  - 51.0.0 dropped support for Python < 3.6.
  - 51.1.0 contains a minor fix for use with pip 20.3 (#30589)

URL: https://trac.sagemath.org/31134
Reported by: jhpalmieri
Ticket author(s): John Palmieri
Reviewer(s): Matthias Koeppe

{{{
sage: Matrix(ZZ, sys.maxsize, sys.maxsize)
*** Error in `python': free(): invalid next size (fast):
0x0000000004d8be80 ***
------------------------------------------------------------------------
Erreur de segmentation (core dumped)
}}}

Upstream bugs:

- [https://github.com/wbhart/flint2/issues/433]

URL: https://trac.sagemath.org/24459
Reported by: jdemeyer
Ticket author(s): Dave Morris
Reviewer(s): Vincent Delecroix

Because there is no conversion implemented between some fields this
ticket adds fallback code that goes through a RR/CC intermediate.
Example:
{{{
sage: SR(CBF(1+I))._convert({'parent':CDF})
...
AttributeError: 'sage.rings.complex_double.ComplexDoubleField_class'
object has no attribute 'complex_field'
}}}

URL: https://trac.sagemath.org/24317
Reported by: rws
Ticket author(s): Ralf Stephan
Reviewer(s): Dave Morris

{{{
sage: bool(x*polylog(x,x)==0)
...
/home/ralf/sage/local/lib/python2.7/site-
packages/sage/symbolic/expression_conversions.pyc in composition(self,
ex, operator)
    644         #FIXME: consider stripping pyobjects() in ops
    645         if hasattr(operator, self.name_init + "evaled_"):
--> 646             return getattr(operator, self.name_init +
"evaled_")(*ops)
    647         else:
    648             ops = [self(_) for _ in ops]

/home/ralf/sage/local/lib/python2.7/site-packages/sage/functions/log.pyc
in _maxima_init_evaled_(self, *args)
    451
    452         n, x = args_maxima
--> 453         if int(n) in [1,2,3]:
    454             return 'li[%s](%s)'%(n, x)
    455         else:

ValueError: invalid literal for int() with base 10: '_SAGE_VAR_x'
}}}

URL: https://trac.sagemath.org/21907
Reported by: rws
Ticket author(s): Frédéric Chapoton
Reviewer(s): Dave Morris

This ticket implements `conjugate` more efficiently for matrices over
CDF and RDF. This speeds up taking the conjugate, and by extension
Hermitian transpose, a lot.

Before:

{{{
sage: A = matrix.random(CDF, 80)
sage: %timeit A.C
28.7 ms ± 628 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: %timeit A.H
30.2 ms ± 572 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
}}}

This is a performance bottleneck because it is much slower than matrix
multiplication for example, even though that would have worse
complexity.

After:

{{{
sage: A = matrix.random(CDF, 80)
sage: %timeit A.C
5.96 µs ± 36.9 ns per loop (mean ± std. dev. of 7 runs, 100000 loops
each)
sage: %timeit A.H
14 µs ± 59.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
}}}

URL: https://trac.sagemath.org/31283
Reported by: gh-mwageringel
Ticket author(s): Markus Wageringel
Reviewer(s): Travis Scrimshaw

We remove the `form` input for `add_connection_form` and
`set_connection_form` because it is deprecated since #30208.

URL: https://trac.sagemath.org/31273
Reported by: gh-mjungmath
Ticket author(s): Michael Jung
Reviewer(s): Eric Gourgoulhon

Make it clear that it will also take elements as input.

URL: https://trac.sagemath.org/31272
Reported by: tscrim
Ticket author(s): Travis Scrimshaw
Reviewer(s): John Palmieri

Trac #31270: Remove sage-location's "sage-force-relocate" mechanism, fix script to work without SAGE_ROOT

#21783 removes the last productive bit of `sage-location`. The only
thing that `sage-location` does now is write a warning if it notices
that the tree has moved.

We want to get rid of the whole mechanism completely.... (or reuse its
remains to implement #31076).

In this ticket, we remove a part of it, the "sage-force-relocate"
mechanism, which used to be invoked by `sage-spkg`.

We also fix the script so that it works in installations without
`SAGE_ROOT`. This is for the benefit of downstream packaging and #30913.

(When we finally get rid of `sage-location`, we can finally close
tickets #15146, #17479, #11755.)

This is also preparation of sorts for #31076, which proposes to add a
different relocation mechanism.

URL: https://trac.sagemath.org/31270
Reported by: mkoeppe
Ticket author(s): Matthias Koeppe, John Palmieri
Reviewer(s): John Palmieri, Matthias Koeppe

Reported on https://ask.sagemath.org/question/55365:
{{{
sage: a = SteenrodAlgebra(2).an_element()
sage: M = CombinatorialFreeModule(GF(2), ['s', 't', 'u'])
sage: s = M.basis()['s']
sage: tensor([a, s])
------------------------------------------------------------------------
---
KeyError                                  Traceback (most recent call
last)
~/sage/local/lib/python3.8/site-packages/sage/misc/cachefunc.pyx in
sage.misc.cachefunc.CachedMethodCaller.__call__
(build/cythonized/sage/misc/cachefunc.c:10303)()
   1942             try:
-> 1943                 return cache[k]
   1944             except TypeError:  # k is not hashable

KeyError: (((Category of supercocommutative super hopf algebras with
basis over Finite Field of size 2, Category of finite dimensional vector
spaces with basis over Finite Field of size 2),), ())

During handling of the above exception, another exception occurred:

AttributeError                            Traceback (most recent call
last)
<ipython-input-5-4fb6e8615dbd> in <module>
----> 1 tensor([a, s])

~/sage/local/lib/python3.8/site-
packages/sage/categories/covariant_functorial_construction.py in
__call__(self, args, **kwargs)
    221         assert(all( hasattr(arg, self._functor_name) for arg in
args))
    222         assert(len(args) > 0)
--> 223         return getattr(args[0], self._functor_name)(*args[1:],
**kwargs)
    224
    225 class FunctorialConstructionCategory(Category): # Should this be
CategoryWithBase?

~/sage/local/lib/python3.8/site-
packages/sage/categories/modules_with_basis.py in tensor(*elements)
   2105             assert(all(isinstance(element, Element) for element
in elements))
   2106             parents = [parent(element) for element in elements]
-> 2107             return tensor(parents)._tensor_of_elements(elements)
# good name???
   2108
   2109     class Homsets(HomsetsCategory):

~/sage/local/lib/python3.8/site-
packages/sage/categories/covariant_functorial_construction.py in
__call__(self, args, **kwargs)
    221         assert(all( hasattr(arg, self._functor_name) for arg in
args))
    222         assert(len(args) > 0)
--> 223         return getattr(args[0], self._functor_name)(*args[1:],
**kwargs)
    224
    225 class FunctorialConstructionCategory(Category): # Should this be
CategoryWithBase?

~/sage/local/lib/python3.8/site-
packages/sage/categories/super_algebras.py in tensor(*parents, **kwargs)
     85             """
     86             constructor = kwargs.pop('constructor',
tensor_signed)
---> 87             cat = constructor.category_from_parents(parents)
     88             return parents[0].__class__.Tensor(parents,
category=cat)
     89
[snip]
~/sage/local/lib/python3.8/site-
packages/sage/categories/covariant_functorial_construction.py in
category_from_category(self, category)
    191         # TODO: add support for parametrized functors
    192         """
--> 193         return getattr(category, self._functor_category)()
    194
    195     def _repr_(self):

AttributeError: 'VectorSpaces.WithBasis_with_category' object
 has no attribute 'SignedTensorProducts'
}}}

If this happens we should fall back on the usual tensor product.

URL: https://trac.sagemath.org/31266
Reported by: tscrim
Ticket author(s): Travis Scrimshaw
Reviewer(s): John Palmieri

and remove very old "temporary cruft" about this

URL: https://trac.sagemath.org/31265
Reported by: chapoton
Ticket author(s): Frédéric Chapoton
Reviewer(s): Travis Scrimshaw

For very large and challenging computations, most of the elements of the
face lattice contain rather few atoms/bits. With little changes to the
code, we can just collect the non zero chunks (64,128 or 256 bits).

RoaringBitmap performs better (starting with maybe 100,000 bits, but not
with less, as container contain 64k bits), but that would add an extra
dependency and make things more complicated.

To avoid code duplications, we also gather some functions in
`bitset_intrinsics.h` that work just the same (e.g. intersection and
union).
(This actually accounts for most changes by this ticket.)

Before (on #27103):

{{{
sage: P = polytopes.Birkhoff_polytope(5)
sage: C = CombinatorialPolyhedron(P)
sage: %time _ = C.f_vector()
CPU times: user 468 ms, sys: 0 ns, total: 468 ms
Wall time: 467 ms

sage: P = polytopes.Birkhoff_polytope(5)
sage: C = CombinatorialPolyhedron(P)
sage: %time _ = C.f_vector()
CPU times: user 440 ms, sys: 0 ns, total: 440 ms
Wall time: 439 ms

sage: P = polytopes.hypercube(14)
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time _ = C.f_vector()
CPU times: user 5.13 s, sys: 4.03 ms, total: 5.14 s
Wall time: 5.13 s
sage: P = polytopes.hypercube(15)
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time _ = C.f_vector()
CPU times: user 30 s, sys: 32 ms, total: 30 s
Wall time: 30 s

sage: P = polytopes.permutahedron(6)
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time _ = C.f_vector()
CPU times: user 1.68 ms, sys: 6 µs, total: 1.68 ms
Wall time: 1.69 ms
sage: P = polytopes.permutahedron(7)
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time _ = C.f_vector()
CPU times: user 89.1 ms, sys: 4 µs, total: 89.1 ms
Wall time: 88.9 ms

sage: P = polytopes.permutahedron(8, backend='normaliz')
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time _ = C.f_vector()
CPU times: user 14.2 s, sys: 8 ms, total: 14.2 s
Wall time: 14.2 s

sage: P = polytopes.associahedron(['A', 11], backend='normaliz')
sage: C = CombinatorialPolyhedron(P)
sage: %time _ = C.f_vector()
CPU times: user 24.3 s, sys: 8.01 ms, total: 24.3 s
Wall time: 24.3 s
}}}

After:

{{{
# Slight slowdown for few atoms.
sage: P = polytopes.Birkhoff_polytope(5)
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 475 ms, sys: 0 ns, total: 475 ms
Wall time: 474 ms
(1, 120, 5040, 50250, 233400, 631700, 1113700, 1367040, 1220550, 817150,
419225, 167200, 52120, 12600, 2300, 300, 25, 1)

sage: P = polytopes.hypercube(14)
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time C.f_vector()
CPU times: user 1.67 s, sys: 0 ns, total: 1.67 s
Wall time: 1.66 s
(1, 16385, 131069, 487383, 1117948, 1769482, 2047331, 1788501, 1200342,
622908, 248963, 75361, 16640, 2470, 197, 1)
sage: P = polytopes.hypercube(15)
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time C.f_vector()
CPU times: user 7.28 s, sys: 8 ms, total: 7.28 s
Wall time: 7.28 s
(1, 32769, 278525, 1105876, 2723539, 4657926, 5866861, 5629624, 4196907,
2454738, 1128127, 404404, 110929, 22386, 3059, 226, 1)

sage: P = polytopes.permutahedron(6)
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time C.f_vector()
CPU times: user 1.44 ms, sys: 79 µs, total: 1.52 ms
Wall time: 1.52 ms
(1, 721, 1987, 1956, 808, 120, 1)
sage: P = polytopes.permutahedron(7)
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time C.f_vector()
CPU times: user 20.8 ms, sys: 0 ns, total: 20.8 ms
Wall time: 20.9 ms
(1, 5041, 16251, 19761, 11144, 2860, 267, 1)
sage: P = polytopes.permutahedron(8, backend='normaliz')
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time C.f_vector()
CPU times: user 616 ms, sys: 8 ms, total: 624 ms
Wall time: 623 ms
(1, 40321, 148899, 215690, 154215, 56022, 9489, 572, 1)

# No change for simplicial/simple polytopes.
sage: P = polytopes.associahedron(['A', 11], backend='normaliz')
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 24.3 s, sys: 16.3 ms, total: 24.3 s
Wall time: 24.3 s
(1, 208012, 1144066, 2735810, 3730650, 3197700, 1790712, 659736, 157080,
23100, 1925, 77, 1)
}}}

This is the last subsequent improvement in comparison to sage 8.9
mentioned in https://arxiv.org/abs/1905.01945.

Follow ups:
- Move things from `geometry/polyhedron/combinatorial_polyhedron` to a
more general location.
- Some renamings for lattices in general `face` -> `element`.
- Expose to simplical complexes.
- Expose to lattice of flats of matroids.

URL: https://trac.sagemath.org/31262
Reported by: gh-kliem
Ticket author(s): Jonathan Kliem
Reviewer(s): Travis Scrimshaw

(from #30922)

URL: https://trac.sagemath.org/31261
Reported by: mkoeppe
Ticket author(s): Matthias Koeppe
Reviewer(s): Jonathan Kliem

The [https://cmake.org/cmake/help/latest/release/3.19.html release
notes] promise improved support for Xcode 12 and for Apple silicon.

Previous update: to 3.18.2 in #30150

URL: https://trac.sagemath.org/31258
Reported by: mkoeppe
Ticket author(s): Matthias Koeppe
Reviewer(s): John Palmieri

The method `quo_rem` of `LaurentPolynomial_mpair` gives wrong answers:

{{{
sage: R.<x,y> = LaurentPolynomialRing(QQ)
sage: q, r = (1/x).quo_rem(y) ; q, r
(0, 1)
sage: q*y + r == 1/x
False
}}}

As remarked [https://groups.google.com/g/sage-devel/c/PhXn1WEShwA on
sage-devel] it is not clear which should be the preferred answer in this
case: both `(0, 1/x)` and `(1/(x*y), 0)` are correct because `y` is a
unit.

URL: https://trac.sagemath.org/31257
Reported by: etn40ff
Ticket author(s): Dave Morris
Reviewer(s): Salvatore Stella

after #31195

URL: https://trac.sagemath.org/31256
Reported by: chapoton
Ticket author(s): Frédéric Chapoton
Reviewer(s): Travis Scrimshaw

There are some missing checks from #30288 and #30274. They will be added
here.

URL: https://trac.sagemath.org/31255
Reported by: gh-mjungmath
Ticket author(s): Michael Jung
Reviewer(s): Matthias Koeppe

{{{
sage: A = matrix.identity(QQ, 4)
sage: A._subdivisions
sage: A2 = A.change_ring(RDF)
sage: A2._subdivisions
( [ 0, 4 ], [ 0, 4 ] )
}}}
We should also disregard when being passed no subdivisions:
{{{
sage: A = matrix.identity(QQ, 4)
sage: A._subdivisions
sage: A.subdivide(A.subdivisions())
sage: A._subdivisions
( [ 0, 4 ], [ 0, 4 ] )
}}}

URL: https://trac.sagemath.org/31254
Reported by: tscrim
Ticket author(s): Travis Scrimshaw
Reviewer(s): Markus Wageringel

This package was removed because there was no upstream release (see
#26332), but the development is still ongoing
https://github.com/mkauers/ore_algebra and the developers follow the
Sage development.

We should be able to use a "pip" package source type, with a
`requirements.txt` pointing to a commit (or a tag) of the version that
works  with the given Sage release.

See the task #31164.

URL: https://trac.sagemath.org/31239
Reported by: tmonteil
Ticket author(s): Thierry Monteil
Reviewer(s): Matthias Koeppe

Trac #31216: tox.ini (local): Add environment variables to skip system package installs and other steps, add mechanism for a local interactive shell

(from #31064)

We add the following to the `local-...` environments:

- an environment variable that can be passed to tox to skip system
package installs, directly reusing a previously set up system
{{{
SKIP_SYSTEM_PKG_INSTALL=yes tox -e local-homebrew-macos-standard --
config.status
SKIP_SYSTEM_PKG_INSTALL=yes tox -e local-homebrew-macos-standard --
config.status
}}}
  This can save time and also give developers more control for
experiments with system packages.

- a target that gives an interactive shell in the tox environment:
{{{
tox -e local-homebrew-macos-standard -- bash
tox -e local-direct -- bash
SKIP_SYSTEM_PKG_INSTALL=yes SKIP_BOOTSTRAP=1 SKIP_CONFIGURE=1 tox -e
local-homebrew-macos-standard -- bash
}}}

URL: https://trac.sagemath.org/31216
Reported by: mkoeppe
Ticket author(s): Matthias Koeppe
Reviewer(s): Tobias Diez

Currently, the dense graphs backend redefines bitsets. We change the
type to `binary_matrix_t`.

This mainly simplifies the code and lets dense graphs use future
improvements of bitsets, but it also speeds up direct functions with the
backend.

Realloc is a bit slower though.

We benefit from the improvements of the binary matrix data structure
done in #31200 and #31207, including the addition of reallocation
method.

Before:

{{{
sage: set_random_seed(0)
sage: edges = [(randint(0,1000), randint(0,1000)) for _ in
range(100000)]
sage: %timeit G = Graph(edges, sparse=False, loops=True)
19.4 ms ± 752 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
sage: G = Graph(edges, sparse=False, loops=True)
sage: %timeit _ = G.copy(sparse=True)
49.2 ms ± 312 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: %timeit _ = G.copy(sparse=False)
6.18 ms ± 5.74 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
}}}

After:
{{{
sage: set_random_seed(0)
sage: edges = [(randint(0,1000), randint(0,1000)) for _ in
range(100000)]
sage: %timeit G = Graph(edges, sparse=False, loops=True)
19.2 ms ± 55.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
sage: G = Graph(edges, sparse=False, loops=True)
sage: %timeit _ = G.copy(sparse=True)
47.3 ms ± 396 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: %timeit _ = G.copy(sparse=False)
3.64 ms ± 15.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
}}}

URL: https://trac.sagemath.org/31197
Reported by: gh-kliem
Ticket author(s): Jonathan Kliem
Reviewer(s): David Coudert

I suggest some code improvements for the documentation (adding a note
that an attribute à la `_is_immutable` is required to check
immutability), an additional method `_require_immutable` (to require
immutability in cases like hash functions) and Python 3 compatibility
(using `format` instead of `%` as recommended in Python's doc).

URL: https://trac.sagemath.org/31196
Reported by: gh-mjungmath
Ticket author(s): Michael Jung
Reviewer(s): Travis Scrimshaw

In #30181, the class `ModuleElementWithMutability` was introduced. In an
effort to set a standard in Sage, as per
`sage.structure.mutability.Mutability`, we rename the `_is_mutable` to
`_is_immutable`. As such, this class is not currently compatible with
the wrappers `sage.structure.mutability.require_mutable` and
`sage.structure.nutability.require_immutable`, see as well #31196.

The same holds for other classes whose mutability attribute will be
unified here.

URL: https://trac.sagemath.org/31194
Reported by: gh-mjungmath
Ticket author(s): Michael Jung
Reviewer(s): Travis Scrimshaw

Removing some duplicate information and making the code more efficient.

URL: https://trac.sagemath.org/31121
Reported by: tscrim
Ticket author(s): Travis Scrimshaw
Reviewer(s): Frédéric Chapoton

(from #30296)

Jupyter ships with its own copy of mathjax already.

We remove the installation of the symlink to our copy of `mathjax` from
the `nbextensions` directory and the corresponding configuration item
from the notebook.

See also a related documentation issue in #24367.

URL: https://trac.sagemath.org/31035
Reported by: mkoeppe
Ticket author(s): Matthias Koeppe
Reviewer(s): Antonio Rojas

#27122 enabled `-march=native` by default. This allows using intrinsics
for Intel and AMD processors (unless the user specified different
`CFLAGS` or `CXXFLAGS` differently).

Bitsets allocated using `MemoryAllocator` are overaligned allocated.
This is not the case otherwise and there are several reasons not to do
so for now:
- More memory usage especially for small bitsets (`bitset_t` itself is
rather small).
- It makes `realloc` a lot harder.
- There seems to be only about 10 percent loss when data is not
overaligned.
- There seems to be only about 1 percent performance loss, when the data
is overaligned but the code is not customized for it
(`_mm256_loadu_si256` instead of `_mm256_load_si256` etc).

See https://software.intel.com/sites/landingpage/IntrinsicsGuide for
details about the instructions.

The emptyness check as it is seems be really fast and it appears
pointless to beat it using intrinsics.

A few minor improvements in the bitset frontend of bitsets were also
made.

Timings without intrinsics (should be exactly the same as without this
ticket as the code almost did not change):

{{{
sage: B = Bitset((randint(0,2**20) for _ in range(2**19)))
sage: %timeit B == B
7.93 µs ± 5.71 ns per loop (mean ± std. dev. of 7 runs, 100000 loops
each)
sage: Bop = ~B
sage: %timeit B.isdisjoint(Bop)
8.11 µs ± 4.43 ns per loop (mean ± std. dev. of 7 runs, 100000 loops
each)
sage: %timeit B.issubset(B)
7.98 µs ± 7.64 ns per loop (mean ± std. dev. of 7 runs, 100000 loops
each)

sage: B2 = ~Bop
sage: %timeit B2.intersection_update(B)
7.22 µs ± 20 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
sage: %timeit B2.union(B)
14.6 µs ± 5.3 ns per loop (mean ± std. dev. of 7 runs, 100000 loops
each)
sage: %timeit B.symmetric_difference(Bop)
14 µs ± 9.34 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
sage: %timeit B.difference_update(Bop)
7.2 µs ± 19.2 ns per loop (mean ± std. dev. of 7 runs, 100000 loops
each)

sage: P = polytopes.hypercube(14)
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time C.f_vector()
CPU times: user 12.8 s, sys: 7.98 ms, total: 12.8 s
Wall time: 12.8 s
(1, 16385, 131069, 487383, 1117948, 1769482, 2047331, 1788501, 1200342,
622908, 248963, 75361, 16640, 2470, 197, 1)

sage: P = polytopes.Birkhoff_polytope(5)
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 581 ms, sys: 0 ns, total: 581 ms
Wall time: 580 ms
(1, 120, 5040, 50250, 233400, 631700, 1113700, 1367040, 1220550, 817150,
419225, 167200, 52120, 12600, 2300, 300, 25, 1)

sage: P = polytopes.associahedron(['A', 11], backend='normaliz')
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 38 s, sys: 20.2 ms, total: 38 s
Wall time: 38 s
(1, 208012, 1144066, 2735810, 3730650, 3197700, 1790712, 659736, 157080,
23100, 1925, 77, 1)
}}}

With SSE4.1 (some of them would also run just with SSE2, but already
SSE4.1 is 2008):
{{{
sage: B = Bitset((randint(0,2**20) for _ in range(2**19)))
sage: %timeit B == B
7.91 µs ± 3.03 ns per loop (mean ± std. dev. of 7 runs, 100000 loops
each)
sage: Bop = ~B
sage: %timeit B.isdisjoint(Bop)
5.1 µs ± 6.09 ns per loop (mean ± std. dev. of 7 runs, 100000 loops
each)
sage: %timeit B.issubset(B)
4.71 µs ± 5.07 ns per loop (mean ± std. dev. of 7 runs, 100000 loops
each)

sage: B2 = ~Bop
sage: %timeit B2.intersection_update(B)
5.57 µs ± 9.94 ns per loop (mean ± std. dev. of 7 runs, 100000 loops
each)
sage: %timeit B2.union(B)
11.9 µs ± 5.64 ns per loop (mean ± std. dev. of 7 runs, 100000 loops
each)
sage: %timeit B.symmetric_difference(Bop)
12.4 µs ± 7.06 ns per loop (mean ± std. dev. of 7 runs, 100000 loops
each)
sage: %timeit B.difference_update(Bop)
4.66 µs ± 38.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops
each)

sage: P = polytopes.hypercube(14)
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time C.f_vector()
CPU times: user 7.98 s, sys: 4 ms, total: 7.99 s
Wall time: 7.98 s
(1, 16385, 131069, 487383, 1117948, 1769482, 2047331, 1788501, 1200342,
622908, 248963, 75361, 16640, 2470, 197, 1)

sage: P = polytopes.Birkhoff_polytope(5)
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 466 ms, sys: 0 ns, total: 466 ms
Wall time: 466 ms
(1, 120, 5040, 50250, 233400, 631700, 1113700, 1367040, 1220550, 817150,
419225, 167200, 52120, 12600, 2300, 300, 25, 1)

sage: P = polytopes.associahedron(['A', 11], backend='normaliz')
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 26.8 s, sys: 8.09 ms, total: 26.8 s
Wall time: 26.8 s
(1, 208012, 1144066, 2735810, 3730650, 3197700, 1790712, 659736, 157080,
23100, 1925, 77, 1)
}}}

With AVX:
{{{
sage: B = Bitset((randint(0,2**20) for _ in range(2**19)))
sage: %timeit B == B
3.99 µs ± 2.46 ns per loop (mean ± std. dev. of 7 runs, 100000 loops
each)
sage: Bop = ~B
sage: %timeit B.isdisjoint(Bop)
3.38 µs ± 12.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops
each)
sage: %timeit B.issubset(B)
3.05 µs ± 2.4 ns per loop (mean ± std. dev. of 7 runs, 100000 loops
each)

sage: P = polytopes.hypercube(14)
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time C.f_vector()
CPU times: user 5.27 s, sys: 7.97 ms, total: 5.28 s
Wall time: 5.28 s
(1, 16385, 131069, 487383, 1117948, 1769482, 2047331, 1788501, 1200342,
622908, 248963, 75361, 16640, 2470, 197, 1)

sage: P = polytopes.Birkhoff_polytope(5)
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 449 ms, sys: 6 µs, total: 449 ms
Wall time: 449 ms
(1, 120, 5040, 50250, 233400, 631700, 1113700, 1367040, 1220550, 817150,
419225, 167200, 52120, 12600, 2300, 300, 25, 1)

# It does not use subset checks as it is a simple polytope.
sage: P = polytopes.associahedron(['A', 11], backend='normaliz')
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 30.4 s, sys: 23.6 ms, total: 30.4 s
Wall time: 30.4 s
(1, 208012, 1144066, 2735810, 3730650, 3197700, 1790712, 659736, 157080,
23100, 1925, 77, 1)
}}}

With AVX2:

{{{
sage: B = Bitset((randint(0,2**20) for _ in range(2**19)))
sage: Bop = ~B
sage: B2 = ~Bop
sage: %timeit B2.intersection_update(B)
4.2 µs ± 3.28 ns per loop (mean ± std. dev. of 7 runs, 100000 loops
each)
sage: %timeit B2.union(B)
12 µs ± 5.9 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
sage: %timeit B.symmetric_difference(Bop)
12 µs ± 5.98 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
sage: %timeit B.difference_update(Bop)
4.03 µs ± 3.46 ns per loop (mean ± std. dev. of 7 runs, 100000 loops
each)

sage: P = polytopes.hypercube(14)
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time C.f_vector()
CPU times: user 5.18 s, sys: 7 µs, total: 5.18 s
Wall time: 5.18 s
(1, 16385, 131069, 487383, 1117948, 1769482, 2047331, 1788501, 1200342,
622908, 248963, 75361, 16640, 2470, 197, 1)

sage: P = polytopes.Birkhoff_polytope(5)
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 436 ms, sys: 3 µs, total: 436 ms
Wall time: 435 ms
(1, 120, 5040, 50250, 233400, 631700, 1113700, 1367040, 1220550, 817150,
419225, 167200, 52120, 12600, 2300, 300, 25, 1)

sage: P = polytopes.associahedron(['A', 11], backend='normaliz')
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 24.3 s, sys: 19.7 ms, total: 24.3 s
Wall time: 24.3 s
(1, 208012, 1144066, 2735810, 3730650, 3197700, 1790712, 659736, 157080,
23100, 1925, 77, 1)
}}}

URL: https://trac.sagemath.org/27103
Reported by: gh-kliem
Ticket author(s): Jonathan Kliem
Reviewer(s): Travis Scrimshaw

We move writing of the `default.qepcadrc` file from `sage-location`
(where it is the last productive bit) to the installation file.

URL: https://trac.sagemath.org/21783
Reported by: mkoeppe
Ticket author(s): Matthias Koeppe
Reviewer(s): John Palmieri

Julian Rüth ([https://gitlab.com/saraedum @saraedum]) opened a merge
request at sagemath/sage!52:
----
{{{
#!markdown
this fixes an issue with line endings in CI. The old version of
git on ubuntu xenial does not understand our .gitattributes or it does
not understand the .git directory that we copy into the docker build
context from a much newer version of git. Anyway, the broken line
endings are gone now.
}}}
[[BR]]

URL: https://trac.sagemath.org/31271
Reported by: galois
Ticket author(s): Julian Rüth
Reviewer(s): Frédéric Chapoton

#30622 broke `sage -b`.

URL: https://trac.sagemath.org/31263
Reported by: gh-kliem
Ticket author(s): Jonathan Kliem
Reviewer(s): Matthias Koeppe