Opened 8 years ago

Closed 5 years ago

# Reimplementation of weak_popov_form for matrices

Reported by: Owned by: ketzu minor sage-duplicate/invalid/wontfix performance matrix weak-popov-form #16739 sd75 jsrn, dlucas, cpernet David Mödinger N/A u/ketzu/overload_for_faster_weak_popov_form e464be9e38cd84c8d52d9c117724e4a9f0ce01e7 #16888,#16896

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

### comment:1 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

### comment:2 Changed 8 years ago by ketzu

• Component changed from PLEASE CHANGE to performance
• Description modified (diff)
• Priority changed from major to minor

### comment:5 Changed 8 years ago by ketzu

• Type changed from PLEASE CHANGE to enhancement

### comment:6 Changed 8 years ago by ketzu

• Description modified (diff)

### comment:7 Changed 8 years ago by ketzu

• Description modified (diff)

### comment:8 Changed 8 years ago by ketzu

• Description modified (diff)

### comment:9 Changed 8 years ago by jsrn

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

### comment:11 Changed 8 years ago by ketzu

• 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.`
Last edited 8 years ago by ketzu (previous) (diff)

### comment:12 Changed 8 years ago by ketzu

• Authors set to David Mödinger

### comment:13 Changed 8 years ago by git

• Commit changed from 60a9dbe8e754e7cebf4da0d3913a721e52c4ce48 to 9d708b99c8bd4ec639352b9355d94b9129ff9c0f

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`

### comment:14 Changed 8 years ago by git

• 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 8 years ago by git

• 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 8 years ago by git

• 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 8 years ago by ketzu

• Description modified (diff)

### comment:18 Changed 8 years ago by ketzu

• Dependencies set to #16888
• Summary changed from overload for faster weak_popov_form to Reimplementation of weak_popov_form for matrices

### comment:19 Changed 7 years ago by dlucas

• Milestone changed from sage-6.4 to sage-6.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.

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`.

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.

### comment:20 Changed 7 years ago by dlucas

• Status changed from needs_review to needs_work

### comment:21 Changed 7 years ago by ketzu

• Dependencies changed from #16888 to #16888,#16896

### comment:23 Changed 6 years ago by 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.

### comment:24 Changed 5 years ago by jsrn

• Milestone changed from sage-6.7 to sage-duplicate/invalid/wontfix
• Status changed from needs_work to positive_review

Closing as wontfix cf #21024.

### comment:25 Changed 5 years ago by embray

• Resolution set to wontfix
• Status changed from positive_review to closed

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

Note: See TracTickets for help on using tickets.