#20751 closed enhancement (fixed)

Check easy invariants first for simplicial complex isomorphism

Reported by: tscrim Owned by: tscrim
Priority: major Milestone: sage-7.3
Component: algebraic topology Keywords: days74
Cc: jhpalmieri, jeremy.l.martin Merged in:
Authors: Travis Scrimshaw Reviewers: John Palmieri
Report Upstream: N/A Work issues:
Branch: fbe4c3d (Commits) Commit: fbe4c3df5d54c56812bb09b01f76826b6d7a7226
Dependencies: #20720 Stopgaps:

Description (last modified by tscrim)

In order to more quickly check if two simplicial complexes are not isomorphic, we should check that their (ordered) facet dimension sequences agree.

We also check that edge labels are respected for the isomorphism, so isomorphisms of the fake degree vertex is not part of the isomorphism.

Change History (9)

comment:1 Changed 12 months ago by tscrim

  • Branch set to public/simplicial_complex/check_easy_invariants-20751
  • Commit set to 00c48e8de85d04e6001b739c6341cf5eb10341fe
  • Dependencies set to #20720
  • Status changed from new to needs_review

New commits:

7b1a299Having vertices() return a tuple instead of a Simplex.
3ace10eFixing a doctest in combinat/cluster_complex.py.
00c48e8trac 20720: referee changes

comment:2 Changed 12 months ago by git

  • Commit changed from 00c48e8de85d04e6001b739c6341cf5eb10341fe to 0af2d7ff13b3b8aea808f64810f73d1abd1cd2b7

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

0af2d7fAdded check against the facet dimension sequence.

comment:3 Changed 12 months ago by git

  • Commit changed from 0af2d7ff13b3b8aea808f64810f73d1abd1cd2b7 to 69709a2e19a2cc6cd9633e31850dc0a38d7a5c24

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

69709a2Make sure edge labels are respected

comment:4 Changed 12 months ago by git

  • Commit changed from 69709a2e19a2cc6cd9633e31850dc0a38d7a5c24 to fbe4c3df5d54c56812bb09b01f76826b6d7a7226

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

fbe4c3dSome doc tweaks reflecting then new behavior.

comment:5 Changed 12 months ago by tscrim

  • Description modified (diff)

comment:6 Changed 12 months ago by jhpalmieri

I think the initial checks can slow things down. Actually, if two complexes are not isomorphic for "obvious" reasons, it is now much faster (by a factor of 40 on my machine) to check that they are not, but if they are actually isomorphic, it is slower (by a factor of 2) to check that. For these timings, I used the complexes Z1, Z2, Z3 from the doctests, and ran

%timeit Z1.is_isomorphic(Z2)  # True
%timeit Z1.is_isomorphic(Z3)  # False

comment:7 Changed 12 months ago by tscrim

It is not the initial checks that are slowing it down, it is the additional check(s) of edge labels for the graph isomorphism. The additional checks are very small (< 1%) in comparison to the isomorphism check (both with and without edge label checks), which you can see via

%lprun -f X.is_isomorphic X.is_isomorphic(X)

However, Jeremy found it necessary to check the edge labels, at least when we want the certificate. Yet we don't have an example where there is not an isomorphism but the graphs are isomorphic without preserving edge labels. So it might be feasible that we don't need to check the edge labels in that case...

comment:8 Changed 11 months ago by jhpalmieri

  • Reviewers set to John Palmieri
  • Status changed from needs_review to positive_review

comment:9 Changed 11 months ago by vbraun

  • Branch changed from public/simplicial_complex/check_easy_invariants-20751 to fbe4c3df5d54c56812bb09b01f76826b6d7a7226
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.