ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 25 Jul 2011 20:25:47 +0200why remove_face uses alexander duality?https://ask.sagemath.org/question/8091/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?Wed, 27 Apr 2011 12:56:04 +0200https://ask.sagemath.org/question/8091/why-remove_face-uses-alexander-duality/Comment by John Palmieri for <p>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?</p>
https://ask.sagemath.org/question/8091/why-remove_face-uses-alexander-duality/?comment=21792#post-id-21792Please 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.Wed, 27 Apr 2011 13:05:40 +0200https://ask.sagemath.org/question/8091/why-remove_face-uses-alexander-duality/?comment=21792#post-id-21792Answer by EmersonL for <p>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?</p>
https://ask.sagemath.org/question/8091/why-remove_face-uses-alexander-duality/?answer=12331#post-id-12331This 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!
Tue, 03 May 2011 13:56:34 +0200https://ask.sagemath.org/question/8091/why-remove_face-uses-alexander-duality/?answer=12331#post-id-12331Comment by John Palmieri for <p>This is the code I got. I'm still novice with python stuff...</p>
<pre><code>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
</code></pre>
<p>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. </p>
<p>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.</p>
<p>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).</p>
<p>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!</p>
https://ask.sagemath.org/question/8091/why-remove_face-uses-alexander-duality/?comment=21448#post-id-21448See http://trac.sagemath.org/sage_trac/ticket/11625 for a patch implementing this.Mon, 25 Jul 2011 20:25:47 +0200https://ask.sagemath.org/question/8091/why-remove_face-uses-alexander-duality/?comment=21448#post-id-21448Answer by John Palmieri for <p>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?</p>
https://ask.sagemath.org/question/8091/why-remove_face-uses-alexander-duality/?answer=12333#post-id-12333(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?
Wed, 04 May 2011 16:12:00 +0200https://ask.sagemath.org/question/8091/why-remove_face-uses-alexander-duality/?answer=12333#post-id-12333Answer by EmersonL for <p>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?</p>
https://ask.sagemath.org/question/8091/why-remove_face-uses-alexander-duality/?answer=12344#post-id-12344try 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)
Thu, 12 May 2011 06:54:34 +0200https://ask.sagemath.org/question/8091/why-remove_face-uses-alexander-duality/?answer=12344#post-id-12344