Quelle aboutCubical.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/hap/www/SideLinks/About/aboutCubical.html

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
 <meta http-equiv="content-type"
content="text/html; charset=ISO-8859-1">
 <title>AboutHap</title>
</head>
<body
style="color: rgb(0, 0, 153); background-color: rgb(204, 255, 255);"
link="#000066" vlink="#000066" alink="#000066">
 
<table
style="text-align: left; margin-left: auto; margin-right: auto; color: rgb(0, 0, 102); width: 1009px; height: 2603px;"
border="0" cellpadding="20" cellspacing="10">
 <tbody>
 <tr align="center">
 <th style="vertical-align: top;">
 <table style="width: 100%; text-align: left;" cellpadding="2"
cellspacing="2">
 <tbody>
 <tr>
 <td style="vertical-align: top;"><a
href="AboutTorsionSubcomplexes.html">Previous</a> 
 </td>
 <td
style="text-align: center; vertical-align: top; color: rgb(0, 0, 102);"><big>About HAP: Simplicial, Cubical,
Permutahedral and Regular CW-Complexes 
 </big></td>
 <td style="text-align: right; vertical-align: top;"><a
href="aboutRandomComplexes.html">next</a> 
 </td>
 </tr>
 </tbody>
 </table>
 <big></big> 
 </th>
 </tr>
 <tr align="center">
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);"><big
style="font-weight: bold;">1. Simplicial Complexes 
 </big></td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255); text-align: left;">A
finite
simplicial
complex
can
be
created in HAP by specifying its
maximal simplices. For instance, the following commmands construct the
simplicial projective plane 
 
 <div style="text-align: center;"><img
style="width: 316px; height: 323px;" alt="" src="projectiveplane.jpg"> 
 </div>
 
and then calculate its integral homologies from the associated cellular
chain complex. 
 </td>
 </tr>
 <tr>
 <td
style="background-color: rgb(255, 255, 204); vertical-align: top;">gap>
L:=[[1,2,6],[2,6,9],[2,3,9],[3,8,9],[3,4,8],[4,5,8], 
> [5,6,9],[5,9,10],[8,9,10],[7,8,10],[5,7,8],[5,6,7], 
> [4,5,10],[3,4,10],[3,7,10],[2,3,7],[2,6,7],[1,2,6]];; 
 
gap> P:=MaximalSimplicesToSimplicialComplex(L); 
Simplicial complex of dimension 2. 
 
gap> C:=ChainComplex(P); 
Chain complex of length 2 in characteristic 0 . 
 
gap> Homology(C,0); 
[ 0 ] 
gap> Homology(C,1); 
[ 2 ] 
gap> Homology(C,2); 
[ ] 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">The
following commands compute the low-dimensional integral homologies of a
10-dimensional simplicial sphere. 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
n:=10;; 
gap>
S:=MaximalSimplicesToSimplicialComplex(Combinations([0..n+1],n+1)); 
Simplicial complex of dimension 10. 
 
gap> C:=ChainComplex(S); 
Chain complex of length 10 in characteristic 0 . 
 
gap> List([0..n],m->Homology(C,m)); 
[ [ 0 ], [ ], [ ], [ ], [ ], [ ], [
], [ ], [ ], [ ], [ 0 ], [ ] ] 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">The
simplicial complex arising as the order complex of the poset of
non-trivial elementary abelian p-subgroups of a finite group G has been
studied by D. Quillen and others. The following commands contruct this
simplicial complex for the Sylow 2-subgroup of the Mathieu group M12
(with p=2), and then verify that in this case the simplicial complex is
contractible. 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
Q:=QuillenComplex(SylowSubgroup(MathieuGroup(12),2),2); 
Simplicial complex of dimension 2. 
 
gap> C:=ChainComplex(Q); 
Chain complex of length 2 in characteristic 0 . 
 
gap> Homology(C,0); 
[ 0 ] 
gap> Homology(C,1); 
[ ] 
gap> Homology(C,2); 
[ ] </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">
 <div style="text-align: center;"><big style="font-weight: bold;">2.
Pure
Cubical
Complexes 
 </big></div>
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">In
HAP we us the term pure cubical
complex to mean a subspace of
d-dimensional Euclidian space arising as a union of finitely many
d-dimensional unit cubes whose vertices have integral coordinates. A
pure cubical complex can be created by specifying a d-dimensional array
of 0s and 1s. For instance, the following commands construct a
3-dimensional cubical 2-sphere and determine its homology in low
dimensions. 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
a:=[[1,1,1],[1,1,1],[1,1,1]];; 
gap> b:=[[1,1,1],[1,0,1],[1,1,1]];; 
gap> c:=[[1,1,1],[1,1,1],[1,1,1]];; 
gap> array:=[a,b,c];; 
gap> S2:=PureCubicalComplex(array); 
Pure cubical complex of dimension 3. 
 
gap> C:=ChainComplex(S2); 
Chain complex of length 3 in characteristic 0 . 
 
gap> Homology(C,0); 
[ 0 ] 
gap> Homology(C,1); 
[ ] 
gap> Homology(C,2); 
[ 0 ] 
gap> Homology(C,3); 
[ ] 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">There
is
a
functor 
 
 <div style="text-align: center;">N:
(Pure
Cubical
Complexes)
------>
(Simplicial
Complexes) 
 </div>
 
that sends a pure cubical complex X to a simplicial complex NX of the same homotopy type. If X
is d-dimensional then we refer to the d-dimensional cells in X as facets. The vertices of NX are the facets of X, and the
dimensional simplices of NX
are the subsets of this vertex set having a non-trivial common
intersection. We refer to NX
as
the

 Cech complex of X. The
following commands compute the Cech complex of the
above cubical 2-sphere and (again) determine the low dimensional
homology of the
2-sphere. 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
NS2:=CechComplexOfPureCubicalComplex(S2); 
Simplicial complex of dimension 3. 
 
gap> C:=ChainComplex(NS2); 
Chain complex of length 3 in characteristic 0 . 
 
gap> Homology(C,0); 
[ 0 ] 
gap> Homology(C,1); 
[ ] 
gap> Homology(C,2); 
[ 0 ] 
gap> Homology(C,3); 
[ ] 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">The
above cubical 2-sphere S2 has twenty-six 3-cells. The following
commands
compute a homotopy retract with just six 3-cells. 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
R:=ContractedComplex(S2); 
Pure cubical complex of dimension 3. 
 
gap> C:=ChainComplex(S2);; 
gap> D:=ChainComplex(R);; 
gap> C!.dimension(3); 
26 
gap> D!.dimension(3); 
6 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">The
two-sphere S2 and its homotopy retract R can be visualized using the
following commands. These commands invoke the <a
href="http://asymptote.sourceforge.net/">Asymptote vector graphics
package</a>. 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
ViewPureCubicalComplex(S2); 
gap> ViewPureCubicalComplex(R); 
 
 <div style="text-align: center;"><img
style="width: 416px; height: 450px;" alt="" src="asyex1.png">

 <img style="width: 394px; height: 450px;" alt="" src="asyex2.png"> 
 </div>
 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">The
following command shows that the Cech complex of this smaller
3-dimensional 2-sphere is actually a 2-dimensional simplicial complex. 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
S:=CechComplexOfPureCubicalComplex(R); 
Simplicial complex of dimension 2. 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">A
digital photograph can be represented as a 2-dimensional pure cubical
complex. This is done by choosing an integer threshold and including a
2-cell in the pure cubical complex for each pixel where the sum of the
three RGB values iis less than the threshold. 
 
The following commands use a threshold of 400 to represent the image 
 
 <div style="text-align: center;"><img
style="width: 247px; height: 287px;" alt="" src="bw_image.bmp"> 
 <div style="text-align: left;"> 
as a pure cubical complex. The complex has 40949 2-dimensional cells. 
 </div>
 </div>
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
image:=ReadImageAsPureCubicalComplex("bw_image.bmp",400); 
Pure cubical complex of dimension 2. 
 
gap> C:=ChainComplex(image); 
Chain complex of length 2 in characteristic 0 . 
 
gap> C!.dimension(0); 
45664 
gap> C!.dimension(1); 
86630 
gap> C!.dimension(2); 
40949 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">The
number of cells in the above cubical complex makes it difficult to
compute the homology of the associated cellular chain complex. One way
around the difficulty is to: 
 <ul>
 </ul>
 <ol>
 <li>Find a homotopy retract R of the pure cubical complex.</li>
 <li>Find a large contractible subcomplex S in R.</li>
 <li>Construct the quotient C(R)/C(S) of the cellular
chain complexes.</li>
 <li>Use the fact that Hn(R) = Hn(
C(R)/C(S) ) for n>0 and that H0(R) is isomorphic to the
direct sum H0(C(R)/C(S))+H0(S).</li>
 </ol>
 <ul>
 </ul>
The following commands apply Steps 1-4 in order to calculate that the
above image has 3 path components and 20 1-cycles. 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
image:=ReadImageAsPureCubicalComplex("bw_image.bmp",400); 
Pure cubical complex of dimension 2. 
 
gap> R:=ContractedComplex(image); 
Pure cubical complex of dimension 2. 
 
gap> S:=ContractibleSubcomplexOfPureCubicalComplex(R); 
Pure cubical complex of dimension 2. 
 
gap> C:=ChainComplexOfPair(R,S); 
Chain complex of length 2 in characteristic 0 . 
 
gap> Homology(C,0); 
[ 0, 0 ] 
 
gap> Homology(C,1); 
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] 
 </td>
 </tr>
 <tr align="center">
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);"><big>3. Cubical Complexes</big> 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">We
us the term cubcial complex
to mean any cellular subcomplex of a pure cubcial complex. This
slightly more general notion allows us to work with smaller homotopy
retracts when making homology computations. 
 
The following commands produce a pure cubical homotopy retract R, and
then a cubcial retract K, of the above black and white image.
Considered as CW-complexes, R involves a total of 16975 cells while K
involves a total
of 7005 cells 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
image:=ReadImageAsPureCubicalComplex("bw_image.bmp",400); 
Pure cubical complex of dimension 2. 
 
gap> R:=ContractedComplex(image); 
Pure cubical complex of dimension 2. 
 
gap> K:=PureCubicalComplexToCubicalComplex(R); 
Cubical complex of dimension 2. 
 
gap> Size(K); 
16975 
 
gap> ContractCubicalComplex(K); 
 
gap> Size(K); 
7005 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">By
working with arbitrary (non-regular) CW-complexes we can further reduce
the number of cells in the cubical complex K. The following
commands use an algorithm, based on the notion of a discrete vector
field, to find a CW-complex L of the homotopy type of K but
involving a total of just 25 cells. (Since H0(K) = Z3
and H1(K) = Z20 this is close to the minimum
possible number of cells in any CW-complex having the homotopy type of
K.) 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
L:=DVFReducedCubicalComplex(K); 
Non-regular cubical complex of dimension 2 with discrete vector field. 
 
gap> Size(L); 
25 
 
gap> C:=ChainComplex(L); 
Chain complex of length 2 in characteristic 0 . 
 
gap> Homology(C,0); 
[ 0, 0, 0 ] 
 
gap> Homology(C,1); 
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] 
 </td>
 </tr>
 <tr align="center">
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);"><big>4. Permutahedral Complexes</big> 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">Euclidean
n-space
can
be
tessellated
by
regular n-dimensional permutahedra. By a pure permutahedral complex we mean
a union of finitely many of the permutahedra in this tessellation.
Using the HAPPermutahedral package written by Fintan Hegarty we can
represent the above black an white image as a pure permutahedral
complex P. Although we are not guaranteed that the homotopy type of the
pure permutahedral complex P is identical to that of the above pure
cubcial complex representing the image, though we would hope that the
homotopy types of the two complexes are not too dissimilar. 
 
The following commands construct a homotopy retract of P, and then
construct the Cech complex NP
(which is defined as in the case of pure cubical complexes). An
advantage of pure permutahedral complexes over pure cubical complexes
is that a pure permutahedral complex of dimension n has Cech complex of
the same dimension. 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
P:=PurePermutahedralComplex(image!.binaryArray); 
Pure Permutahedral Complex of dimension 2. 
 
gap> ContractPurePermutahedralComplex(P); 
 
gap> NP:=PureComplexToSimplicialComplex(P,5); 
Simplicial complex of dimension 2. 
 
gap> Homology(D,0); 
[ 0, 0, 0 ] 
 
gap> Homology(NP,1); 
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">By
contrast, the Cech complex of the pure cubical representation of the
black and white image is a simplicial complex of dimension
3. 
 </td>
 </tr>
 <tr align="center">
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);"><big>5. Regular CW-complexes</big> 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">Simplicial,
cubical
and
permutahedral
complexes
are
all examples of regular
CW-spaces. Since some homotopical algorithms are best implemented in
the general setting of regular CW-spaces the HAP package proides a data
type for this general setting. 
 
The following example creates a 4-dimensional pure cubical complex T
representing a standard torus. It then computes the Cech
complex NT which is a 15-dimensional simplicial complex. It then
converts the data type of NT into that of a regular CW-somplex. This
CW-complex Y involves a total of 1172776 cells. 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
Circle:=PureCubicalComplex([[1,1,1,1,1],[1,1,0,1,1],[1,1,1,1,1]]); 
Pure cubical complex of dimension 2. 
 
gap> T:=DirectProductOfPureCubicalComplexes(Circle,Circle); 
Pure cubical complex of dimension 4. 
 
gap> NT:=CechComplexOfPureCubicalComplex(T); 
Simplicial complex of dimension 15. 
 
gap> Y:=SimplicialComplexToRegularCWSpace(NT); 
Regular CW-space of dimension 15 
 
gap> Size(Y); 
1172776 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">The
15-dimensional CW-space Y has 1172776 cells. However, we know from its
construction that it has the homotopy type of a torus. The following
commands compute a set of "critical cells" for Y which can be used to
build a smaller non-regular CW-complex of the same homotopy type. The
computation shows that there is a CW-complex of the same homotopy type
involving just one 0-cell, two 1-cells and one 2-cell. 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
CriticalCellsOfRegularCWSpace(Y); 
[ [ 2, 5872 ], [ 1, 1116 ], [ 1, 2017 ], [ 0, 196 ] ] 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">The
following command computes the chain complex of the space whose cells
correspond to the critical cells of Y. 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
C:=ChainComplex(Y);; 
 
gap> List([0..15],C!.dimension); 
[ 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] 
 </td>
 </tr>
 <tr align="center">
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);"><big>6. Homotopy Equivalent Pure Cubical
Complexes</big> 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">It
often happens that, for a given pure cubical complex X, any pure
cubical homotopy retract R of X is necessarily quite large. Smaller
homotopy equivalent pure cubical complexes ZR can often be obtained by
allowing zig-zag sequences of homotopy retracts. 
 
 <div style="text-align: center;">X ----> Y1 <---- Y2
----> Y3 <---- Y4 ----> ... <--- ZR 
 </div>
 <div style="text-align: left;"> 
To illustrate the benefit of this approach we consisder the suspension
S of the above black and white image. The pure complex S has 182727
facets. Our algorithm for finding a homotopy retract of S produces a
homotopy retract R with 29809 facets. Our algorithm for finding a
zig-zag homotopy equivalent complex produces a homotopy equivalent pure
cubcial complex ZR with just 304 facets. 
 
Finally, we produce the cellular chain complex of a non-regular
CW-complex V of the homotopy type of S. The CW-complex V has one
0-cell, two 1-cells and twenty 2-cells. This is the minimum possible
number of cells for any CW-complex of the homotopy type of S. 
 </div>
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
image:=ReadImageAsPureCubicalComplex("bw_image.bmp",400); 
 
gap> X:=SuspensionOfPureCubicalComplex(image); 
Pure cubical complex of dimension 3. 
 
gap> Size(X); 
182727 
 
gap> R:=ContractedComplex(X); 
Pure cubical complex of dimension 3. 
 
gap> Size(R); 
29809 
 
gap> ZR:=ZigZagContractedPureCubicalComplex(S); 
Pure cubical complex of dimension 3. 
 
gap> Size(ZR); 
304 
 
gap>
V:=DVFReducedCubicalComplex(PureCubicalComplexToCubicalComplex(ZR)); 
Non-regular cubical complex of dimension 3 with discrete vector field. 
 
gap> C:=ChainComplex(V); 
Chain complex of length 3 in characteristic 0 . 
 
gap> C!.dimension(0); 
1 
gap> C!.dimension(1); 
2 
gap> C!.dimension(2); 
20 
gap> C!.dimension(3); 
0 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top;">
 <table
style="margin-left: auto; margin-right: auto; width: 100%; text-align: left;"
border="0" cellpadding="2" cellspacing="2">
 <tbody>
 <tr>
 <td style="vertical-align: top;"><a
style="color: rgb(0, 0, 102);" href="AboutTorsionSubcomplexes.html">Previous
Page</a> 
 </td>
 <td style="text-align: center; vertical-align: top;"><a
href="aboutContents.html">Contents</a> 
 </td>
 <td style="text-align: right; vertical-align: top;"><a
href="aboutRandomComplexes.html">Next
page 
 </a> </td>
 </tr>
 </tbody>
 </table>
 <a href="aboutTopology.html"> 
 </a> </td>
 </tr>
 </tbody>
</table>
 
 
</body>
</html>

Messung V0.5

¤ Dauer der Verarbeitung: 0.13 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.