Opened 9 years ago

Closed 2 years ago

#13584 closed enhancement (wontfix)

Add rcm to matrix/matrix2.pyx

Reported by: r.gaia.cs Owned by: r.gaia.cs
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: linear algebra Keywords: matrix, rcm
Cc: embray Merged in:
Authors: William Stein, Rob Beezer, Frédéric Chapoton, Ralf Stephan Reviewers:
Report Upstream: N/A Work issues: Cython issues
Branch: public/ticket/13584 (Commits, GitHub, GitLab) Commit: c3fb93fe197a6d47643fc66f7beb8cd06888c551
Dependencies: Stopgaps:

Status badges

Description (last modified by rws)

It will be great to have the RCM (Reverse Cuthill-McKee) for a matrix.

Note that #13583 is for graphs while this is for matrix. The reason to implement the same algorithm twice is because speedy.

Attachments (1)

trac_13584-matrix_rcm.patch (10.4 KB) - added by r.gaia.cs 9 years ago.

Download all attachments as: .zip

Change History (26)

comment:1 Changed 9 years ago by r.gaia.cs

  • Status changed from new to needs_review

comment:2 Changed 9 years ago by r.gaia.cs

  • Description modified (diff)

Changed 9 years ago by r.gaia.cs

comment:3 Changed 9 years ago by r.gaia.cs

  • Dependencies #13565, #13581 deleted

comment:4 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:5 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:6 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:7 Changed 7 years ago by rws

  • Branch set to u/rws/add_rcm_to_matrix_matrix2_pyx

comment:8 Changed 7 years ago by rws

  • Commit set to 9698b503b097ce7ccecc8770611a53c78611236e
  • Description modified (diff)

New commits:

9698b5013584: Add some matrix to doctest of rcm().

comment:9 Changed 7 years ago by rws

  • Status changed from needs_review to needs_work
[matrices ] docstring of sage.matrix.matrix2.Matrix:8: WARNING: Definition list ends without a blank line; unexpected unindent.
[matrices ] docstring of sage.matrix.matrix2.Matrix:16: WARNING: Definition list ends without a blank line; unexpected unindent.
[matrices ] docstring of sage.matrix.matrix2.Matrix.C:2: WARNING: Definition list ends without a blank line; unexpected unindent.

comment:10 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:11 Changed 6 years ago by chapoton

  • Branch changed from u/rws/add_rcm_to_matrix_matrix2_pyx to public/ticket/13584
  • Commit changed from 9698b503b097ce7ccecc8770611a53c78611236e to ba6c01d594276fb29ea96a4c5718933251c2c5ea

I have formatted the doc. There is a doctest missing.


New commits:

e6a316eMerge branch 'u/rws/add_rcm_to_matrix_matrix2_pyx' into 6.5.rc3
ba6c01dtrac #13584 doc formatting

comment:12 Changed 6 years ago by git

  • Commit changed from ba6c01d594276fb29ea96a4c5718933251c2c5ea to c3fb93fe197a6d47643fc66f7beb8cd06888c551

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

c3fb93f13584: add missing doctest

comment:13 Changed 6 years ago by rws

  • Authors changed from was, mmarco, rbeezer to William A. Stein, Marco Mezzarobba, Rob Beezer, Frédéric Chapoton, Ralf Stephan
  • Status changed from needs_work to needs_review

comment:14 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-6.4 to sage-6.5
  • Status changed from needs_review to needs_work
  • Work issues set to Cython issues

There are various Cython issues:

  1. (*) The code cannot be interrupted, see http://www.sagemath.org/doc/developer/coding_in_cython.html#interrupt-and-signal-handling
  2. Sometimes there is cdef int i when there is no i.
  3. When you use for i in xrange(n), you should declare the type of i.
  4. You can replace xrange() by range() in such code.
  5. More generally, try to declare the types of your variables.
  6. (*) When you cdef a type, make sure it is correct. In particular ncols() is not an int!
  7. Instead of matrix.ncols(), in Cython you can use matrix._ncols.
  8. About the private methods you add (like _find_pseudo_peripheral_node): you should consider making them cpdef for speed.

The (*) items must be fixed, the rest are suggestions.

comment:15 Changed 6 years ago by vdelecroix

Some more comments:

  1. What is the point of having _adj_list when we already have nonzero_positions_in_row? If you are not happy with the diagonal terms you can either remove them from the output of nonzero_positions_in_row or add an optional argument. You can also adapt _adj accordingly.
  1. The design is very ugly. If you need several methods to achieve a task then create a new class to handle them. It is a nonsense to add 6 private very specific methods (that will furthermore not appear in the documentation). Having an independent class can also be useful to avoid duplication with #13583.
  1. The call
    if self[i,j] != 0:
        ...
    
    is very slow compared to
    if self.get_unsafe(i,j):
        ...
    
    The latter avoids a creation of tuple, conversions between C variables and Python variables and a coercion (the 0 in the first version is a Python int).

comment:16 Changed 6 years ago by jdemeyer

Since your code is about 400 lines, I also suggest to add your code to a new module instead of making matrix2.pyx (already the second largest file in Sage) even bigger. Your method in matrix2.pyx could just call

from sage.matrix.rcm cimport rcm

class Matrix2(...):
    ...
    def reverse_cuthill_mckee(...)
        """
        doctests...
        """
        return rcm(...)

comment:17 Changed 6 years ago by ncohen

Hellooooo everybody,

I was not aware of this ticket, and it seems that we work on very similar topics. I implemented this recently, which is the exact (and much slower) version of the problem that the RCM tries to solve.

http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_decompositions/bandwidth.html

When you will have decided where exactly the new module will be, can you think of adding a 'seealso' from this heuristic to the graph's 'bandwidth' function, and conversely?

Thaaaaaaaaaaanks,

Nathann

comment:18 Changed 6 years ago by chapoton

  • Milestone changed from sage-6.5 to sage-6.8

comment:19 Changed 6 years ago by vdelecroix

  • Authors changed from William A. Stein, Marco Mezzarobba, Rob Beezer, Frédéric Chapoton, Ralf Stephan to William A. Stein, Marc Mezzarobba, Rob Beezer, Frédéric Chapoton, Ralf Stephan

Marco -> Marc

comment:20 Changed 6 years ago by mmezzarobba

  • Authors changed from William A. Stein, Marc Mezzarobba, Rob Beezer, Frédéric Chapoton, Ralf Stephan to William A. Stein, Rob Beezer, Frédéric Chapoton, Ralf Stephan

I don't think I ever touched that code.

comment:21 Changed 6 years ago by r.gaia.cs

I'm OK if we close this as out of date.

comment:22 Changed 5 years ago by chapoton

  • Authors changed from William A. Stein, Rob Beezer, Frédéric Chapoton, Ralf Stephan to William Stein, Rob Beezer, Frédéric Chapoton, Ralf Stephan

comment:23 Changed 2 years ago by chapoton

  • Milestone changed from sage-6.8 to sage-duplicate/invalid/wontfix
  • Status changed from needs_work to needs_review

comment:24 Changed 2 years ago by chapoton

  • Cc embray added
  • Status changed from needs_review to positive_review

obsolete, please close

comment:25 Changed 2 years ago by embray

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

If you say so.

Note: See TracTickets for help on using tickets.