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:  sageduplicate/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: 
Description (last modified by )
It will be great to have the RCM (Reverse CuthillMcKee) 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)
Change History (26)
comment:1 Changed 9 years ago by
 Status changed from new to needs_review
comment:2 Changed 9 years ago by
 Description modified (diff)
Changed 9 years ago by
comment:3 Changed 9 years ago by
 Dependencies #13565, #13581 deleted
comment:4 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:5 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:6 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:7 Changed 7 years ago by
 Branch set to u/rws/add_rcm_to_matrix_matrix2_pyx
comment:8 Changed 7 years ago by
 Commit set to 9698b503b097ce7ccecc8770611a53c78611236e
 Description modified (diff)
comment:9 Changed 7 years ago by
 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
 Milestone changed from sage6.3 to sage6.4
comment:11 Changed 6 years ago by
 Branch changed from u/rws/add_rcm_to_matrix_matrix2_pyx to public/ticket/13584
 Commit changed from 9698b503b097ce7ccecc8770611a53c78611236e to ba6c01d594276fb29ea96a4c5718933251c2c5ea
comment:12 Changed 6 years ago by
 Commit changed from ba6c01d594276fb29ea96a4c5718933251c2c5ea to c3fb93fe197a6d47643fc66f7beb8cd06888c551
Branch pushed to git repo; I updated commit sha1. New commits:
c3fb93f  13584: add missing doctest

comment:13 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:14 Changed 6 years ago by
 Milestone changed from sage6.4 to sage6.5
 Status changed from needs_review to needs_work
 Work issues set to Cython issues
There are various Cython issues:
 (*) The code cannot be interrupted, see http://www.sagemath.org/doc/developer/coding_in_cython.html#interruptandsignalhandling
 Sometimes there is
cdef int i
when there is noi
.  When you use
for i in xrange(n)
, you should declare the type ofi
.  You can replace
xrange()
byrange()
in such code.  More generally, try to declare the types of your variables.
 (*) When you
cdef
a type, make sure it is correct. In particularncols()
is not anint
!  Instead of
matrix.ncols()
, in Cython you can usematrix._ncols
.  About the private methods you add (like
_find_pseudo_peripheral_node
): you should consider making themcpdef
for speed.
The (*) items must be fixed, the rest are suggestions.
comment:15 Changed 6 years ago by
Some more comments:
 What is the point of having
_adj_list
when we already havenonzero_positions_in_row
? If you are not happy with the diagonal terms you can either remove them from the output ofnonzero_positions_in_row
or add an optional argument. You can also adapt_adj
accordingly.
 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.
 The call
if self[i,j] != 0: ...
is very slow compared toif self.get_unsafe(i,j): ...
The latter avoids a creation of tuple, conversions between C variables and Python variables and a coercion (the0
in the first version is a Python int).
comment:16 Changed 6 years ago by
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
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
 Milestone changed from sage6.5 to sage6.8
comment:21 Changed 6 years ago by
I'm OK if we close this as out of date.
comment:22 Changed 5 years ago by
comment:23 Changed 2 years ago by
 Milestone changed from sage6.8 to sageduplicate/invalid/wontfix
 Status changed from needs_work to needs_review
comment:24 Changed 2 years ago by
 Cc embray added
 Status changed from needs_review to positive_review
obsolete, please close
comment:25 Changed 2 years ago by
 Resolution set to wontfix
 Status changed from positive_review to closed
If you say so.
New commits:
13584: Add some matrix to doctest of rcm().