Finite dimensional modules with basis: improved conversions to vectors and matrices

[nthiery]

This ticket:

• Implements the option sparse for CombinatorialFreeModule.Element._vector_
• Implements Modules.WithBasis.FiniteDimensional.ParentMethods.matrix for building a matrix from a list of elements
• Refactors Modules.WithBasis.FiniteDimensional.MorphismMethods.matrix to use the latter and accept the option sparse

This is a follow up to #11111.

It's based on #16659 due to a trivial syntactic conflict. Since #16659 is likely to be positive reviewed very soon, it's probably not worth it making it independent.

[nthiery]

Last 10 new commits:

​0c44982	17696: use is_identity_decomposition_into_orthogonal_idempotents in the examples
​cba7c8d	17696: factored out of the examples a basic implementation of the 0-Hecke monoid
​6e81e4b	16659: proofreading and little additions to the doc; small refactoring of the code
​19756de	16659: minor line-split in the doc
​fd8e1ad	16659: refactored _orthogonal_decomposition and updated doctests accordingly
​cc327ef	16659: improved documentation for _orthogonal_decomposition
​e00dfdb	16659: improved documentation for _orthogonal_decomposition
​cce7d3d	17696: added crosslinks
​faf83a1	16659: added missing hecke_monoid.py file
​223e558	18310: Finite dimensional modules with basis: improved conversions to vectors and matrices

[git]

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

​3a433dc

18310: cleanup and documentation

[tscrim]

Looks good overall. This was something Darij and I wondered about when looking at Lie algebras (something I will need to change on that ticket). However I have a question about the column attribute in FDModWithBasis.ParentMethods.matrix. You currently have assert not columns in the method. Did you want that to be a NotImplementedError, or did you want to have that do something in this ticket?

---

New commits:

​b055669	Merge branch 'u/nthiery/categories/finite_dimensinonal_modules_with_basis_vector_matrix-18310' of trac.sagemath.org:sage into public/categories/fin_dim_modules_with_basis_vector_matrix-18310
​e3fd939	Some trivial doc formatting cleanup from reviewer.

[git]

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

​642ab71

18310: implement columns option for matrix

[nthiery]

Replying to tscrim:

Looks good overall; I made some minor doc formatting tweaks.

I am happy with them; thanks! Isn't triple quoting of strings kind of overkill? Not that I really mind, but it's kind of heavy handed and really Sphinx should do that for us ...

However I have a question about the column attribute in FDModWithBasis.ParentMethods.matrix. You currently have assert not columns in the method. Did you want that to be a NotImplementedError, or did you want to have that do something in this ticket?

Oops; just a marker I had left for myself and I later forgot. There is a basic implementation now! Back to needs review.

Cheers,

[tscrim]

Replying to nthiery:

Replying to tscrim:

Looks good overall; I made some minor doc formatting tweaks.

I am happy with them; thanks! Isn't triple quoting of strings kind of overkill? Not that I really mind, but it's kind of heavy handed and really Sphinx should do that for us ...

It's 2 backticks and then a quote, so it gives it that nice code look in the (non-interactive) doc (I prefer this because it is meant to reflect exact user input).

However I have a question about the column attribute in FDModWithBasis.ParentMethods.matrix. You currently have assert not columns in the method. Did you want that to be a NotImplementedError, or did you want to have that do something in this ticket?

Oops; just a marker I had left for myself and I later forgot. There is a basic implementation now! Back to needs review.

Thanks. Positive review.

[jdemeyer]

The base_ring argument of matrix() is not documented in the INPUT block.

IMHO, this belongs in the discussion on Trac, not in the docstring, especially the reference to a future hypothetical fix for #18312:

Constructing a sparse matrix with this method is currently
really much faster than building it from sparse vectors;
see :trac:`18312`::

    sage: n = 10^3; F = CombinatorialFreeModule(QQ, range(n)); vectors = [F.zero()]*n
    sage: %timeit m = F.matrix(vectors, sparse=True) # not tested
    The slowest run ...
    1000 loops, best of 3: 466 µs per loop
    sage: %timeit m = matrix(QQ, [v._vector_(sparse=True) for v in vectors], sparse=True) # not tested
    1 loops, best of 3: 1.19 s per loop

When :trac:`18312` will be fixed, using this method is
likely to still save some constant time factor.

And finally a question: is this new code relevant only for combinatorial free modules or also "normal" free modules?

[git]

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

​035418c

18310: document base_ring option

[jdemeyer]

Replying to jdemeyer:

And finally a question: is this new code relevant only for combinatorial free modules or also "normal" free modules?

Answering my own question: for normal free modules, it seems that matrix() just returns basis_matrix(). That's an annoying inconsistency. I actually see no reason to have this matrix() alias for basis_matrix().

Proposal: define matrix(*args, **kwds) in free modules which calls basis_matrix() if no arguments are given (this should be deprecated) and calls the modified(*) categories implementation if any argument is supplied.

(*) The base_ring of the resulting matrix should be the coordinate_ring, not the base_ring of the free module.

[nthiery]

Replying to jdemeyer:

The base_ring argument of matrix() is not documented in the INPUT block.

Oops, fixed. Thanks!

IMHO, this belongs in the discussion on Trac, not in the docstring, especially the reference to a future hypothetical fix for #18312:

I don't agree. This is not a discussion about how to implement this ticket, but an information for the user, indicating the relevance of this method in the short and long term. She has little chance to find this information if it's only on trac.

And finally a question: is this new code relevant only for combinatorial free modules or also "normal" free modules?

It's meant for any FiniteDimensionalModulesWithBasis?. When "normal" free modules will finally be in this category, they will benefit from this code; one of the thing to settle for this is the syntax to iterate through the terms. Up to this syntax detail, I believe this generic code from this ticket should work properly.

Ah, this raises a good point: FreeModule? already defines a matrix method, so we have a name conflict. Any good alternative name suggestion?

Cheers,

Nicolas

[jdemeyer]

Replying to nthiery:

but an information for the user, indicating the relevance of this method in the short and long term. She has little chance to find this information if it's only on trac.

Compromise: at least remove the sentence When :trac:`18312` will be fixed, using this method is likely to still save some constant time factor.

[nthiery]

Hi Jeroen!

Replying to jdemeyer:

Replying to nthiery:

but an information for the user, indicating the relevance of this method in the short and long term. She has little chance to find this information if it's only on trac.

Compromise: at least remove the sentence When :trac:`18312` will be fixed, using this method is likely to still save some constant time factor.

With the idea that we will update the comment when 18312 will be fixed? That sounds very reasonable indeed. I am just slightly hesitant, because I would not want the user to believe that this method is just a workaround, when it's actually a way to better express a typical intention, to give a chance to the system to better optimize it. If you think it does not read that way I am happy to remove this sentence.

[nthiery]

Replying to jdemeyer:

Answering my own question: for normal free modules, it seems that matrix() just returns basis_matrix(). That's an annoying inconsistency. I actually see no reason to have this matrix() alias for basis_matrix().

Proposal: define matrix(*args, **kwds) in free modules which calls basis_matrix() if no arguments are given (this should be deprecated) and calls the modified(*) categories implementation if any argument is supplied.

+1.

Do you agree that this should go in #10672 rather than here? It would be weird to have matrix call a method that is not yet available from the categories. As a first step, we could just deprecate FreeModule.matrix for now. What do you think?

(*) The base_ring of the resulting matrix should be the coordinate_ring, not the base_ring of the free module.

Gasp, another inconsistency: most other modules in Sage (polynomial rings, matrix space, ...) don't define coordinate_ring: there it's assumed that the coefficients of elements live in base_ring. Ok, clarifying this is for #10672 since it's not about this specific method, but about all uses of base_ring.

Thanks for the thoughts

Cheers,

Nicolas

[jdemeyer]

Replying to nthiery:

Gasp, another inconsistency: most other modules in Sage (polynomial rings, matrix space, ...) don't define coordinate_ring: there it's assumed that the coefficients of elements live in base_ring.

That's easily worked around by defining coordinate_ring as an alias of base_ring in the category code. Then it can be overridden in specific cases where needed.

[nthiery]

Replying to jdemeyer:

Replying to nthiery:

Gasp, another inconsistency: most other modules in Sage (polynomial rings, matrix space, ...) don't define coordinate_ring: there it's assumed that the coefficients of elements live in base_ring.

That's easily worked around by defining coordinate_ring as an alias of base_ring in the category code. Then it can be overridden in specific cases where needed.

Yes. And making sure all the category (and users) code calls coordinate_ring instead of base_ring whenever appropriate. That's certainly doable, but we want to make sure we want this feature generally before adding this little additional layer of complexity. Anyway, that's for #10672.

[git]

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

​485ae19

Rebase over 8.1.beta9.

[tscrim]

I rebased this over 8.1.beta9, but I'm not sure if there is anything that needs to be addressed from the conversion above. Jeroen, do you happen to remember or can recreate?

[git]

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

​7585373

Merge branch 'public/categories/fin_dim_modules_with_basis_vector_matrix-18310' of git://trac.sagemath.org/sage into public/categories/fin_dim_modules_with_basis_vector_matrix-18310

[mkoeppe]

Is this ticket still relevant? It would need rebasing

[tscrim]

I am pretty sure it is still relevant as this adds extra features like the ability to specify sparseness.

[git]

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

​f4f4e20

Finite dimensional modules with basis: improved conversions to vectors and matrices (squashed)

[mkoeppe]

Squashed. Still on top of 8.3.rc3

[mkoeppe]

Merging 9.2.beta3 creates some merge conflicts that look like they will be easy to resolve ... for people who know this code well

[mkoeppe]

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

Setting a new milestone for this ticket based on a cursory review.