Opened 7 years ago
Last modified 7 weeks ago
#18310 needs_work enhancement
Finite dimensional modules with basis: improved conversions to vectors and matrices
Reported by:  nthiery  Owned by:  

Priority:  major  Milestone:  sage9.7 
Component:  linear algebra  Keywords:  
Cc:  hivert, saliola, virmaux, sagecombinat, 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_matrix18310 (Commits, GitHub, GitLab)  Commit:  f4f4e20ce84e476c401738cadbc6b6b88bc43043 
Dependencies:  Stopgaps: 
Description (last modified by )
This ticket:
 Implements the option
sparse
forCombinatorialFreeModule.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 optionsparse
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
 Description modified (diff)
comment:2 Changed 7 years ago by
 Cc tscrim darij added
comment:3 Changed 7 years ago by
 Branch set to u/nthiery/categories/finite_dimensinonal_modules_with_basis_vector_matrix18310
comment:4 Changed 7 years ago by
 Commit set to 223e55834daf91167b517b7c80f0af92ef627fba
 Description modified (diff)
comment:5 Changed 7 years ago by
 Commit changed from 223e55834daf91167b517b7c80f0af92ef627fba to 3a433dc8318f07f85622c0f14116de51dac8bd20
Branch pushed to git repo; I updated commit sha1. New commits:
3a433dc  18310: cleanup and documentation

comment:6 Changed 7 years ago by
 Status changed from new to needs_review
comment:7 followup: ↓ 9 Changed 7 years ago by
 Branch changed from u/nthiery/categories/finite_dimensinonal_modules_with_basis_vector_matrix18310 to public/categories/fin_dim_modules_with_basis_vector_matrix18310
 Commit changed from 3a433dc8318f07f85622c0f14116de51dac8bd20 to e3fd9394117180fd542e34eafa088bd95928488c
 Reviewers set to Travis Scrimshaw
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_matrix18310' of trac.sagemath.org:sage into public/categories/fin_dim_modules_with_basis_vector_matrix18310

e3fd939  Some trivial doc formatting cleanup from reviewer.

comment:8 Changed 7 years ago by
 Commit changed from e3fd9394117180fd542e34eafa088bd95928488c to 642ab71f657054a9643b6f9de109f92d77cef421
Branch pushed to git repo; I updated commit sha1. New commits:
642ab71  18310: implement columns option for matrix

comment:9 in reply to: ↑ 7 ; followup: ↓ 10 Changed 7 years ago by
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 inFDModWithBasis.ParentMethods.matrix
. You currently haveassert not columns
in the method. Did you want that to be aNotImplementedError
, 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
 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 (noninteractive) doc (I prefer this because it is meant to reflect exact user input).
However I have a question about the
column
attribute inFDModWithBasis.ParentMethods.matrix
. You currently haveassert not columns
in the method. Did you want that to be aNotImplementedError
, 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 followups: ↓ 13 ↓ 14 Changed 7 years ago by
 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
 Commit changed from 642ab71f657054a9643b6f9de109f92d77cef421 to 035418cccaab72f73565c50d3e5b6391d294a467
Branch pushed to git repo; I updated commit sha1. New commits:
035418c  18310: document base_ring option

comment:13 in reply to: ↑ 11 ; followup: ↓ 17 Changed 7 years ago by
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 ; followup: ↓ 15 Changed 7 years ago by
Replying to jdemeyer:
The
base_ring
argument ofmatrix()
is not documented in theINPUT
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 ; followup: ↓ 16 Changed 7 years ago by
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
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 ; followup: ↓ 18 Changed 7 years ago by
Replying to jdemeyer:
Answering my own question: for normal free modules, it seems that
matrix()
just returnsbasis_matrix()
. That's an annoying inconsistency. I actually see no reason to have thismatrix()
alias forbasis_matrix()
.Proposal: define
matrix(*args, **kwds)
in free modules which callsbasis_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 thecoordinate_ring
, not thebase_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 ; followup: ↓ 19 Changed 7 years ago by
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
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 ofbase_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
 Commit changed from 035418cccaab72f73565c50d3e5b6391d294a467 to 485ae1952374751ee2e0d2ba31ad7e59a9897f65
Branch pushed to git repo; I updated commit sha1. New commits:
485ae19  Rebase over 8.1.beta9.

comment:21 Changed 5 years ago by
 Milestone changed from sage6.7 to sage8.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
 Commit changed from 485ae1952374751ee2e0d2ba31ad7e59a9897f65 to 758537354cb93d2f3dad16e065baf017fa5ed0ad
Branch pushed to git repo; I updated commit sha1. New commits:
7585373  Merge branch 'public/categories/fin_dim_modules_with_basis_vector_matrix18310' of git://trac.sagemath.org/sage into public/categories/fin_dim_modules_with_basis_vector_matrix18310

comment:23 Changed 23 months ago by
 Milestone changed from sage8.1 to sage9.2
 Status changed from needs_review to needs_info
Is this ticket still relevant? It would need rebasing
comment:24 Changed 23 months ago by
I am pretty sure it is still relevant as this adds extra features like the ability to specify sparseness.
comment:25 Changed 23 months ago by
 Commit changed from 758537354cb93d2f3dad16e065baf017fa5ed0ad to f4f4e20ce84e476c401738cadbc6b6b88bc43043
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)

comment:26 Changed 23 months ago by
Squashed. Still on top of 8.3.rc3
comment:27 Changed 23 months ago by
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 23 months ago by
 Status changed from needs_info to needs_work
comment:29 Changed 21 months ago by
 Milestone changed from sage9.2 to sage9.3
comment:30 Changed 15 months ago by
 Milestone changed from sage9.3 to sage9.4
Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
comment:31 Changed 10 months ago by
 Milestone changed from sage9.4 to sage9.5
Setting a new milestone for this ticket based on a cursory review.
comment:32 Changed 5 months ago by
 Milestone changed from sage9.5 to sage9.6
comment:33 Changed 7 weeks ago by
 Milestone changed from sage9.6 to sage9.7
Last 10 new commits:
17696: use is_identity_decomposition_into_orthogonal_idempotents in the examples
17696: factored out of the examples a basic implementation of the 0Hecke monoid
16659: proofreading and little additions to the doc; small refactoring of the code
16659: minor linesplit in the doc
16659: refactored _orthogonal_decomposition and updated doctests accordingly
16659: improved documentation for _orthogonal_decomposition
16659: improved documentation for _orthogonal_decomposition
17696: added crosslinks
16659: added missing hecke_monoid.py file
18310: Finite dimensional modules with basis: improved conversions to vectors and matrices