Opened 4 months ago
Last modified 3 months ago
#31992 new enhancement
FiniteRankFreeModuleMorphism: Add method SVD (singular value decomposition)
Reported by:  mkoeppe  Owned by:  

Priority:  major  Milestone:  sage9.5 
Component:  linear algebra  Keywords:  
Cc:  egourgoulhon, ghmjungmath, ghhonglizhaobob  Merged in:  
Authors:  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/ghhonglizhaobob/finiterankfreemodulemorphism__add_method_svd__singular_value_decomposition_ (Commits, GitHub, GitLab)  Commit:  38bcecc8796d95eb8946ba51eb4f807ca9edef99 
Dependencies:  Stopgaps: 
Description (last modified by )
This operation is currently available for matrices over RDF
.
The version for FiniteRankFreeModuleMorphism
would define a new basis on each of the domain and codomain (with an orthogonal change of basis) so that the matrix of the morphism in the new bases is the diagonal of the singular values.
Example:
sage: M = FiniteRankFreeModule(ZZ, 3, name='M') sage: N = FiniteRankFreeModule(ZZ, 2, name='N') sage: e = M.basis('e') ; f = N.basis('f') sage: H = Hom(M,N) ; H Set of Morphisms from Rank3 free module M over the Integer Ring to Rank2 free module N over the Integer Ring in Category of finite dimensional modules over Integer Ring sage: phi = H([[2,1,3], [1,0,4]], name='phi', latex_name=r'\phi') ; phi Generic morphism: From: Rank3 free module M over the Integer Ring To: Rank2 free module N over the Integer Ring sage: phi.matrix(e, f) [ 2 1 3] [ 1 0 4] sage: f_prime = N.basis('f_prime', from_family=(f[0]f[1], 2*f[0]+3*f[1] # pretend that this basis is the right orthogonal matrix of the SVD... sage: phi.matrix(e, f_prime) [ 8 3 1] [ 3 1 1]
Change History (22)
comment:1 followup: ↓ 2 Changed 4 months ago by
 Description modified (diff)
comment:2 in reply to: ↑ 1 Changed 3 months ago by
comment:3 followups: ↓ 4 ↓ 5 Changed 3 months ago by
RDF is the "real doubleprecision field"  equivalent of double
in C.
https://doc.sagemath.org/html/en/reference/rings_numerical/sage/rings/real_double.html
comment:4 in reply to: ↑ 3 ; followup: ↓ 6 Changed 3 months ago by
Replying to mkoeppe:
RDF is the "real doubleprecision field"  equivalent of
double
in C. https://doc.sagemath.org/html/en/reference/rings_numerical/sage/rings/real_double.html
Thanks professor. Additionally, in implementing the SVD, should we resort to external libraries such as numpy
, or is it a better practice to use sage
methods whenever possible?
comment:5 in reply to: ↑ 3 Changed 3 months ago by
If I'm understanding correctly after reading the code, we are still working with matrices (instead of highdimensional tensors). Suppose A
is the matrix obtained from M.hom(N, some_matrix, basis=(e, f))
. Let x.parent() == M
, y.parent() == N
. Then we have:
y = A*x y = U * S * V_dagger * x # do SVD on A (U_dagger * y) = S * (V_dagger * x) # invert U y_prime = S*x_prime # renamed x and y
In code, we will reassign the default bases of M
and N
:
M._def_basis = V N._def_basis = U # certainly, this reassignment needs more # work in terms of actual implementations
such that S
would be the result of hom.matrix()
in this new basis.
comment:6 in reply to: ↑ 4 ; followup: ↓ 7 Changed 3 months ago by
Replying to ghhonglizhaobob:
in implementing the SVD, should we resort to external libraries such as
numpy
, or is it a better practice to usesage
methods whenever possible?
In Sage we support a wide range of rings for the arithmetic, and consequently often use multiple libraries for the implementation and also have an inSage generic implementation.
The existing implementation of SVD
in src/sage/matrix/matrix_double_dense.pyx
just calls scipy.linalg.svd
.
It would be quite useful to add a generic implementation that only uses the general methods that Sage matrices offer. In that way, we could have access to arbitrary precision and symbolic computations.
It would also be good to check what other libraries that we already use or could easily use also provide implementations of SVD.
comment:7 in reply to: ↑ 6 Changed 3 months ago by
Replying to mkoeppe:
Replying to ghhonglizhaobob:
in implementing the SVD, should we resort to external libraries such as
numpy
, or is it a better practice to usesage
methods whenever possible?In Sage we support a wide range of rings for the arithmetic, and consequently often use multiple libraries for the implementation and also have an inSage generic implementation.
The existing implementation of
SVD
insrc/sage/matrix/matrix_double_dense.pyx
just callsscipy.linalg.svd
.It would be quite useful to add a generic implementation that only uses the general methods that Sage matrices offer. In that way, we could have access to arbitrary precision and symbolic computations.
It would also be good to check what other libraries that we already use or could easily use also provide implementations of SVD.
I think currently SVD()
doesn't support other fields such as ZZ
, or QQ
. We may be restricted to RDF
if we choose to use matrix_double_dense.pyx
.
comment:8 followup: ↓ 9 Changed 3 months ago by
Yes, that's right  and that's I think also exactly what scipy.linalg.svd
provides. That's why I said that it will be good to check what other implementations are available in other software. A quick search for "arbitrary precision svd" did not lead me to good results though
comment:9 in reply to: ↑ 8 ; followup: ↓ 10 Changed 3 months ago by
Replying to mkoeppe:
Yes, that's right  and that's I think also exactly what
scipy.linalg.svd
provides. That's why I said that it will be good to check what other implementations are available in other software. A quick search for "arbitrary precision svd" did not lead me to good results though
Could we consider symbolic SVD such as in MATLAB or sympy
？ This way we can preserve the QQ
structure, however I feel svd on ZZ
will be a bit demanding..
comment:10 in reply to: ↑ 9 ; followup: ↓ 12 Changed 3 months ago by
Replying to ghhonglizhaobob:
Could we consider symbolic SVD such as in MATLAB or
sympy
？ This way we can preserve the
Do you have an example or link that illustrates what you have in mind?
comment:11 followup: ↓ 13 Changed 3 months ago by
 Branch set to u/ghhonglizhaobob/finiterankfreemodulemorphism__add_method_svd__singular_value_decomposition_
comment:12 in reply to: ↑ 10 Changed 3 months ago by
 Branch u/ghhonglizhaobob/finiterankfreemodulemorphism__add_method_svd__singular_value_decomposition_ deleted
Replying to mkoeppe:
Replying to ghhonglizhaobob:
Could we consider symbolic SVD such as in MATLAB or
sympy
？ This way we can preserve theDo you have an example or link that illustrates what you have in mind?
In sympy
, by Matrix.singular_value_decomposition()
which would return symbolic results: https://docs.sympy.org/latest/modules/matrices/matrices.html
comment:13 in reply to: ↑ 11 Changed 3 months ago by
Replying to ghhonglizhaobob:
Pushed a preliminary version which only deals with RDF
, added a method diagonalize()
in FiniteRankFreeModuleMorphism
.
comment:14 Changed 3 months ago by
 Branch set to u/ghhonglizhaobob/finiterankfreemodulemorphism__add_method_svd__singular_value_decomposition_
comment:15 followup: ↓ 17 Changed 3 months ago by
 Commit set to b141a4f5a95015fd50a61d4a929d76844b488f79
Be careful what you push. You accidentally pushed your from the built generated files. The source code you want to modify is in src/sage/
.
Can you please rebase the branch accordingly?
comment:16 Changed 3 months ago by
 Commit changed from b141a4f5a95015fd50a61d4a929d76844b488f79 to 38bcecc8796d95eb8946ba51eb4f807ca9edef99
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
38bcecc  edited SVD

comment:17 in reply to: ↑ 15 ; followup: ↓ 19 Changed 3 months ago by
Replying to ghmjungmath:
Be careful what you push. You accidentally pushed your from the built generated files. The source code you want to modify is in
src/sage/
.Can you please rebase the branch accordingly?
Sorry, I have reset and pushed the code again.
comment:18 Changed 3 months ago by
I've opened #32171 (Matrix: Add generic SVD method using sympy)
comment:19 in reply to: ↑ 17 Changed 3 months ago by
Replying to ghhonglizhaobob:
Sorry, I have reset and pushed the code again.
Don't worry. Thanks for taking care of it. :)
comment:20 Changed 3 months ago by
When ready for review, please set author name here on the ticket to your full name, and set to "needs_review".
comment:21 Changed 3 months ago by
The EXAMPLES
section should probably be extended so that one can see the effect of the function.
Some development tools that help with this:
./sage fixdoctests src/sage/tensor/modules/free_module_morphism.py
will run the doctests and update the output./sage docbuild reference/tensor_free_modules html
will build the HMTL documentation  looking at it may reveal mistakes in the markup of the docstring
comment:22 Changed 3 months ago by
 Milestone changed from sage9.4 to sage9.5
Replying to mkoeppe:
Sorry for asking a naive question... In the description, what does
RDF
refer to ("this operation is currently available for matrices overRDF
")?