Opened 21 months ago

Last modified 3 months ago

#29177 needs_work defect

Make echelon_form(transformation=True) return transformation matrix

Reported by: klee Owned by:
Priority: minor Milestone: sage-9.5
Component: linear algebra Keywords:
Cc: slelievre Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by klee)

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 (16)

comment:1 follow-up: Changed 21 months ago by nbruin

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.

comment:2 in reply to: ↑ 1 ; follow-up: Changed 21 months ago by klee

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 ; follow-up: Changed 21 months ago by 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 of transformation.

comment:4 in reply to: ↑ 3 ; follow-up: Changed 21 months ago by klee

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 of transformation.

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 ; follow-up: Changed 21 months ago by nbruin

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 case-by-case. 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 21 months ago by klee

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 case-by-case. 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 21 months ago by klee

  • Authors set to Kwankyu Lee
  • Branch set to u/klee/29177
  • Description modified (diff)

comment:8 Changed 21 months ago by git

  • Commit set to deaf629b99df7a4a95fde72808d33b276caf7712

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

deaf629Fix the docstring of echelon_form()

comment:9 Changed 21 months ago by klee

  • Description modified (diff)
  • Status changed from new to needs_review

comment:10 Changed 21 months ago by klee

  • Description modified (diff)

comment:11 follow-up: Changed 21 months ago by slelievre

  • 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 21 months ago by klee

  • Authors Kwankyu Lee deleted
  • 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 non-field rings.

matrix_integer_dense support echelon_form(transformation=True)for flint and padic backends.

comment:13 Changed 19 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.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 14 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:15 Changed 8 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:16 Changed 3 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.

Note: See TracTickets for help on using tickets.