Opened 5 years ago

Closed 2 years ago

#16742 closed enhancement (wontfix)

Reimplementation of weak_popov_form for matrices

Reported by: ketzu Owned by:
Priority: minor Milestone: sage-duplicate/invalid/wontfix
Component: performance Keywords: matrix weak-popov-form #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) Commit: e464be9e38cd84c8d52d9c117724e4a9f0ce01e7
Dependencies: #16888,#16896 Stopgaps:

Description (last modified by 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

Change History (25)

comment:1 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:2 Changed 5 years ago by ketzu

  • Component changed from PLEASE CHANGE to performance
  • Description modified (diff)
  • Keywords matrix weak-popov-form added
  • Priority changed from major to minor

comment:3 Changed 5 years ago by ketzu

  • Keywords #16739 added

comment:4 Changed 5 years ago by ketzu

  • Cc jsrn added

comment:5 Changed 5 years ago by ketzu

  • Type changed from PLEASE CHANGE to enhancement

comment:6 Changed 5 years ago by ketzu

  • Description modified (diff)

comment:7 Changed 5 years ago by ketzu

  • Description modified (diff)

comment:8 Changed 5 years ago by ketzu

  • Description modified (diff)

comment:9 Changed 5 years ago by jsrn

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

comment:10 Changed 5 years ago by ketzu

  • Branch set to u/ketzu/overload_for_faster_weak_popov_form

comment:11 Changed 5 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 5 years ago by ketzu (previous) (diff)

comment:12 Changed 5 years ago by ketzu

  • Authors set to David Mödinger

comment:13 Changed 5 years ago by git

  • Commit changed from 60a9dbe8e754e7cebf4da0d3913a721e52c4ce48 to 9d708b99c8bd4ec639352b9355d94b9129ff9c0f

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

b15a340Doc changes.
9d1d165Docstring update.
72e7817Added SEEALSO entry
73c3ff0Again minor doc changes.
401dbd4Added two examples.
9d708b9Added a few examples

comment:14 Changed 5 years ago by git

  • Commit changed from 9d708b99c8bd4ec639352b9355d94b9129ff9c0f to f5a445639a8ce20aaff60a8679fa12c7eb9fd4ac

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

f5a4456Bugfix for zero lines and correction of an example.

comment:15 Changed 5 years ago by git

  • Commit changed from f5a445639a8ce20aaff60a8679fa12c7eb9fd4ac to ebf38b673c14d7e83fd15005ac479fa04536330d

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

ebf38b6Added commentary for understanding the code.

comment:16 Changed 5 years ago by git

  • Commit changed from ebf38b673c14d7e83fd15005ac479fa04536330d to e464be9e38cd84c8d52d9c117724e4a9f0ce01e7

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

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

comment:17 Changed 5 years ago by ketzu

  • Description modified (diff)

comment:18 Changed 5 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 5 years ago by dlucas

  • Cc dlucas added
  • 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.

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.

comment:20 Changed 5 years ago by dlucas

  • Status changed from needs_review to needs_work

comment:21 Changed 4 years ago by ketzu

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

comment:22 Changed 3 years ago by cpernet

  • Cc cpernet added
  • Keywords sd75 added

comment:23 Changed 3 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 3 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 2 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.