Ask Your Question

# why remove_face uses alexander duality?

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 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.

( 2011-04-27 13:05:40 +0200 )edit

## 3 Answers

Sort by » oldest newest most voted

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!

more

## Comments

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

( 2011-07-25 20:25:47 +0200 )edit

(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?

more

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)

more

## Your Answer

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

Add Answer

## Stats

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

Seen: 455 times

Last updated: May 12 '11