COMPUTING HOMOLOGY:b10...00 blk0 0CS 468 – Lecture 711/6/2Afra Zomorodian – CS 468 Lecture 7 - Page 1TIDBITS• Lecture 8 is on Tuesday, November 12• Email me about projects!• Projects will be November 27th and December 4th.• November 20th?• Triangulation of exampleAfra Zomorodian – CS 468 Lecture 7 - Page 2(LAST TIME)EULER-POINCAR´E• chain complex C∗:. . . → Ck+1∂k+1−−−→ Ck∂k−→ Ck−1→ . . .• Homology functors H∗• H∗(C∗) is a chain complex:. . . → Hk+1∂k+1−−−→ Hk∂k−→ Hk−1→ . . .• What is its Euler characteristic?• (Theorem) χ(K) = χ(C∗) = χ(H∗(C∗)).•Pi(−1)isi=Pi(−1)irank(Hi) =Pi(−1)iβiAfra Zomorodian – CS 468 Lecture 7 - Page 3OVERVIEW• Dualities• Data structures– Quad-Edge– Edge-Facet• Computing Homology– Reduction Algorithm– Incremental AlgorithmAfra Zomorodian – CS 468 Lecture 7 - Page 4DUALITYa cdb(a) Tetrahedrona b c dbcabac ad cd bdbcdacdabdabcφφ(b) PosetAfra Zomorodian – CS 468 Lecture 7 - Page 5PLATONIC SOLIDSsolid vertices edges facestetrahedron 4 6 4cube 8 12 6octahedron 6 12 8dodecahedron 20 30 12icosahedron 12 30 20Afra Zomorodian – CS 468 Lecture 7 - Page 6ORIENTATIONThe Optiverse [Sullivan ’98]Afra Zomorodian – CS 468 Lecture 7 - Page 7BACKGROUND-FOREGROUNDAfra Zomorodian – CS 468 Lecture 7 - Page 8COMPLEMENTARITYAfra Zomorodian – CS 468 Lecture 7 - Page 9TIME REVERSALAfra Zomorodian – CS 468 Lecture 7 - Page 10DUALITY• Orientation: inside vs. outside• Structure: primal vs. dual (poset vs. upside-down poset)• Complementarity: background vs. foreground• Time reversal: forward vs. backwardAfra Zomorodian – CS 468 Lecture 7 - Page 11DIRECTED EDGERightLeft• An edge e has two vertices• A directed edge goes from Org (e) to Dest (e)• An edge separates two cells• Sym(e) goes in the opposite directionAfra Zomorodian – CS 468 Lecture 7 - Page 12QUAD-EDGERightLeft• Rot(e) gives you the dual edge (clockwise) and Tor(e) (counter)• Edge e stores its number and the next clockwise edge with the sameorigin: Onext (e)• A Quad-Edge is Edge[4]: edge, rot, sym, tor• All operations O(1)Afra Zomorodian – CS 468 Lecture 7 - Page 13OPERATIONSRightLeft• Oprev (e) = (Rot ◦ Onext◦ Rot)(e)• Dnext (e) = (Sym ◦ Onext◦ Sym)(e)• Lnext (e) = (Tor ◦ Onext ◦ Rot)(e)Afra Zomorodian – CS 468 Lecture 7 - Page 14ORIENTED TRIANGLEScbaabc bca cabacbcbabacSymSymSymEnextEnext EnextEnextEnextEnext• Sym does one transposition (changes orientation)• Enext does two transpositions (rotate by 60 degrees clockwise)• Array of six edge-facets for each triangle• All operations O(1)Afra Zomorodian – CS 468 Lecture 7 - Page 15FNEXTbcdae• Fnext (bac) = bad• Fnext (abd) = abc• Fnext (abc) = abe• Each store its FnextAfra Zomorodian – CS 468 Lecture 7 - Page 16FACES OF A TETRAHEDRONbcda(a) f = bacbcda(b) Fnext(f) = badbcda(c) Sym ( Fnext (f )) = abdbcda(d) Sym ( Fnext (Enext (f ))) = ca dAfra Zomorodian – CS 468 Lecture 7 - Page 17HOMOLOGY• The kth homology group isHk= Zk/Bk= ker ∂k/im ∂k+1.• Compute a basis for ker ∂k• Compute a basis for im ∂k + 1CkBk−1Zk−1Ck−1δk+1δkCk+10 00ZkkBZk+1k+1BAfra Zomorodian – CS 468 Lecture 7 - Page 18MATRIX REPRESENTATION• Boundary homomorphism is linear, so it has a matrix• ∂k: Ck→ Ck−1• Use oriented simplices as bases for domain and codomain!• Mkis the standard matrix representation for ∂kAfra Zomorodian – CS 468 Lecture 7 - Page 19EXAMPLEdabcM1=ab bc cd ad aca −1 0 0 −1 −1b 1 −1 0 0 0c 0 1 −1 0 1d 0 0 1 1 0Afra Zomorodian – CS 468 Lecture 7 - Page 20ELEMENTARY OPERATIONS• The elementary row operations on Mkare1. exchange row i and row j,2. multiply row i by −1,3. replace row i by (row i) + q(row j), where q is an integer andj 6= i.• Similar elementary column operations on columns• Effect: change of basesAfra Zomorodian – CS 468 Lecture 7 - Page 21DESCRIPTION• Homology groups are finitely generated abelian.• (Theorem) Every finitely generated abelian group is isomorphic toproduct of cyclic groups of the formZm1× Zm2× . . . × Zmr× Z × Z × . . . × Z,• βk= β(Hk)• Torsion coefficientsAfra Zomorodian – CS 468 Lecture 7 - Page 22INTUITION• How do we find cycles?• How do we find boundaries?• What does a free generator correspond to?• How does a torsional element appear?Afra Zomorodian – CS 468 Lecture 7 - Page 23REDUCTION ALGORITHM• Like Gaussian elimination, we keep changing the basis to get to the(Smith) normal form:˜Mk=b10...00 blk0 0• lk= rank Mk= rank˜Mk, bi≥ 1• bi|bi+1for all 1 ≤ i < lkAfra Zomorodian – CS 468 Lecture 7 - Page 24REDUCED EXAMPLEdabc˜M1=cd bc ab z1z2d − c 1 0 0 0 0c − b 0 1 0 0 0b − a 0 0 1 0 0a 0 0 0 0 0• z1= ad − bc − cd − ab and z2= ac − bc − ab form a basis for Z1• {d − c, c − b, b − a} is a basis for B0Afra Zomorodian – CS 468 Lecture 7 - Page 25REDUCED EXAMPLEM2=abc acdac −1 1ad 0 −1cd 0 1bc 1 0ab 1 0˜M2=−abc −acd + abcac − bc − ab 1 0ad − cd − bc − ab 0 1cd 0 0bc 0 0ab 0 0Afra Zomorodian – CS 468 Lecture 7 - Page 25-1NORMAL FORM˜Mk=b10...00 blk0 0• Description:1. the torsion coefficients of Hk−1are bi≥ 12. {ei| lk+ 1 ≤ i ≤ mk} is a basis for Zk. Therefore,rank Zk= mk− lk.3. {biˆei| 1 ≤ i ≤ lk} is a basis for Bk−1. Equivalently,rank Bk= rank Mk+1= lk+1.• βk= rank Zk− rank Bk= mk− lk− lk+1Afra Zomorodian – CS 468 Lecture 7 - Page 26IN S3• Algorithm takes O(m3) operations, but integers can get large• Subcomplexes are torsion-free, so we don’t need the force!• k-chain: c =Pini[σi], ni∈ Z, σi∈ K• Different view, niare coefficients• We can multiply, but not divide (in Z)• We can also change to other coefficients, such as R, Q, etc.• Z2Homology– restrict to 0,1, so unoriented simplices– −σ = σ– Addition is symmetric sum: c + d = (c ∪ d) − (c ∩ d).Afra Zomorodian – CS 468 Lecture 7 - Page