Waldek,
Thank you for including the algebraic topology in 1.3.0 despite some
remaining issues.
I thought the best way to tackle those issues is to look at them, one at
a time, then try to work out a separate patch for each one.
I guess I could send you some patches and see if you accept them, but it
seems more efficient to discuss the options first and then I could write
a patch for the option which you and others on this list think is best.
So, assuming that is acceptable, here is the first issue:
Description of Issue
--------------------
On 30/08/16 16:43, Waldek Hebisch wrote:
> ATM I think that VertexSet
> is messed up. Let me present a simple example, namely
> simplicial complex with 3 vertices (say 1, 2, 3) and
> a single edge (say between 1 and 2). Now, vertex 3
> in not connected to anything but is still part of the
> complex. So we need to specify somewhere set of
> vertices of the complex. Currenly it is done via
> vertex set part in representation of complexes. But
> this clearly is highly suboptimal. In particular
> your VertexSetAbstract can only represent intervals
> so it is not possible to perform simple operations
> like renumber vertices keeping 1 in place and mapping
> 2 to 4 and 3 to 5 without introducing extra nodes.
> So it would be better to keep list of nodes in the
> complex. But then your VertexSet is not needed at
> all: you may want domain for vertices but there is
> no need to specify _subset_ of domain.
There are some wider issues about VertexSet such as how to work with
cochains and so on but I was hoping to discuss that as a separate issue.
Can we disallow renumbering vertices in a way that would leave gaps? I
think it might be best to require that there are no gaps in the vertex
numbers, that is the vertex numbers go through 1..n without missing out
any. This is all that is needed for combinatorics but for geometry I
tend to think of this as an index into the geometry information.
The Rep for FiniteSimplicialComplex is:
Rep := Record(VERTSET : VS, SIMP : List(OrientedFacet))
and the Rep for OrientedFacet is:
Rep := Record(mul : Integer, fac : List(NNI))
Are you suggesting that this is changed to this:
The Rep for FiniteSimplicialComplex would be:
Rep := List(OrientedFacet)
and the Rep for OrientedFacet would be:
Rep := Record(mul : Integer, fac : List(VS))
I think that indexing, as currently implemented, is the only practical
option. A simplicial complex might be very large, we want it to scale
up. If we are using geometric coordinates then, a simplicial complex
contains multiple references to each vertex, so typing it from the CLI
would require the user to type each coordinates multiple times also the
CLI output would probably be complex and long with multiple copies of
each coordinate. I also suspect that indexes are much more efficient to
compare and work with than coordinates which may contain floating point
values which may have rounding errors.
I think the above also applies to DeltaComplex although it would be
possible to remove geometry information from DeltaComplex especially
where it is used to hold topologies with the same point or edge
appearing in different places.
So if we start with FiniteSimplicialComplex containing VertexSet and we
want to calculate homology, converting to DeltaComplex would be the
first stage of this and loosing geometric information would not matter
because its not needed for homology. However I am not sure that this is
true for cohomology so I would like to retain VertexSet in DeltaComplex
until we know the requirements for cohomology.
I would like to decouple the link to VertexSet slightly as explained below.
Test Case
---------
This illustrates a bug when converting FiniteSimplicialComplex to
DeltaComplex.
We create a simplicial complex containing an edge and 1 unconnected
point, this is then converted to a delta complex which contains only the
line but the additional point is missing:
(1) -> ASIMP := FiniteSimplicialComplex(VertexSetAbstract)
(1) FiniteSimplicialComplex(VertexSetAbstract)
Type: Type
(2) -> v1:List(List(NNI)) := [[1::NNI,2::NNI],[3::NNI]]
(2) [[1,2],[3]]
Type: List(List(NonNegativeInteger))
(3) -> sc1 := simplicialComplex(vertexSeta(3::NNI),v1)$ASIMP
(3)
(1,2)
(3)
Type: FiniteSimplicialComplex(VertexSetAbstract)
(4) -> )expose DeltaComplex
DeltaComplex is now explicitly exposed in frame frame1
(4) -> d1 := deltaComplex(sc1)
(4)
1D:[[1,- 2]]
Type: DeltaComplex(VertexSetAbstract)
Options
-------
How to fix this bug? deltaComplex should be reading in the number of
verticies from the vertexSet and making sure any unconnected vertices
are included, it is not doing that so I could just implement it as intended.
However, I think it would be better to include the information in the
face map and get the information from there. This would decouple the
link to vertexSet slightly.
So how to include this information in the boundary maps? This is often
shown as a diagram (like in Hatcher p102)
d2 d1 d0
... C2 ---> C1 ---> C0 ---> 0
Where:
C2 = 2 dimensional chain (set of triangles/squares/polygons)
C1 = 1 dimensional chain (set of edges)
C0 = 0 dimensional chain (set of points)
0 = -1 dimensional chain (zero)
d2 = boundary map (triangles to edges)
d1 = boundary map (edges to points)
d0 = boundary map (points to 0)
In the DeltaComplex Rep I only included boundary maps down to d1 (not
d0) so I could add this last boundary map in each case. 'd0' would be a
list whose length is the number of points and whose entries are all zero.
This would give us the information we need because all we need is the
number of points. It also matches most text books better because they
usually include d0 in definitions. However a list with all zeroes is not
a very efficient coding of the information.
A more efficient implementation would be to add a single NNI to
DeltaComplex Rep to hold the number of vertices.
So what would you prefer, a more efficient Rep or a more mathematically
correct Rep? When I say a single NNI is more efficient, it is more space
efficient, but it might not be more time efficient because it means
points are handled differently from higher order facets. I would prefer
to have a list containing all zeroes and handle everything the same.
Martin B
--
You received this message because you are subscribed to the Google Groups "FriCAS -
computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to fricas-devel+unsubscr...@googlegroups.com.
To post to this group, send email to fricas-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.