CHomP Pawe l Pilarczyk 1 CHomP Computational Homology Project [3] OS Windows Mac Unix Linux [3] CHomP [3] 2 3 CHomP CHomP 4 5 C++ [1] 2 CHomP 1 2 K 1 = { A 1 A 2 A 3, A 1 A 2, A 2 A 3, A 1 A 3, A 3 A 4, A 1, A 2, A 3, A 4, A 5 }, K 2 = { A 1 A 2, A 2 A 3, A 1 A 3, A 3 A 4, A 1, A 2, A 3, A 4, A 5 } K = {s i i = 1,,N} K = N i=1 s i CHomP homsimpl 1(a) (b) A i i 1
(a) K 1 (b) K 2 1: ; (a) sc1.txt {1,2,3} {3,4} {5} ; (b) sc2.txt {1,2} {2,3} {1,3} {3,4} {5} homsimpl 1(a) A 1 A 2, A 2 A 3, A 1 A 3, A 1, A 2, A 3, A 4 CHomP ; filename homsimpl filename 2 (a) homsimpl sc1.txt (b) homsimpl sc2.txt 2: (a) H 0 (K 1 ) = Z 2, (b) H 0 (K 2 ) = Z 2, H 1 (K 2 ) = Z (a) (b) 2 (b) 1 A 1,A 2,A 3 2
homsimpl CHomP homsimpl filename1 filename2 homsimpl -g homsimpl filename1 -g filename2 homsimpl homsimpl K 1 K 2 K 1 H (K 1,K 2 ) homsimpl K 1 filename1 K 2 filename2 homsimpl filename1 filename2 3 Computational Homology Project X R n Q = I 1 I 2 I n I i = [l i,l i + 1] [l i,l i ], l i Z m X = Q k, Q k : k=1 n 2 3
; (I) n [l 1,l 1 + 1] [l n,l n + 1] (l 1,,l n ) 3 fullcubes.txt fullcubes.txt (1,2) (2,1) (2,3) (3,2) (5,2) 3: (1,2) (2,1) 3 (II) k [l 1,l 1 + 1] [l k 1,l k 1 + 1] [l k,l k ] [l k+1,l k+1 + 1] [l n,l n + 1] [l 1,l 1 +1] x x [l k 1,l k 1 +1] x [l k,l k ] x [l k+1,l k+1 +1] x x [l n,l n +1] [(l 1,,l k 1,l k,l k+1,,l n ) (l 1 +1,,l k 1 +1,l k,l k+1 +1,,l n +1)] 2 x 2 4 reducubes.txt CHomP chomp 3 4 filename 4
; reducubes.txt [1,2] x [2,3] [(1,2) (2,3)] [2] x [3,4] [(2,3) (2,4)] [2,3] x [2] [(2,2) (3,2)] [2,3] x [4] [(2,4) (3,4)] [3] x [2,3] [(3,2) (3,3)] [3] x [3,4] [(3,3) (3,4)] [5] x [2] [(5,2) (5,2)] 4: chomp filename 2, 1, 0 MM CR PP --engine chomp filename --engine MM CR CHomP homcubes homcubes filename homsimpl homcubes filename1 -g filename2 filename2 homsimpl homcubes A.txt B.txt H (A B,B) CHomP bitmap 2 (I) bmp2pset bitmap picture.bmp bmp2pset picture.bmp picture.txt 5
picture.bmp picture.txt homcubes bitmap (0 255) bmp2pset -t -t 4 (X,A) (Y,B), (A X,B Y ) f : (X,A) (Y,B), f(a) B CHomP [1][2] X,Y,A,B X, Y, A, B X Y F : X Y X Q i Y f : X Y Q X f(q) F(Q) F f f f : H (X,A) H (Y,B) F : X Y F(Q) F(A) B F [1][2] 1 Q i R Q i R X F(R) F : X Y F(Q) CHomP 2 1 X Q {Q 1,...,Q n } Y (1,2) -> {(4,1) (4,2) (5,1) (5,2) (6,1) (6,2)} 5 F ( [1, 2] [2, 3] ) = { [4,5] [1, 2], [4,5] [2, 3], [5, 6] [1, 2], [5, 6] [2, 3], [6, 7] [1,2], [6, 7] [2, 3] } 2 Q F(Q) X 5 6
5: Q f F [(1,2)(2,3)] [(4,1)(7,3)] 1 2 X F homcubes f F : (X, A) (Y, B) F, X, A, Y, B 5 A = B = 3 H (X,A),H (Y,B) homcubes F.map X.cub A.cub Y.cub B.cub -g XA.gen -g YB.gen XA.gen,YB.gen H (X,A),H (Y,B) CHomP chkmvmap homcubes F.map X.cub,A.cub,Y.cub,B.cub chkmvmap F.map X.cub A.cub Y.cub B.cub 5 C++ CHomP C++ chomp homcubes CHomP 7
5.1 chomp C++ bitmap chomp engine 6: bitmap bitmap n bitmap 1 1 0 R d [0,n 1 ] [0,n d ] n 1,,n d n 1 32 32 64 64 1 8 6 bitmap (0,,0) n 1 1 1 0 n 1 2 1 d void ComputeBettiNumbers (const void *buffer, int *sizes, int dim, int *result, const char *engine = 0, const int *wrapping = 0, bool quiet = false); CubicalSet ComputeBettiNumbers bitmap CHomP CubicalSet CubicalSet [n 1,n+ 1 ] [n d,n+ d ] d n 1,...,n d n+ 1,...,n+ d Add Delete (k 1,...,k d ) 8
n i k i < n + i void ComputeBettiNumbers (const CubicalSet &s, int *result, const char *engine = 0, bool quiet = false); 1 1 CubicalSet 01 #include <iostream> 02 #include "capd/homengin/cubiset.h" 03 04 int main () 05 { 06 int left coords [] = {-6, -5, 0}; 07 int right coords [] = {6, 1, 4}; 08 CubicalSet Q (left coords, right coords, 3); 09 10 int cube1 [] = {1, -5, 0}; 11 Q. Add (cube1); 12 int cube2 [] = {5, -2, 2}; 13 Q. Add (cube2); 14 15 int betti [4]; 16 ComputeBettiNumbers (Q, betti, "MM CR", true); 17 for (int i = 0; i < 4; ++ i) 18 std::cout << (i? " " : "") << betti [i]; 19 std::cout << \n ; 20 return 0; 21 } 5.2 chomp::homology coordinate 16 short int [ 32768, 32767] Cube SetOfCubes Cube R d Cube coord dim SetOfCubes add remove SetOfCubes 9
check SetOfCubes X (X,A) Homology 2 2 Cube SetOfCubes 01 #include <iostream> 02 #include "chomp/homology/homology.h" 03 04 using namespace chomp::homology; 05 06 int main () 07 { 08 coordinate coords1 [] = {1, -5, 0}; 09 Cube Q (coords1, 3); 10 SetOfCubes S; 11 S. add (Q); 12 coordinate coords2 [] = {5, -2, 2}; 13 S. add (Cube (coords2, 3)); 14 15 Chain hom = 0; 16 int maxlevel = Homology (S, "S", hom); 17 for (int q = 0; q <= maxlevel; ++ q) 18 std::cout << (q? " " : "") << BettiNumber (hom [q]); 19 std::cout << \n ; 20 delete [] hom; 21 return 0; 22 } CubicalCell CubicalComplex R d CubicalCell Cube CubicalComplex add C dim k [] C[k] CubicalComplex Homology CubicalMap CubicalMap Q Cube F CubicalMap SetOfCubes F[Q] add = CubicalMap Homology 10
[1] T. Kaczynski, K. Mischaikow, and M. Mrozek, Computational Homology, Applied Mathematical Science Vol. 157, Springer, 2004. [2] K. Mischaikow, M. Mrozek, P. Pilarczyk, Graph approach to the computation of the homology of continuous maps, Foundations of Computational Mathematics 5 (2005) 199 229. [3] http://chomp.rutgers.edu/ 11