Reimplementation of weak_popov_form for matrices

[ketzu]

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 mulders-storjohann 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/tech-reports/3xx/356.pdf

[jsrn]

Note to passers-by: ketzu is in the process of writing a patch for this.

[ketzu]

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.

[git]

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

​b15a340	Doc changes.
​9d1d165	Docstring update.
​72e7817	Added SEEALSO entry
​73c3ff0	Again minor doc changes.
​401dbd4	Added two examples.
​9d708b9	Added a few examples

[git]

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

​f5a4456

Bugfix for zero lines and correction of an example.

[git]

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

​ebf38b6

Added commentary for understanding the code.

[git]

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

​e464be9

counting zero lines instead of negativ indices, changed to coding conventions

[dlucas]

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.

Documentation-related 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 Python-related 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 mulders-storjohann algorithm.

I think it will be more explicit for the user to say something like "This is a helper function for Mulders-Storjohann 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) mulders-storjohann 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 de-deprecate it) which will do the transformations to get the wPf of the input using mulders-storjohann 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.

[klee]

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.

[jsrn]

Closing as wontfix cf #21024.

[embray]

Closing tickets in the sage-duplicate/invalid/wontfix module with positive_review (i.e. someone has confirmed they should be closed).