(This question is about speed improvements of an existing approach, not
about finding a first toy solution.)
Let A, B be two ( (n+m) x n ) integer matrices. Say that these are
isomorphic if they coincide up to *simultaneous* row and column
permutations of the indices 0,...,n-1.
Example: [[1,0],[0,0]] and [[0,0],[0,1]] are isomorphic because
interchanging rows 0 and 1 and also columns 0 and 1 interchange the two.
NonExample: [[1,0],[0,0]] and [[0,1],[0,0]] are not isomorphic.
I would now like to obtain a canonical form CF : Mat( (n+m) x n) -> Mat(
(n+m) x n) for each isomorphism class. This is CF(M1) == CF(M2) if and only
if M1 and M2 are isomorphic. I actually do not care if the canonical form
is a matrix, a canonical hash function is enough and what I do use below.
This is almost the graph canonical form because two graphs are isomorphic
if and only if their adjacency matrices are isomorphic in the above sense.
So what I do currently is
* turn my integer matrix into a directed, edge-labelled graph
* turn this edge-labelled graph into an unlabelled graph by replacing each
non-one-label into a new vertex and keep track which new vertices represent
the same edge label
* use the canonical form algorithm in Sage to compute a canonical form (I
use the bliss version, because it allows me to not get back a graph, but
only a list of edges which is good enough to compute a canonical hash).
The code is
def matrix_canonical_hash(M, n, m):
dg,partition = _matrix_to_digraph(M, n, m)
dg_canon = dg.canonical_label(partition=partition, algorithm="bliss",
return_graph=False)
return hash(tuple(sorted(dg_canon)))
def _matrix_to_digraph(M, n, m):
dg = DiGraph(sparse=True)
dg.add_vertices(range(n+m))
edge_labels = []
new_vertex = n+m
new_partition = []
for i, j in M.nonzero_positions():
if i < n:
a, b = M[i, j], M[j, i]
else:
a, b = M[i, j], -M[i, j]
if a > 0:
if a == 1 and b == -1:
dg._backend.add_edge(i,j,None,True)
else:
try:
x = edge_labels.index((a,b))
except ValueError:
x = len(edge_labels)
edge_labels.append((a,b))
new_partition.append([])
finally:
dg.add_vertex(new_vertex)
dg._backend.add_edge(i,new_vertex,None,True)
dg._backend.add_edge(new_vertex,j,None,True)
new_partition[x].append(new_vertex)
new_vertex += 1
elif i >= n:
if a == -1 and b == 1:
dg._backend.add_edge(j,i,None,True)
else:
a = -a
b = -b
try:
x = edge_labels.index((a,b))
except ValueError:
x = len(edge_labels)
edge_labels.append((a,b))
new_partition.append([])
finally:
dg.add_vertex(new_vertex)
dg._backend.add_edge(j,new_vertex,None,True)
dg._backend.add_edge(new_vertex,i,None,True)
new_partition[x].append(new_vertex)
new_vertex += 1
partition = [list(range(n))]
if m > 0:
partition.append(list(range(n,n+m)))
if new_partition:
partition.extend(new_partition)
return dg, partition
def fast_copy(M, n, m):
Mnew = zero_matrix(n+m,n)
for (i,j),val in M.dict().iteritems():
Mnew[i,j] = val
return Mnew
My matrices have a few more properties which I use in _matrix_to_digraph
(namely that M[i,j] and M[j,i] have opposite signs and M[i,j] > 0 for i >=
n).
Since I have to do many of such test, it needs to be fast. Currently, only
1/3 of the time is spent doing the bliss algorithm. My questions thus are:
1. Does anyone know if there is a (similarly optimized) version of the
canonical form algorithms that do the canonical forms on matrices rather
than on graphs?
2. Does anyone see how I can speed the construction of the canonical form
input graph from a given matrix ?
Many thanks for your help -- any improvements will make their way into the
cluster algebra and quiver mutation functionality in main Sage,
Christian
--
You received this message because you are subscribed to the Google Groups
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.
