Opened 15 months ago
Last modified 2 months ago
#29177 needs_work defect
Make echelon_form(transformation=True) return transformation matrix
Reported by:  klee  Owned by:  

Priority:  minor  Milestone:  sage9.4 
Component:  linear algebra  Keywords:  
Cc:  slelievre  Merged in:  
Authors:  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
Contrary to user expectation, we get:
sage: m = matrix(GF(5), 3, [1,2,3,4,5,6,7,8,9]) sage: m [1 2 3] [4 0 1] [2 3 4] sage: m.echelon_form(transformation=True) [1 0 4] [0 1 2] [0 0 0] sage: m = matrix(QQ, 3, [1,2,3,4,5,6,7,8,9]) sage: m.echelon_form(transformation=True) [ 1 0 1] [ 0 1 2] [ 0 0 0]
No transformation matrix is returned. The docstring of echelon_form() says
 "transformation"  boolean. Whether to also return the transformation matrix. Some matrix backends do not provide this information, in which case this option is ignored.
So the default backends does not produce a transformation matrix!
In fact, the "transformation" option is rarely supported.
Change History (15)
comment:1 followup: ↓ 2 Changed 15 months ago by
comment:2 in reply to: ↑ 1 ; followup: ↓ 3 Changed 15 months ago by
Replying to nbruin:
I suspect that it's going to be better to use a good backend and augment than to switch to a backend that produces the transformation matrix via other means.
I agree. So we can make backend choice independent from transformation=True
.
comment:3 in reply to: ↑ 2 ; followup: ↓ 4 Changed 15 months ago by
Replying to klee:
I agree. So we can make backend choice independent from
transformation=True
.
Well ... it means that if backend=auto
(or whatever the default option is), a good choice for the base ring should be made that takes into account the value of transformation
.
comment:4 in reply to: ↑ 3 ; followup: ↓ 5 Changed 15 months ago by
Replying to nbruin:
Replying to klee:
I agree. So we can make backend choice independent from
transformation=True
.Well ... it means that if
backend=auto
(or whatever the default option is), a good choice for the base ring should be made that takes into account the value oftransformation
.
I tried to early detect whether a backend supports transformation matrix. Each backend that does not compute tansformation matrix may raise an exception when given the transformation=True
argument. If such an exception is raised, then we resort to the default strategy usingextended_echelon_form()
method. But this would add overhead of not much worth to each backend...
comment:5 in reply to: ↑ 4 ; followup: ↓ 6 Changed 15 months ago by
Replying to klee:
I tried to early detect whether a backend supports transformation matrix. Each backend that does not compute tansformation matrix may raise an exception when given the
transformation=True
argument. If such an exception is raised, then we resort to the default strategy usingextended_echelon_form()
method. But this would add overhead of not much worth to each backend...
It looks to me that this routine gets overridden on a lot of matrix classes, in which the various backends (or "algorithms") are implemented casebycase. For instance, the one on integer matrices seems to cast an error for certain algorithms if transformation matrix is not specified.
Given that the minimal interface seems to be that transformation matrices are *not* supported, I guess the "generic" routine could just do this by augmenting. You'll have to go through all the special cases anyway, and since the backends are explicitly known there, you can just tune for each if augmentation or asking for a transformation matrix is the right thing to do.
comment:6 in reply to: ↑ 5 Changed 15 months ago by
Replying to nbruin:
It looks to me that this routine gets overridden on a lot of matrix classes, in which the various backends (or "algorithms") are implemented casebycase. For instance, the one on integer matrices seems to cast an error for certain algorithms if transformation matrix is not specified.
Right.
Given that the minimal interface seems to be that transformation matrices are *not* supported, I guess the "generic" routine could just do this by augmenting. You'll have to go through all the special cases anyway, and since the backends are explicitly known there, you can just tune for each if augmentation or asking for a transformation matrix is the right thing to do.
I looked through all echelon_form()
definitions in
matrix_gf2e_dense
matrix_mod2_dense
matrix_modn_dense_template
matrix_cyclo_dense
matrix_integer_dense
matrix_mpolynomial_dense
matrix_rational_dense
matrix_rational_sparse
My conclusion is that echelon_form()
basically does not support transformation
option, except matrices over ZZ
and uncommon rings.
So I decided to just clarify the misleading docstring.
comment:7 Changed 15 months ago by
 Branch set to u/klee/29177
 Description modified (diff)
comment:8 Changed 15 months ago by
 Commit set to deaf629b99df7a4a95fde72808d33b276caf7712
Branch pushed to git repo; I updated commit sha1. New commits:
deaf629  Fix the docstring of echelon_form()

comment:9 Changed 15 months ago by
 Description modified (diff)
 Status changed from new to needs_review
comment:10 Changed 15 months ago by
 Description modified (diff)
comment:11 followup: ↓ 12 Changed 14 months ago by
 Cc slelievre added
 Summary changed from No transformation matrix returns from echelon_form(transformation=True) to Make echelon_form(transformation=True) return transformation matrix
comment:12 in reply to: ↑ 11 Changed 14 months ago by
 Branch u/klee/29177 deleted
 Commit deaf629b99df7a4a95fde72808d33b276caf7712 deleted
 Description modified (diff)
 Status changed from needs_review to needs_work
For your information:
module  has echelonize()?  has echelon_form()? 
matrix2  O  O 
matrix_gf2e_dense  O  X 
matrix_mod2_dense  O  X 
matrix_modn_dense_template  O  X 
matrix_cyclo_dense  X  O 
matrix_integer_dense  X  O 
matrix_mpolynomial_dense  O  O 
matrix_rational_dense  O  O 
matrix_rational_sparse  O  O 
matrix2
support echelon_form(transformation=True)
for matrices over nonfield rings.
matrix_integer_dense
support echelon_form(transformation=True)
for flint and padic backends.
comment:13 Changed 12 months ago by
 Milestone changed from sage9.1 to sage9.2
Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.
comment:14 Changed 8 months ago by
 Milestone changed from sage9.2 to sage9.3
comment:15 Changed 2 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.
As remarked before, if one augments the matrix on the right with an identity matrix, then that keeps track of the row operations and hence the transformation matrix. A default strategy to get the transformation matrix is to do this augmentation trick. You can override this with other tracking strategies for backends that support it. It's probably worth doing some timings to see what the penalty of this augmentation is. I suspect that it's going to be better to use a good backend and augment than to switch to a backend that produces the transformation matrix via other means.