Ask Your Question
0

why remove_face uses alexander duality?

asked 2011-04-27 12:56:04 +0100

EmersonL gravatar image

updated 2011-05-04 06:05:43 +0100

The method for simplicial complexes remove_face is very slow for not to say that never ends. The documentation describes the used algorithm, but it seems pretty unefficient. I think it is easier simply to remove the facets containing the face to delete F, and for each facet add the faces not containing F. That is the join of the boundary of F and the complement of F (the link). Why to use such elaborate algorithm?

edit retag flag offensive close merge delete

Comments

Please write a new version; if it works and is faster, it can be merged into Sage. The Alexander duality method could also use work, I think.

John Palmieri gravatar imageJohn Palmieri ( 2011-04-27 13:05:40 +0100 )edit

3 Answers

Sort by » oldest newest most voted
0

answered 2011-05-03 13:56:34 +0100

EmersonL gravatar image

updated 2011-05-03 17:07:12 +0100

benjaminfjones gravatar image

This is the code I got. I'm still novice with python stuff...

def remove_face(SC,FACE):
    """Remove the Simplex FACE from the SimplicialComplex SC, by taking
    the facets of SC not containing FACE, union with
    link(FACE)*boundary(face)."""
    ffboundary=SimplicialComplex(FACE,FACE.faces()) # boundary
    link=SC.link(FACE)#link
    a=ffboundary.join(link,rename_vertices=False)#join
    b=Set([elem for elem in SC.facets() if FACE.is_face(elem)==False])
    c=a.facets().union(b)
    SC2=SimplicialComplex(SC.vertices(),c)
    return SC2

There is a minor problem now in case that FACE is not a face of SC. Maybe an error can be added, but I think the algorithm is right, and the problem is in the way the link is computed.

The problem is that the link of a simplex not being a face in the complex is not the simplicial complex {()} (the irrelevant complex), but simply {} (the void complex). The link definition doesn't include the empty set in this case, so the answer is tecnically wrong.

If the link is void, the join would be void, and no faces are added or removed... Besides, if the link makes this difference, it can be used as a test for a simplex being a face (since {} is supposed to be false).

I tested the examples to compare results with sage documentation (here FACE must be a Simplex), but with real examples (a bit bigger), I didn't manage to wait for sage, while my algorithm was about a second... Regards!

edit flag offensive delete link more

Comments

See http://trac.sagemath.org/sage_trac/ticket/11625 for a patch implementing this.

John Palmieri gravatar imageJohn Palmieri ( 2011-07-25 20:25:47 +0100 )edit
0

answered 2011-05-04 16:12:00 +0100

(This is really a comment for EmersonL's answer, but it's too long to fit, plus I wanted to format it nicely.)

I'm not getting any speed-up with your version. I added it to the file simplicial_complex.py, calling it "remove_face2", and I added one line:

FACE = Simplex(FACE)

at the beginning so that you can enter a list of vertices, not necessarily an actual simplex. Then I did this:

sage: S = range(1,8)
sage: timeit('Z = SimplicialComplex(S, [S]); Z.remove_face([1,2,3])')
625 loops, best of 3: 675 µs per loop
sage: timeit('Z = SimplicialComplex(S, [S]); Z.remove_face2([1,2,3])')
625 loops, best of 3: 940 µs per loop

I tried a few other examples, and the old version was faster for most of them, comparable for all of them. Can you give some examples where your code is faster?

edit flag offensive delete link more
0

answered 2011-05-12 06:54:34 +0100

EmersonL gravatar image

updated 2011-05-12 07:40:49 +0100

try this:

T=SimplicialComplex(10,[[0,1,2,3,4,5,6],[1,2,3,4,5,6,7],[0,1,2,4,5,6,7],[0,1,2,3,5,6,7],[0,1,2,3,4,5,7],[0,1,2,3,4,7,8],[0,1,2,3,4,6,8],[0,1,2,4,6,7,8],[0,1,2,3,6,7,8],[0,1,3,4,5,7,8],[0,1,3,4,5,6,8],[0,1,4,5,6,7,8],[1,3,4,5,7,8,9],[1,3,4,5,6,8,9],[0,3,4,5,6,8,9],[0,3,4,5,6,9,10],[0,2,3,4,5,6,10],[0,4,5,6,8,9,10],[0,3,4,5,8,9,10],[0,3,4,6,8,9,10],[0,2,4,5,6,7,10],[0,2,3,4,5,7,10],[2,3,4,5,6,7,10],[0,2,3,4,6,8,10],[0,4,5,6,7,8,10],[0,3,4,5,7,8,10],[0,2,4,6,7,8,10],[0,2,3,4,7,8,10],[1,3,4,5,6,7,10]])

FACE=Simplex([1,2,5])

remove_face(T,FACE)
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2011-04-27 12:56:04 +0100

Seen: 503 times

Last updated: May 12 '11