Opened 7 years ago
Closed 4 years ago
#16742 closed enhancement (wontfix)
Reimplementation of weak_popov_form for matrices
Reported by:  ketzu  Owned by:  

Priority:  minor  Milestone:  sageduplicate/invalid/wontfix 
Component:  performance  Keywords:  matrix weakpopovform #16739 sd75 
Cc:  jsrn, dlucas, cpernet  Merged in:  
Authors:  David Mödinger  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/ketzu/overload_for_faster_weak_popov_form (Commits, GitHub, GitLab)  Commit:  e464be9e38cd84c8d52d9c117724e4a9f0ce01e7 
Dependencies:  #16888,#16896  Stopgaps: 
Description (last modified by )
The target of this ticket is to enhance the function weak_popov of the matrix interface. The function should transform the matrix in weak popov form, it will use muldersstorjohann algorithm and should be much faster than the current implementation but will not work for polynomials over a fraction field only for polynomial rings over finite fields.
This ticket is independent from but connected to #16739.
Short description of weak popov form: Let R be an ordered Ring and Amxn a matrix over R. The leading position of a row is called the position i in [1,m) such that the order of A[i,_] is maximal within the row. If there are multiple entries with the maximum order, the highest i is the leading position (the furthest to the right in the matrix). A is in weak popov form if all leading positions are different (zero lines ignored).
The function will implement this only for polynomial rings, the order function is the degree of the polynomial. Example:
[x2+1, x]
[x, x+1]
is in weak popov form: Row 1 has the degrees 2 and 1, the leading position is for i=0, row 2 has two times degree 1 so the higher i is chosen with i=1.
[x2+1, x]
[x,0]
is NOT in weak popov form, row 1 has now degrees 1 and 1, so the leading position is i=0 as in row 1.
See: [MS] Mulders, Storjohann, On Lattice Reduction for Polynomial Matrices, ftp://ftp.inf.ethz.ch/pub/publications/techreports/3xx/356.pdf
Change History (25)
comment:1 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:2 Changed 7 years ago by
 Component changed from PLEASE CHANGE to performance
 Description modified (diff)
 Keywords matrix weakpopovform added
 Priority changed from major to minor
comment:3 Changed 7 years ago by
 Keywords #16739 added
comment:4 Changed 7 years ago by
 Cc jsrn added
comment:5 Changed 7 years ago by
 Type changed from PLEASE CHANGE to enhancement
comment:6 Changed 7 years ago by
 Description modified (diff)
comment:7 Changed 7 years ago by
 Description modified (diff)
comment:8 Changed 7 years ago by
 Description modified (diff)
comment:9 Changed 7 years ago by
comment:10 Changed 7 years ago by
 Branch set to u/ketzu/overload_for_faster_weak_popov_form
comment:11 Changed 7 years ago by
 Commit set to 60a9dbe8e754e7cebf4da0d3913a721e52c4ce48
Doctests / Examples are still missing
New commits:
f0afa2b  Initial implementation in matrix/matrix_weak_popov.pyx

46c14d8  Renamed to more apropriate weak_popov.pyx, added to module_list.py modules list.

44b5b83  Hook into weak_popov_form(self) by keyword implementation, value used so far is 'cython'.

60a9dbe  Added boolean keyword 'transposition' to mark computation of a matrix U such that U*A=A.wpf(). This is to check correctness of a computation. If B = copy(A) and after A.weak_popov_form() U.is_invertible()==True and A.is_weak_popov()==True then A is in weak popov form and is unimodular equivalent to B its origin.

comment:12 Changed 7 years ago by
comment:13 Changed 7 years ago by
 Commit changed from 60a9dbe8e754e7cebf4da0d3913a721e52c4ce48 to 9d708b99c8bd4ec639352b9355d94b9129ff9c0f
comment:14 Changed 7 years ago by
 Commit changed from 9d708b99c8bd4ec639352b9355d94b9129ff9c0f to f5a445639a8ce20aaff60a8679fa12c7eb9fd4ac
Branch pushed to git repo; I updated commit sha1. New commits:
f5a4456  Bugfix for zero lines and correction of an example.

comment:15 Changed 7 years ago by
 Commit changed from f5a445639a8ce20aaff60a8679fa12c7eb9fd4ac to ebf38b673c14d7e83fd15005ac479fa04536330d
Branch pushed to git repo; I updated commit sha1. New commits:
ebf38b6  Added commentary for understanding the code.

comment:16 Changed 7 years ago by
 Commit changed from ebf38b673c14d7e83fd15005ac479fa04536330d to e464be9e38cd84c8d52d9c117724e4a9f0ce01e7
Branch pushed to git repo; I updated commit sha1. New commits:
e464be9  counting zero lines instead of negativ indices, changed to coding conventions

comment:17 Changed 7 years ago by
 Description modified (diff)
comment:18 Changed 7 years ago by
 Dependencies set to #16888
 Summary changed from overload for faster weak_popov_form to Reimplementation of weak_popov_form for matrices
comment:19 Changed 6 years ago by
 Cc dlucas added
 Milestone changed from sage6.4 to sage6.7
 Status changed from new to needs_review
Hello,
I'm working on the review for tickets related to the weal Popov form problem. Even if this one was not on needs_review
state, I considered that it was quite old, and did not change for a while, so I took the liberty to review it.
General comments
g1) Several conflicts arise if merge with latest Sage beta. They need to be fixed.
g2) There are some trailing whitespaces in the files you modified. It will be nice to remove them.
g3) There are errors while building the documentation. To check if the documentation builds as it should, and check if the html output looks good or not, you can use sage docbuild reference/myFolder html
, replacing my folder by the part of Sage you were working on. Here, it will be reference/matrices
.
Documentationrelated comments
d1) While writing documentation, you can use double backticks to have a nice formatting for variables. If you use simple backticks, it will format it as LaTeX test, which will just be italic if used on simple text. It is advised in Sage documentation to use double backticks around variables in the output block. Besides, it looks better for variables, or Pythonrelated keyworkds (like True
, or None
) to use this syntax.
d2) The title of the file weak_popov.pyx
is splitted on the html documentation. Write the title in one line, or use an underscore to avoid this.
d3) After the merge with latest beta, especially with the content of #16888, doctests of weak_popov.pyx
are broken as weak_popov_form
method throws a deprecation warning.
d4) I think it's better to call directly the method you're doctesting. In mulders_storjohann
's doctests, call mulders_storjohann
instead of weak_popov
.
d5) On line 152 (examples for mulders_storjohann
) in weak_popov
, you say "Generally matrices in weak popov form will just be returned". I think they will always be returned. In that case, can you remove "generally"? If I'm wrong, can you add an example in which we input a matrix in wPf which is not returned as is?
d6) You can get a nice formatting on the ALGORITHM
block (weak_popov.py:102
) if you use only one colon instead of two after the ALGORITHM
keyword.
d7) On both helper methods you wrote in weak_popov.pyx
, you have this block:
.. note:: This method is used in the muldersstorjohann algorithm.
I think it will be more explicit for the user to say something like "This is a helper function for MuldersStorjohann algorithm and should only be used internally".
d8) At the beginning of each function, you write something like "Function to do something". You can go straight to the point, and write directly "Returns this" or "Computes that".
d9) In simmple_transformation
's doc, input parameter U
is not documented.
Code and design related comments
c1) muldersstorjohann
method takes a matrix M
as an input, then modifies it in place, and outputs the modified matrix. I think it's not an intuitive behaviour. It should either modify the input in place, and output nothing or copy the input and output the modified copy.
c2) With the merge of #16888, old weak_popov_form
method will be deprecated and renamed row_reduced_form
. Which means that, without any changes, one will need to call M.row_reduced_form(implementation="cython")
to get the weak Popov form of M
... Which is not intuitive at all. What I suggest here is to reinstate the method weak_popov_form
(as it will compute the wPf, we can dedeprecate it) which will do the transformations to get the wPf of the input using muldersstorjohann
method. By doing that, we keep the row_reduced_form
method for users who absolutely want the row reduced form of their matrices, and have a real weak Popov form computation with methods explicitely named.
c3) As #16896 changes the calling conventions of row_reduced_from
, I think one the two tickets should depend on the other one to be sure we get what we want in the end, namely a wPf method and a rrf method with simplfied calling conventions.
comment:20 Changed 6 years ago by
 Status changed from needs_review to needs_work
comment:21 Changed 6 years ago by
 Dependencies changed from #16888 to #16888,#16896
comment:22 Changed 5 years ago by
 Cc cpernet added
 Keywords sd75 added
comment:23 Changed 4 years ago by
In #21024, I reimplemented this "reimplementation of weak popov form" in the _weak_popov_form
in a newly added matrix_polynomial_dense.pyx
file. I did timing comparisons between my implementation of MS algorithm with the implementation in this ticket. The result is that the implementation in _weak_popov_form
is much faster than the latter. So if #21024 is merged, then this ticket can be safely discarded.
comment:24 Changed 4 years ago by
 Milestone changed from sage6.7 to sageduplicate/invalid/wontfix
 Status changed from needs_work to positive_review
Closing as wontfix cf #21024.
comment:25 Changed 4 years ago by
 Resolution set to wontfix
 Status changed from positive_review to closed
Closing tickets in the sageduplicate/invalid/wontfix module with positive_review (i.e. someone has confirmed they should be closed).
Note to passersby: ketzu is in the process of writing a patch for this.