(This question is about speed improvements of an existing approach, not about finding a first toy solution.)

## Advertising

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 sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at https://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.