Opened 7 years ago

Last modified 3 months ago

#18310 needs_work enhancement

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

Reported by: nthiery Owned by:
Priority: major Milestone: sage-9.7
Component: linear algebra Keywords:
Cc: hivert, saliola, virmaux, sage-combinat, tscrim, darij Merged in:
Authors: Nicolas M. Thiéry Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: public/categories/fin_dim_modules_with_basis_vector_matrix-18310 (Commits, GitHub, GitLab) Commit: f4f4e20ce84e476c401738cadbc6b6b88bc43043
Dependencies: Stopgaps:

Status badges

Description (last modified by 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.

Change History (33)

comment:1 Changed 7 years ago by nthiery

  • Description modified (diff)

comment:2 Changed 7 years ago by tscrim

  • Cc tscrim darij added

comment:3 Changed 7 years ago by nthiery

  • Branch set to u/nthiery/categories/finite_dimensinonal_modules_with_basis_vector_matrix-18310

comment:4 Changed 7 years ago by nthiery

  • Commit set to 223e55834daf91167b517b7c80f0af92ef627fba
  • Description modified (diff)

Last 10 new commits:

0c4498217696: use is_identity_decomposition_into_orthogonal_idempotents in the examples
cba7c8d17696: factored out of the examples a basic implementation of the 0-Hecke monoid
6e81e4b16659: proofreading and little additions to the doc; small refactoring of the code
19756de16659: minor line-split in the doc
fd8e1ad16659: refactored _orthogonal_decomposition and updated doctests accordingly
cc327ef16659: improved documentation for _orthogonal_decomposition
e00dfdb16659: improved documentation for _orthogonal_decomposition
cce7d3d17696: added crosslinks
faf83a116659: added missing hecke_monoid.py file
223e55818310: Finite dimensional modules with basis: improved conversions to vectors and matrices

comment:5 Changed 7 years ago by git

  • Commit changed from 223e55834daf91167b517b7c80f0af92ef627fba to 3a433dc8318f07f85622c0f14116de51dac8bd20

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

3a433dc18310: cleanup and documentation

comment:6 Changed 7 years ago by nthiery

  • Authors set to Nicolas M. Thiéry
  • Status changed from new to needs_review

comment:7 follow-up: Changed 7 years ago by tscrim

  • Branch changed from u/nthiery/categories/finite_dimensinonal_modules_with_basis_vector_matrix-18310 to public/categories/fin_dim_modules_with_basis_vector_matrix-18310
  • Commit changed from 3a433dc8318f07f85622c0f14116de51dac8bd20 to e3fd9394117180fd542e34eafa088bd95928488c
  • Reviewers set to Travis Scrimshaw

Looks good overall; I made some minor doc formatting tweaks. 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:

b055669Merge 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
e3fd939Some trivial doc formatting cleanup from reviewer.
Last edited 7 years ago by tscrim (previous) (diff)

comment:8 Changed 7 years ago by git

  • Commit changed from e3fd9394117180fd542e34eafa088bd95928488c to 642ab71f657054a9643b6f9de109f92d77cef421

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

642ab7118310: implement columns option for matrix

comment:9 in reply to: ↑ 7 ; follow-up: Changed 7 years ago by 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,

comment:10 in reply to: ↑ 9 Changed 7 years ago by tscrim

  • Status changed from needs_review to positive_review

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.

comment:11 follow-ups: Changed 7 years ago by jdemeyer

  • Status changed from positive_review to needs_work

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?

comment:12 Changed 7 years ago by git

  • Commit changed from 642ab71f657054a9643b6f9de109f92d77cef421 to 035418cccaab72f73565c50d3e5b6391d294a467

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

035418c18310: document base_ring option

comment:13 in reply to: ↑ 11 ; follow-up: Changed 7 years ago by 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.

comment:14 in reply to: ↑ 11 ; follow-up: Changed 7 years ago by 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

comment:15 in reply to: ↑ 14 ; follow-up: Changed 7 years ago by 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.

comment:16 in reply to: ↑ 15 Changed 7 years ago by 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.

comment:17 in reply to: ↑ 13 ; follow-up: Changed 7 years ago by 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

comment:18 in reply to: ↑ 17 ; follow-up: Changed 7 years ago by 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.

comment:19 in reply to: ↑ 18 Changed 7 years ago by 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.

comment:20 Changed 5 years ago by git

  • Commit changed from 035418cccaab72f73565c50d3e5b6391d294a467 to 485ae1952374751ee2e0d2ba31ad7e59a9897f65

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

485ae19Rebase over 8.1.beta9.

comment:21 Changed 5 years ago by tscrim

  • Milestone changed from sage-6.7 to sage-8.1
  • Status changed from needs_work to needs_review

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?

comment:22 Changed 4 years ago by git

  • Commit changed from 485ae1952374751ee2e0d2ba31ad7e59a9897f65 to 758537354cb93d2f3dad16e065baf017fa5ed0ad

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

7585373Merge 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

comment:23 Changed 2 years ago by mkoeppe

  • Milestone changed from sage-8.1 to sage-9.2
  • Status changed from needs_review to needs_info

Is this ticket still relevant? It would need rebasing

comment:24 Changed 2 years ago by tscrim

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

comment:25 Changed 2 years ago by git

  • Commit changed from 758537354cb93d2f3dad16e065baf017fa5ed0ad to f4f4e20ce84e476c401738cadbc6b6b88bc43043

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

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

comment:26 Changed 2 years ago by mkoeppe

Squashed. Still on top of 8.3.rc3

comment:27 Changed 2 years ago by 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

comment:28 Changed 2 years ago by mkoeppe

  • Status changed from needs_info to needs_work

comment:29 Changed 22 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:30 Changed 17 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

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

comment:31 Changed 12 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5

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

comment:32 Changed 7 months ago by mkoeppe

  • Milestone changed from sage-9.5 to sage-9.6

comment:33 Changed 3 months ago by mkoeppe

  • Milestone changed from sage-9.6 to sage-9.7
Note: See TracTickets for help on using tickets.