weak popov form does not compute weak popov form

2b95a2b7-8aad-4035-aedd-60fac31272a9 commented 10 years ago

While working on the sage.matrix.matrix2.weak_popov_form (for sage.matrix.matrix_misc.weak_popov_form applies the same) method for performance issues I noticed something.

The weak Popov form as defined in [MS] is not computed by this method. The other references do not call this form weak Popov form, it is a les restrictive definition for a certain row reduced form of matrix.

Followup ticket for reimplementation of wpf: #16742 and #16896.

[MS] T. Mulders, A. Storjohann, "On lattice reduction for polynomial matrices," J. Symbolic Comput. 35 (2003), no. 4, 377--401

Comment of weak_popov_form:

OUTPUT:

      A 3-tuple !`(W,N,d)`   consisting of:

      1. !`W`   - a matrix over !`k(x)`   giving a weak the Popov form of self
      2. !`N`   - a matrix over !`k[x]`   representing row operations used to
          transform !`self`   to !`W`  
      3. !`d`   - degree of respective columns of W; the degree of a column is
         the maximum of the degree of its elements

CC: @johanrosenkilde

Component: linear algebra

Keywords: weak-popov-form matrix

Author: David Mödinger

Branch/Commit: c19cc11

Reviewer: David Lucas

Issue created by migration from https://trac.sagemath.org/ticket/16888

2b95a2b7-8aad-4035-aedd-60fac31272a9 commented 10 years ago

Changed keywords from none to weak-popov-form matrix

2b95a2b7-8aad-4035-aedd-60fac31272a9 commented 10 years ago

Description changed:

--- 
+++ 
@@ -1 +1,26 @@
+While working on the sage.matrix.matrix2.weak_popov_form method for performance issues I noticed something.

+The weak Popov form as defined in [MS] is not computed by this method. The other references do not call this form weak Popov form, it is a les restrictive definition for a certain row reduced form of matrix.
+
+While renaming I see this as a chance to correct some (in my opinion) strange behavior of the method:
+
+1. It takes a parameter ascend but does not relay it to the function (it is entirely ignored)
+2. It takes a parameter ascend which is not related to either weak Popov form or row reduced form
+3. It returns a 3-touple even though it is only expected to compute the wpf/rrf
+4. d of the 3-touple and the sorting is unnecessary computation and should probably not be part of the method.
+5. while N is nice to check some things, in my opinion it should only be given if asked for
+
+[MS] T. Mulders, A. Storjohann, "On lattice reduction for polynomial
+          matrices," J. Symbolic Comput. 35 (2003), no. 4, 377--401
+
+Comment of weak_popov_form:
+
+        OUTPUT:
+
+        A 3-tuple !`(W,N,d)` consisting of:
+
+        1. !`W` - a matrix over !`k(x)` giving a weak the Popov form of self
+        2. !`N` - a matrix over !`k[x]` representing row operations used to
+            transform !`self` to !`W`
+        3. !`d` - degree of respective columns of W; the degree of a column is
+           the maximum of the degree of its elements

2b95a2b7-8aad-4035-aedd-60fac31272a9 commented 10 years ago

Description changed:

--- 
+++ 
@@ -10,17 +10,19 @@
 4. d of the 3-touple and the sorting is unnecessary computation and should probably not be part of the method.
 5. while N is nice to check some things, in my opinion it should only be given if asked for

+Followup ticket for reimplementation of wpf: [ticket:16742 #16742.]
+
 [MS] T. Mulders, A. Storjohann, "On lattice reduction for polynomial
-          matrices," J. Symbolic Comput. 35 (2003), no. 4, 377--401
+          matrices," J. Symbolic Comput. 35 (2003), no. 4, 377--401

 Comment of weak_popov_form:

-        OUTPUT:
-
-        A 3-tuple !`(W,N,d)` consisting of:
-
-        1. !`W` - a matrix over !`k(x)` giving a weak the Popov form of self
-        2. !`N` - a matrix over !`k[x]` representing row operations used to
-            transform !`self` to !`W`
-        3. !`d` - degree of respective columns of W; the degree of a column is
-           the maximum of the degree of its elements
+  OUTPUT:
+ 
+         A 3-tuple !`(W,N,d)`  consisting of:
+ 
+         1. !`W`  - a matrix over !`k(x)`  giving a weak the Popov form of self
+         2. !`N`  - a matrix over !`k[x]`  representing row operations used to
+             transform !`self`  to !`W` 
+         3. !`d`  - degree of respective columns of W; the degree of a column is
+            the maximum of the degree of its elements

2b95a2b7-8aad-4035-aedd-60fac31272a9 commented 10 years ago

Branch: u/ketzu/weak_popov_form_does_not_compute_weak_popov_form

2b95a2b7-8aad-4035-aedd-60fac31272a9 commented 10 years ago

Commit: 970fde5

2b95a2b7-8aad-4035-aedd-60fac31272a9 commented 10 years ago

comment:4

I think there should be a keyword ("transposition=False" oder something) to indicate the matrix N is wanted. Also I am not completely sure I did the deprecations right in any way.

New commits:

970fde5 Rename of weak_popov_form() to row_reduced_form() added deprecation warning, rework of the use of the ascend parameter, removed sorting and returning d if ascend is not set.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 970fde5 to 12755f1

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

12755f1 Reduced to be a renaming only.

2b95a2b7-8aad-4035-aedd-60fac31272a9 commented 10 years ago

Author: David Mödinger

2b95a2b7-8aad-4035-aedd-60fac31272a9 commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,16 +1,8 @@
-While working on the sage.matrix.matrix2.weak_popov_form method for performance issues I noticed something.
+While working on the sage.matrix.matrix2.weak_popov_form (for sage.matrix.matrix_misc.weak_popov_form applies the same) method for performance issues I noticed something.

 The weak Popov form as defined in [MS] is not computed by this method. The other references do not call this form weak Popov form, it is a les restrictive definition for a certain row reduced form of matrix.

-While renaming I see this as a chance to correct some (in my opinion) strange behavior of the method:
-
-1. It takes a parameter ascend but does not relay it to the function (it is entirely ignored)
-2. It takes a parameter ascend which is not related to either weak Popov form or row reduced form
-3. It returns a 3-touple even though it is only expected to compute the wpf/rrf
-4. d of the 3-touple and the sorting is unnecessary computation and should probably not be part of the method.
-5. while N is nice to check some things, in my opinion it should only be given if asked for
-
-Followup ticket for reimplementation of wpf: [ticket:16742 #16742.]
+Followup ticket for reimplementation of wpf: #16742 and #16896.

 [MS] T. Mulders, A. Storjohann, "On lattice reduction for polynomial
           matrices," J. Symbolic Comput. 35 (2003), no. 4, 377--401
@@ -18,11 +10,11 @@
 Comment of weak_popov_form:

   OUTPUT:
- 
-         A 3-tuple !`(W,N,d)`  consisting of:
- 
-         1. !`W`  - a matrix over !`k(x)`  giving a weak the Popov form of self
-         2. !`N`  - a matrix over !`k[x]`  representing row operations used to
-             transform !`self`  to !`W` 
-         3. !`d`  - degree of respective columns of W; the degree of a column is
-            the maximum of the degree of its elements
+  
+          A 3-tuple !`(W,N,d)`   consisting of:
+  
+          1. !`W`   - a matrix over !`k(x)`   giving a weak the Popov form of self
+          2. !`N`   - a matrix over !`k[x]`   representing row operations used to
+              transform !`self`   to !`W`  
+          3. !`d`   - degree of respective columns of W; the degree of a column is
+             the maximum of the degree of its elements

2b95a2b7-8aad-4035-aedd-60fac31272a9 commented 10 years ago

New commits:

12755f1 Reduced to be a renaming only.

New commits:

12755f1 Reduced to be a renaming only.

2b95a2b7-8aad-4035-aedd-60fac31272a9 commented 10 years ago

comment:7

sagemath / sage

weak popov form does not compute weak popov form #16888