allow several implementations of matrices in MatrixSpace

[vdelecroix]

The aim of this ticket is to revamp the MatrixSpace constructor in order to be able to choose the implementation.

For example, with the attached branch one can have access to 2 implementations of integer matrices

sage: MatrixSpace(ZZ, 3, implementation='flint')
Full MatrixSpace of 3 by 3 dense matrices over Integer Ring
sage: MatrixSpace(ZZ, 3, implementation='generic')
Full MatrixSpace of 3 by 3 dense matrices over Integer Ring (using Matrix_generic_dense)

One important change is the move of the method _get_matrix_class of MatrixSpace as an independent function.

A problem arose with CartanMatrix (in sage/combinat/root_system/cartan_matrix.py). The class CartanMatrix inherits from Matrix_integer_sparse but does not properly redefines the parent. As a consequence of the changes here, many matrix operations are not valid anymore for inherited types (mostly submatrices operations such as __getitem__ with slices or stack). A fix is provided by defining CartanMatrix.matrix_space.

follow up: #23714 (implementation of gap matrices)

[vdelecroix]

experimental branch ready!

---

New commits:

​457d2fb	23704: getitem/setitem for libgap elements
​34f1ddc	TMP 23706 commit

[jipilab]

The title of the ticket could be a bit more specific.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​d9f0532

TMP 23706 commit

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​a925818	23704: forgot to set j appropriately!
​007bdcf	TMP COMMIT 23706: fix some doctests

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​f8940d4

TMP 23706: remove print statement

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​235c561

TMP 23706 COMMIT: remove randomize for cyclo_dense

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​dce22c8

TMP COMMIT 23706: more careful about input

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​4dc210b	23704: forgot to set j appropriately!
​c3241d6	23704: "multi-indices "multi indices" "multiindices"
​f1013de	23706: allow different matrix implementations

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0cbf7ff

23706: fix call to _get_matrix_class

[vdelecroix]

hum... got a lot of failures

combinat/root_system/root_lattice_realizations.py  # 1 doctest failed
combinat/root_system/root_system.py  # 1 doctest failed
combinat/root_system/weight_space.py  # 3 doctests failed
combinat/root_system/type_affine.py  # 3 doctests failed
combinat/root_system/ambient_space.py  # 1 doctest failed
combinat/root_system/root_space.py  # 1 doctest failed
combinat/root_system/cartan_type.py  # 2 doctests failed
categories/crystals.py  # 2 doctests failed
combinat/root_system/weight_lattice_realizations.py  # 12 doctests failed
combinat/root_system/cartan_matrix.py  # 5 doctests failed
combinat/root_system/type_relabel.py  # 1 doctest failed
combinat/root_system/dynkin_diagram.py  # 4 doctests failed
combinat/root_system/type_marked.py  # 1 doctest failed
combinat/root_system/type_reducible.py  # 2 doctests failed

[vdelecroix]

Needs to fix #23721 first.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​a087066	23721: __copy__/__deepcopy__ on GapElement
​9f74040	23706: allow to choose implementation of matrices

[vdelecroix]

I postponed the introduction of Matrix_gap in ticket #23714

[vdelecroix]

... wrong commits

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​4efbf51

23706: allow to choose matrix mplementation

[vdelecroix]

JP, do you feel up for the review?

[vdelecroix]

Fucking root systems

sage -t --long src/sage/combinat/root_system/cartan_type.py  # 2 doctests failed
sage -t --long src/sage/combinat/root_system/weight_lattice_realizations.py  # 12 doctests failed
sage -t --long src/sage/combinat/root_system/ambient_space.py  # 1 doctest failed
sage -t --long src/sage/combinat/root_system/root_lattice_realizations.py  # 1 doctest failed
sage -t --long src/sage/combinat/root_system/type_marked.py  # 1 doctest failed
sage -t --long src/sage/combinat/root_system/type_reducible.py  # 2 doctests failed
sage -t --long src/sage/combinat/root_system/root_space.py  # 1 doctest failed
sage -t --long src/sage/combinat/root_system/cartan_matrix.py  # 5 doctests failed
sage -t --long src/sage/combinat/root_system/dynkin_diagram.py  # 4 doctests failed
sage -t --long src/sage/combinat/root_system/weight_space.py  # 3 doctests failed
sage -t --long src/sage/combinat/root_system/type_relabel.py  # 1 doctest failed
sage -t --long src/sage/combinat/root_system/type_affine.py  # 3 doctests failed
sage -t --long src/sage/combinat/root_system/root_system.py  # 1 doctest failed
sage -t --long src/sage/categories/crystals.py  # 2 doctests failed

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​d5fa13d

23706: dirty fixes for Cartan matrices

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​98d9ae1

23706: fix for CartanMatrix

[vdelecroix]

Cartan matrices are fixed... waiting for patchbot verdict again.

[jipilab]

Ok, I'm "back on trac"!

I'll give a look at this today.

Where should I throw in the benchmarking script? I guess it is not a good idea to hard code the best implementation, but at least, in the tests, we could add some relevant benchmarks to keep track of the evolution?

[jipilab]

In the description of the test:

+        Check that multiplication for matrices with different backends are not allowed::

I would also mention that sparsity is checked ( the reason why there is no X appearing in row 2, column 3...)

The changes in the CartanMatrix? look good.

In one of the bot's report, I get an error here:

**********************************************************************
File "src/sage/matrix/matrix_gfpn_dense.pyx", line 1484, in sage.matrix.matrix_gfpn_dense.Matrix_gfpn_dense._echelon_in_place_classical
Failed example:
    type(X)
Expected:
    <type 'sage.matrix.matrix_generic_dense.Matrix_generic_dense'>
Got:
    <type 'sage.matrix.matrix_gfpn_dense.Matrix_gfpn_dense'>
**********************************************************************

Other errors look to be unrelated. I'm still looking into the changes.

[jipilab]

I ran the test on the file src/sage/matrix/matrix_gfpn_dense.pyx and all tests passed...

[jipilab]

Just did some pep8 corrections... Otherwise, it looks good. Perhaps we should wait to get a proper bot to go over the changes as they touch many files...

---

New commits:

​ae0bfc3

Some pep8 conventions

[vdelecroix]

Replying to jipilab:

I ran the test on the file src/sage/matrix/matrix_gfpn_dense.pyx and all tests passed...

This need to be fixed. It depends whether meataxe is installed or not.

[vdelecroix]

New commits:

​cc35c82

23706: fix doctest in matrix_gfpn_dense.pyx

[vdelecroix]

Much cleaner now!!

[vdelecroix]

Replying to jipilab:

Ok, I'm "back on trac"!

I'll give a look at this today.

Where should I throw in the benchmarking script? I guess it is not a good idea to hard code the best implementation, but at least, in the tests, we could add some relevant benchmarks to keep track of the evolution?

Not here. You should open a new ticket (and you can add it to the follow-up list of this ticket). Moreover the concept of "best implementation" depends on what you intend to do (e.g. matrix multiplication, Gauss elimination, determinant, etc).

[jipilab]

The ticket does not apply on beta5. I'm compiling b5 right now and I'll check if I can diagnose further. I have to install meataxe and checkout testing. Give my machine some time and I get back here!

[jipilab]

Is there a dependency to #23721?

[vdelecroix]

Replying to jipilab:

Is there a dependency to #23721?

Not that I know of...

[vdelecroix]

Replying to jipilab:

The ticket does not apply on beta5. I'm compiling b5 right now and I'll check if I can diagnose further. I have to install meataxe and checkout testing. Give my machine some time and I get back here!

The problem comes from something that has changed in matrix_space.py. The merge is simple but I have to leave in 5 minutes... will fix that first thing this afternoon.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​869b155

Rebased on beta5 (attempt to solve conflict)

[jipilab]

Replying to vdelecroix:

Replying to jipilab:

The ticket does not apply on beta5. I'm compiling b5 right now and I'll check if I can diagnose further. I have to install meataxe and checkout testing. Give my machine some time and I get back here!

The problem comes from something that has changed in matrix_space.py. The merge is simple but I have to leave in 5 minutes... will fix that first thing this afternoon.

Damn, I just read this comment... Hope I did not create any trouble.

[vdelecroix]

It's ok.

[jipilab]

There are some spurious doc errors, otherwise, it looks good.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​47a0f13	23706: remove trailing whitespaces in cartan_matrix.py
​079981a	23706: fix doctests

[vdelecroix]

j'ai poussé... reste plus qu'à attendre les verdits de madame patchbot.

[vdelecroix]

New commits:

​dee269a	23706: allow to choose matrix implementation
​0ca3ae5	23706: fix for CartanMatrix
​4cb0c2f	Some pep8 conventions
​5c415f5	23706: fix doctest in matrix_gfpn_dense.pyx

[jdemeyer]

Conflicts with #24096

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​08c9865	23706: allow to choose matrix implementation
​c3b5370	23706: fix for CartanMatrix
​07376df	Some pep8 conventions
​4f818de	23706: fix doctest in matrix_gfpn_dense.pyx

[vdelecroix]

rebased on 8.1.rc0

[vdelecroix]

patchbot is happy! jipilab?

[tscrim]

I have a few comments:

-    def matrix_space(self, nrows=None, ncols=None, sparse=None):
+    def matrix_space(self, nrows=None, ncols=None, sparse=True):
         r"""
         Return a matrix space over the integers.
 
         INPUT:
 
-        - ``nrows`` - number of rows
+        - ``nrows`` -- number of rows
 
-        - ``ncols`` - number of columns
+        - ``ncols`` -- number of columns
 
-        - ``sparse`` - (boolean) sparseness
+        - ``sparse`` -- (boolean) sparseness
 
         EXAMPLES::
 
             sage: cm = CartanMatrix(['A', 3])
             sage: cm.matrix_space()
             Full MatrixSpace of 3 by 3 sparse matrices over Integer Ring
             sage: cm.matrix_space(2, 2)
             Full MatrixSpace of 2 by 2 sparse matrices over Integer Ring
             sage: cm[:2,1:]   # indirect doctest
             [-1  0]
             [ 2 -1]
         """
         if nrows is None:
             nrows = self.nrows()
         if ncols is None:
             ncols = self.ncols()
-        if sparse is None:
-            sparse = True
 
         if nrows == self.nrows() and ncols == self.ncols() and sparse:
             return self.parent()
         else:
             from sage.matrix.matrix_space import MatrixSpace
             return MatrixSpace(ZZ, nrows, ncols, sparse is None or bool(sparse))

I would make this into a more 2/3 compatible test:

            sage: for i in range(3):
            ....:     for j in range(3):
            ....:         try:
            ....:             s = M[i].an_element() * M[j].an_element()
            ....:             print('X', end='')
            ....:         except TypeError:
            ....:             print(' ', end='')
            ....:     print()

I would instead create a 0/1-matrix and output that. Another option would be creating an appropriate string with '\n'.join(...). Similar for another test.

These tests should not be marked as meataxe if it really is using the generic implementation:

            sage: MS = MatrixSpace(M.base_ring(), M.nrows(), M.ncols(), implementation='generic')
            sage: X = MS(M)                         # optional: meataxe
            sage: type(X)                           # optional: meataxe
            sage: X.echelon_form() # optional: meataxe

Otherwise that would be a bug.

Do we want m4ri to have precedence over trying meataxe when no implementation is given? (I'm cc-ing Simon to note that there might be a change in behavior.)

I'm also split on documenting about when we use a non-generic implementation by default. It feels too much like an implementation detail that it should be hidden from the more casual users, but I think it is good for the more advanced users to have it in the public doc. Thoughts?

I'm also not 100% convinced about having to explicitly convert matrices of different implementations, but since things are likely to be incompatible and it seems unlikely that this would be a problem (I think a user who is choosing implementations will probably be careful and might even appreciate this error). I do not have a good reason to make this an objection, but I am just noting that this might come up from a user.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​eeeba32

23706: a default argument and doctests

[vdelecroix]

Thanks Travis for having a look.

Replying to tscrim:

[SNIP]

agreed and changed in eeeba32

Do we want m4ri to have precedence over trying meataxe when no implementation is given? (I'm cc-ing Simon to note that there might be a change in behavior.)

There should not be any change. It concerns only the case characteristic = 2.

if implementation is None:
    if R.characteristic() == 2 and R.order() <= 65536:
        implementation = 'm4ri'
    elif R.order() <= 255:
        try:
            from . import matrix_gfpn_dense
        except ImportError:
            implementation = 'generic'
        else:
            implementation = 'meataxe'
    else:
        implementation = 'generic'

where it used to be

if R.characteristic() == 2:
    if R.order() <= 65536:
        return matrix_gf2e_dense.Matrix_gf2e_dense
elif R.order() <= 255:
    try:
        from . import matrix_gfpn_dense
        return matrix_gfpn_dense.Matrix_gfpn_dense
    except ImportError:
        pass

I'm also split on documenting about when we use a non-generic implementation by default. It feels too much like an implementation detail that it should be hidden from the more casual users, but I think it is good for the more advanced users to have it in the public doc. Thoughts?

What would you expect exactly? It would be a nightmare to keep the documentation up to date.

I'm also not 100% convinced about having to explicitly convert matrices of different implementations, but since things are likely to be incompatible and it seems unlikely that this would be a problem (I think a user who is choosing implementations will probably be careful and might even appreciate this error). I do not have a good reason to make this an objection, but I am just noting that this might come up from a user.

It should be possible to implement coercion to the default implementation (with conversion). Anyway, I would like to keep such changes for later.

[tscrim]

Replying to vdelecroix:

Thanks Travis for having a look.

Do we want m4ri to have precedence over trying meataxe when no implementation is given? (I'm cc-ing Simon to note that there might be a change in behavior.)

There should not be any change. It concerns only the case characteristic = 2. [snip]

Right, actually I might have misread what meataxe is for and it's a non-issue because it is not meant for characteristic 2. Sorry for the noise.

I'm also split on documenting about when we use a non-generic implementation by default. It feels too much like an implementation detail that it should be hidden from the more casual users, but I think it is good for the more advanced users to have it in the public doc. Thoughts?

What would you expect exactly? It would be a nightmare to keep the documentation up to date.

Keeping it up to date would not be such a problem; at least I don't expect it to change that much. However, I tried a few different ways to present the info and nothing really worked too well. There's just a few too many little cases for the finite fields. I guess if someone cares enough they are good enough to just look at the code.

Thanks. Positive review.

[vbraun]

Documentation doesn't build

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​c06ed6e	23706: allow to choose matrix implementation
​758947e	23706: fix for CartanMatrix
​e394c15	Some pep8 conventions
​c16fc79	23706: fix doctest in matrix_gfpn_dense.pyx
​6bff8c8	23706: a default argument and doctests

[vdelecroix]

With the rebasing I do not have any problem with the documentation.

[vdelecroix]

found out

[dochtml] [matrices ] docstring of sage.matrix.action.MatrixMatrixAction:24: WARNING: Unexpected indentation.
[dochtml] [matrices ] docstring of sage.matrix.action.MatrixMatrixAction:25: WARNING: Block quote ends without a blank line; unexpected unindent.
[dochtml] [matrices ] /opt/sage/local/lib/python2.7/site-packages/sage/matrix/special.py:docstring of sage.matrix.special:48: WARNING: undefined label: sage.combinat.matrices.hadamard_matrix (if the link has no caption the label must precede a section header)
[dochtml] [matrices ] /opt/sage/local/lib/python2.7/site-packages/sage/matrix/special.py:docstring of sage.matrix.special:49: WARNING: undefined label: sage.combinat.matrices.latin (if the link has no caption the label must precede a section header)
[dochtml] Error building the documentation.
[dochtml] Traceback (most recent call last):
[dochtml]   File "/opt/sage/local/lib/python2.7/runpy.py", line 174, in _run_module_as_main
[dochtml]     "__main__", fname, loader, pkg_name)
[dochtml]   File "/opt/sage/local/lib/python2.7/runpy.py", line 72, in _run_code
[dochtml]     exec code in run_globals
[dochtml]   File "/opt/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__main__.py", line 2, in <module>
[dochtml]     main()
[dochtml]   File "/opt/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 1675, in main
[dochtml]     builder()
[dochtml]   File "/opt/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 310, in _wrapper
[dochtml]     getattr(get_builder(document), 'inventory')(*args, **kwds)
[dochtml]   File "/opt/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 505, in _wrapper
[dochtml]     build_many(build_ref_doc, L)
[dochtml]   File "/opt/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 260, in build_many
[dochtml]     results.append(target(arg))
[dochtml]   File "/opt/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 71, in build_ref_doc
[dochtml]     getattr(ReferenceSubBuilder(doc, lang), format)(*args, **kwds)
[dochtml]   File "/opt/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 720, in _wrapper
[dochtml]     getattr(DocBuilder, build_type)(self, *args, **kwds)
[dochtml]   File "/opt/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 105, in f
[dochtml]     runsphinx()
[dochtml]   File "/opt/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/sphinxbuild.py", line 218, in runsphinx
[dochtml]     raise exception
[dochtml] OSError: [matrices ] docstring of sage.matrix.action.MatrixMatrixAction:24: WARNING: Unexpected indentation.
[dochtml] 
[dochtml] [matrices ] WARNING: Error building the documentation.
[dochtml] [matrices ] Traceback (most recent call last):
[dochtml] [matrices ] File "/opt/sage/local/lib/python2.7/runpy.py", line 174, in _run_module_as_main
[dochtml] [matrices ] "__main__", fname, loader, pkg_name)
[dochtml] [matrices ] File "/opt/sage/local/lib/python2.7/runpy.py", line 72, in _run_code
[dochtml] [matrices ] exec code in run_globals
[dochtml] [matrices ] File "/opt/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__main__.py", line 2, in <module>
[dochtml] [matrices ] main()
[dochtml] [matrices ] File "/opt/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 1675, in main
[dochtml] [matrices ] builder()
[dochtml] [matrices ] File "/opt/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 310, in _wrapper
[dochtml] [matrices ] getattr(get_builder(document), 'inventory')(*args, **kwds)
[dochtml] [matrices ] File "/opt/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 505, in _wrapper
[dochtml] [matrices ] build_many(build_ref_doc, L)
[dochtml] [matrices ] File "/opt/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 260, in build_many
[dochtml] [matrices ] results.append(target(arg))
[dochtml] [matrices ] File "/opt/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 71, in build_ref_doc
[dochtml] [matrices ] getattr(ReferenceSubBuilder(doc, lang), format)(*args, **kwds)
[dochtml] [matrices ] File "/opt/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 720, in _wrapper
[dochtml] [matrices ] getattr(DocBuilder, build_type)(self, *args, **kwds)
[dochtml] [matrices ] File "/opt/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 105, in f
[dochtml] [matrices ] runsphinx()
[dochtml] [matrices ] File "/opt/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/sphinxbuild.py", line 218, in runsphinx
[dochtml] [matrices ] raise exception
[dochtml] [matrices ] OSError: [matrices ] docstring of sage.matrix.action.MatrixMatrixAction:24: WARNING: Unexpected indentation.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​018226b

23706: separate the NOTE and TESTS blocks

[vdelecroix]

I don't understand why, but sphinx was in trouble with NOTE and TESTS being in the same documentation string.

[tscrim]

It may not be Sphinx but our custom handling of the TESTS block (at least, IIRC we do something special there in order to hide the block).

[tscrim]

Anyways, the workaround is fine with me and there is a green patchbot. Back to positive review.

[vdelecroix]

thanks Travis.