5 ms·

Computational Algebraic Topology, lecture notes [pdf]

127 points by MAXPOOL 6y ago

spekcular 6y ago
For anyone looking for the "computational" aspects, the only bit I could find was the algorithm presented in section 6. Otherwise these are pretty standard algebraic topology notes.
- pfortuny 6y ago
  Looks like “simplicial” would be a better adjective, or “combinatorial”, as opposed to “continuous”.
- WoahNoun 6y ago
  I assume it's using computational since the focus in on simplicial complexes where everything can theoretically be computed. Some of the filtration stuff on finite discrete points looks like Machine Learning / Topological Data Analysis which definitely wasn't covered in my AT class.
  - prionassembly 6y ago
    The hardest thing for me to grok trying to learn enough AT for TDA (but: I mean really learn, not just understand in a loose Medium-blog kind of way) was the ker/im definition of homology. I pestered people on IRC for days, and just worked hard to stretch my brain enough to see that it applies in many "small" cases. If you're coming from topology to AT and can grok the ker/im stuff, TDA should be easy peasy to you. I flunked (I think I scraped a couple of points on appeal by sophistry and desperation so I passed, but really) real analysis, so I never moved into topology beyond skimming books to "learn about" key concepts. You simply can't have too much math in life. I'm having a kid soon and I struggle between what seems truer to my core values (let the kid have a childhood and then personal inclinations; advise but not push; if he wants to do the gifted kid thing, yay) and what seems practical advice (learn as many human languages as you can, at least English, French and German; learn math deeply, suffering along the way).
    - spekcular 6y ago
      Did anyone suggest thinking of ker/im as "boundaries modulo cycles"? That is, homology detects "holes," loosely speaking, and a hole is exactly something that you can draw a cycle around, where that cycle is not the boundary of some disk (in 2 dimensions, for example). To be even more concrete, if I cut out a disk from a piece of paper, I've created a cycle (the circle bounding the disk) that is not the boundary of any disk in the piece of paper (because I cut it out). Admittedly, this gets a little funkier in higher dimensions, but for 2 dimensions, it's a good guide. (I think Hatcher's book has a discussion of how to make this idea precise in higher dimensions.)
      - prionassembly 6y ago
        It was the "modulo" I had trouble with (the idea of quotient spaces). I understood well how kernels corresponded to cycles (people on IRC made me do lots of calculations with chain complexes both in Z/2 and R), and had some idea of groups (or, at least, of when something is a semigroup and not a group...) but didn't have an internal feeling of what quotient groups were.
        jvvw 6y ago
        Do you grok equivalence classes because quotients (of anything) are basically sets of equivalence classes? And on the parenting front, luckily you start with a baby not a ten year old so you have lots of chance to grow as a parent before making those sorts of decisions - a lot of parenting is deciding when to be directive/non-directive and when to take charge based on your superior understanding of the world (not letting your toddler walk into the road!) and when to let them learn from their own mistakes.
      - Y_Y 6y ago
        This is just the same as my own conception, then again I also used (and can highly recommend) Hatcher. He kindly provides a pdf on his webpage here: https://pi.math.cornell.edu/~hatcher/AT/ATpage.html https://pi.math.cornell.edu/~hatcher/AT/ATpage.html
      - 6y ago
cambalache 6y ago
27 MB for just 100 pages of lecture notes? You can find in certain Russian site, 600p textbooks weighting 2-3 MB
- Koshkin 6y ago
  There's quite a few pictures in there.
- arunc 6y ago
  Examples please
kkylin 6y ago
This book looks like it may be a nice complement to these CAT notes: https://www2.math.upenn.edu/~ghrist/notes.html https://www2.math.upenn.edu/~ghrist/notes.html (I haven't gone through either.)
sharker8 6y ago
Anyone have a glossary or index for newbs? Like a shortcut to reading the symbolic notation? I have some expository knowledge to sets (ie. sets are denoted by capital letters). And some of the symbols (ie. the vertical pipe means given or 'where' and indicates a predicate assumption of sorts). Anyone have the cheat code for laypeople and undergrads?
- smt1 6y ago
  I recommend this book first actually to make sure you understand topology from a higher level perspective: https://www2.math.upenn.edu/~ghrist/notes.html https://www2.math.upenn.edu/~ghrist/notes.html It does a more panoramic view of topology and homological algebra, ending with category theory. I would read chapter 10.10 then appendix A first, but the rest of the book has a ton of illustrative motivational examples. IMHO, understanding the elegance of category theory is useful for understanding the connections between different types of math (that you may already know). There are a ton of types of math that don't really map that naturally to set theory, especially on computers. Learning some of the language of the commutative diagram (and functors, natural transformations, adjunctions) helps a lot IMHO since categorical structure can be found everywhere and it helps understand groups/rings/fields/homology/homotopy much easier, because it helps you learn how different math "behaves" relative to each other, and I find it more easily constructible on a computer (especially with any lang with higher order functions), you may want to think of the arrows as maps/functions/morphisms between types/interfaces/physical processes/computational states.
- xyzzyz 6y ago
  Sorry, there is no cheat code here. Understanding this stuff requires real and significant time investment, and is beyond arms reach (though not beyond sight) of undergrads and especially laypeople. If you put in investment, understand what is module, quotient operation, exact sequence etc, you will be able to follow. However, this is not trivial and not just an issue of notation: there are real, fundamental concepts here that one must learn to grasp.
  - sharker8 6y ago
    What would be your "pareto list", ie the list of the concepts, symbols, notation, etc that would get one 80% of the way with 20% of the knowledge?
heinrichhartman 6y ago
Does anyone have a reference to actual computational applications of Algebraic Topology? These notes contain the definition of various chain complexes and groups (co-homology/homotopy) that are in-principle computable. However, I have not seen this being efficiently applied somewhere, and not been able to come up with interesting applications myself. Topics I have considered are: 1. Triangulation of solutions of equations (for e.g. homology computations) does not seem to be very popular, at least in dimension >3. I suspect this is a hard problem, but maybe I am just missing pointers to the right literature. 2. CAD applications or Computer Games have lot's of triangulated objects. Their topology seems to be not to be very interesting. Again: In dimension <=3 there is really not that much going on. And since you have constructed the object yourself, you probably know the geometry already. 3. Graphs appear everywhere, and can be viewed as 1-dimensional chain complexes but do not have interesting co-homology groups. 4. Did anyone compute homology groups for "Manifold Learning"? It's also not clear to me, how much interesting information can be extracted from those homology groups. Applications of Homotopy/Homology in (semi-classical) Physics are already quite slim (apart from Quantum Field Theory, String Theory, Gauge Theory?!) as most of it takes place in contractible spaces $IR^n$.
- shenberg 6y ago
  The field of topological data analysis attempts to use homologies that persist in multiple scales (="Persistent Homologies") as learnable features, but frankly nothing I saw from this field seemed to work particularly well. The one practical algorithm I've seen which uses topological arguments for justification is UMAP for dimensionality reduction, the core idea IMO* is very much like density estimation and I'm not sure the mathematical justification gives more insight. * The core idea IMO: while in high-dimensional space, absolute distances lose meaning, relative distances between neighboring points are good yard-sticks. This insight is also what powers DBSCAN and other such density-based algorithms. I don't think using the language of simplical complexes when explaining the algorithm simplifies or adds insight.
- thereticent 6y ago
  I'm not sure if this is the kind of example you mean, but there have been interesting applications in analyzing electroencephalographic readings in various cognitive and neurologic disorders: e.g. https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0166787 https://journals.plos.org/plosone/article?id=10.1371/journal...
jamessb 6y ago
The webpage for the course [1] includes not just these lecture notes, but also 4 problem sets and links to videos of the lectures on YouTube. [1]: http://people.maths.ox.ac.uk/nanda/cat/ http://people.maths.ox.ac.uk/nanda/cat/
meiji163 6y ago
Cool notes, I also recommend this paper which actually implements persistent homology :P http://fodava.gatech.edu/files/reports/FODAVA-08-02.pdf http://fodava.gatech.edu/files/reports/FODAVA-08-02.pdf
outlace 6y ago
I wrote a series of blog posts about persistent homology and topological data analysis for absolute beginners as I was obsessed with it for some time: http://outlace.com/TDApart1.html http://outlace.com/TDApart1.html
- flafla2 6y ago
  This looks great, thanks!
- 3PS 6y ago
  Just briefly skimming over your post, a quick correction to the Continuity section: > Definition (Homomorphism) There is a homomorphism (i.e. an equivalence relation) between two topological spaces if there exists a function f:X→Y, where X and Y are topological spaces (X,τX) and (Y,τY) with the following properties This should be "homeomorphism", not "homomorphism". A homomorphism is a structure-preserving map, like a continuous function (in the context of topological spaces) or a linear map (in the context of vector spaces). Homomorphisms are very much one-directional. Homeomorphisms, on the other hand, are specifically equivalences between topological spaces, and are defined as continuous functions with continuous inverses. Edit: finished reading it. I'm impressed by how much you cover in such a short space. Overall it looks good, so thanks for taking the time to write it. Some of these ideas are at a pretty high level of abstractness, so I sympathize with anyone who struggles to get any kind of intuition for them at a first go.
  - outlace 6y ago
    Thanks for the correction!
Koshkin 6y ago
These notes (on a different yet somewhat related subject) seem a little more friendly in the way they explain the basics: https://www.cs.cmu.edu/~kmcrane/Projects/DDG/ https://www.cs.cmu.edu/~kmcrane/Projects/DDG/

127 points by MAXPOOL 6y ago

For anyone looking for the "computational" aspects, the only bit I could find was the algorithm presented in section 6. Otherwise these are pretty standard algebraic topology notes.

pfortuny 6y ago
Looks like “simplicial” would be a better adjective, or “combinatorial”, as opposed to “continuous”.
WoahNoun 6y ago
I assume it's using computational since the focus in on simplicial complexes where everything can theoretically be computed. Some of the filtration stuff on finite discrete points looks like Machine Learning / Topological Data Analysis which definitely wasn't covered in my AT class.
- prionassembly 6y ago
  The hardest thing for me to grok trying to learn enough AT for TDA (but: I mean really learn, not just understand in a loose Medium-blog kind of way) was the ker/im definition of homology. I pestered people on IRC for days, and just worked hard to stretch my brain enough to see that it applies in many "small" cases. If you're coming from topology to AT and can grok the ker/im stuff, TDA should be easy peasy to you. I flunked (I think I scraped a couple of points on appeal by sophistry and desperation so I passed, but really) real analysis, so I never moved into topology beyond skimming books to "learn about" key concepts. You simply can't have too much math in life. I'm having a kid soon and I struggle between what seems truer to my core values (let the kid have a childhood and then personal inclinations; advise but not push; if he wants to do the gifted kid thing, yay) and what seems practical advice (learn as many human languages as you can, at least English, French and German; learn math deeply, suffering along the way).
  - spekcular 6y ago
    Did anyone suggest thinking of ker/im as "boundaries modulo cycles"? That is, homology detects "holes," loosely speaking, and a hole is exactly something that you can draw a cycle around, where that cycle is not the boundary of some disk (in 2 dimensions, for example). To be even more concrete, if I cut out a disk from a piece of paper, I've created a cycle (the circle bounding the disk) that is not the boundary of any disk in the piece of paper (because I cut it out). Admittedly, this gets a little funkier in higher dimensions, but for 2 dimensions, it's a good guide. (I think Hatcher's book has a discussion of how to make this idea precise in higher dimensions.)
    - prionassembly 6y ago
      It was the "modulo" I had trouble with (the idea of quotient spaces). I understood well how kernels corresponded to cycles (people on IRC made me do lots of calculations with chain complexes both in Z/2 and R), and had some idea of groups (or, at least, of when something is a semigroup and not a group...) but didn't have an internal feeling of what quotient groups were.
      - jvvw 6y ago
        Do you grok equivalence classes because quotients (of anything) are basically sets of equivalence classes? And on the parenting front, luckily you start with a baby not a ten year old so you have lots of chance to grow as a parent before making those sorts of decisions - a lot of parenting is deciding when to be directive/non-directive and when to take charge based on your superior understanding of the world (not letting your toddler walk into the road!) and when to let them learn from their own mistakes.
    - Y_Y 6y ago
      This is just the same as my own conception, then again I also used (and can highly recommend) Hatcher. He kindly provides a pdf on his webpage here: https://pi.math.cornell.edu/~hatcher/AT/ATpage.html https://pi.math.cornell.edu/~hatcher/AT/ATpage.html
    - 6y ago

cambalache 6y ago

27 MB for just 100 pages of lecture notes? You can find in certain Russian site, 600p textbooks weighting 2-3 MB

Koshkin 6y ago
There's quite a few pictures in there.
arunc 6y ago
Examples please

kkylin 6y ago

This book looks like it may be a nice complement to these CAT notes: https://www2.math.upenn.edu/~ghrist/notes.html https://www2.math.upenn.edu/~ghrist/notes.html (I haven't gone through either.)

sharker8 6y ago

Anyone have a glossary or index for newbs? Like a shortcut to reading the symbolic notation? I have some expository knowledge to sets (ie. sets are denoted by capital letters). And some of the symbols (ie. the vertical pipe means given or 'where' and indicates a predicate assumption of sorts). Anyone have the cheat code for laypeople and undergrads?

smt1 6y ago
I recommend this book first actually to make sure you understand topology from a higher level perspective: https://www2.math.upenn.edu/~ghrist/notes.html https://www2.math.upenn.edu/~ghrist/notes.html It does a more panoramic view of topology and homological algebra, ending with category theory. I would read chapter 10.10 then appendix A first, but the rest of the book has a ton of illustrative motivational examples. IMHO, understanding the elegance of category theory is useful for understanding the connections between different types of math (that you may already know). There are a ton of types of math that don't really map that naturally to set theory, especially on computers. Learning some of the language of the commutative diagram (and functors, natural transformations, adjunctions) helps a lot IMHO since categorical structure can be found everywhere and it helps understand groups/rings/fields/homology/homotopy much easier, because it helps you learn how different math "behaves" relative to each other, and I find it more easily constructible on a computer (especially with any lang with higher order functions), you may want to think of the arrows as maps/functions/morphisms between types/interfaces/physical processes/computational states.
xyzzyz 6y ago
Sorry, there is no cheat code here. Understanding this stuff requires real and significant time investment, and is beyond arms reach (though not beyond sight) of undergrads and especially laypeople. If you put in investment, understand what is module, quotient operation, exact sequence etc, you will be able to follow. However, this is not trivial and not just an issue of notation: there are real, fundamental concepts here that one must learn to grasp.
- sharker8 6y ago
  What would be your "pareto list", ie the list of the concepts, symbols, notation, etc that would get one 80% of the way with 20% of the knowledge?

heinrichhartman 6y ago

Does anyone have a reference to actual computational applications of Algebraic Topology? These notes contain the definition of various chain complexes and groups (co-homology/homotopy) that are in-principle computable. However, I have not seen this being efficiently applied somewhere, and not been able to come up with interesting applications myself. Topics I have considered are: 1. Triangulation of solutions of equations (for e.g. homology computations) does not seem to be very popular, at least in dimension >3. I suspect this is a hard problem, but maybe I am just missing pointers to the right literature. 2. CAD applications or Computer Games have lot's of triangulated objects. Their topology seems to be not to be very interesting. Again: In dimension <=3 there is really not that much going on. And since you have constructed the object yourself, you probably know the geometry already. 3. Graphs appear everywhere, and can be viewed as 1-dimensional chain complexes but do not have interesting co-homology groups. 4. Did anyone compute homology groups for "Manifold Learning"? It's also not clear to me, how much interesting information can be extracted from those homology groups. Applications of Homotopy/Homology in (semi-classical) Physics are already quite slim (apart from Quantum Field Theory, String Theory, Gauge Theory?!) as most of it takes place in contractible spaces $IR^n$.

shenberg 6y ago
The field of topological data analysis attempts to use homologies that persist in multiple scales (="Persistent Homologies") as learnable features, but frankly nothing I saw from this field seemed to work particularly well. The one practical algorithm I've seen which uses topological arguments for justification is UMAP for dimensionality reduction, the core idea IMO* is very much like density estimation and I'm not sure the mathematical justification gives more insight. * The core idea IMO: while in high-dimensional space, absolute distances lose meaning, relative distances between neighboring points are good yard-sticks. This insight is also what powers DBSCAN and other such density-based algorithms. I don't think using the language of simplical complexes when explaining the algorithm simplifies or adds insight.
thereticent 6y ago
I'm not sure if this is the kind of example you mean, but there have been interesting applications in analyzing electroencephalographic readings in various cognitive and neurologic disorders: e.g. https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0166787 https://journals.plos.org/plosone/article?id=10.1371/journal...

jamessb 6y ago

The webpage for the course [1] includes not just these lecture notes, but also 4 problem sets and links to videos of the lectures on YouTube. [1]: http://people.maths.ox.ac.uk/nanda/cat/ http://people.maths.ox.ac.uk/nanda/cat/

meiji163 6y ago

Cool notes, I also recommend this paper which actually implements persistent homology :P http://fodava.gatech.edu/files/reports/FODAVA-08-02.pdf http://fodava.gatech.edu/files/reports/FODAVA-08-02.pdf

outlace 6y ago

I wrote a series of blog posts about persistent homology and topological data analysis for absolute beginners as I was obsessed with it for some time: http://outlace.com/TDApart1.html http://outlace.com/TDApart1.html

flafla2 6y ago
This looks great, thanks!
3PS 6y ago
Just briefly skimming over your post, a quick correction to the Continuity section: > Definition (Homomorphism) There is a homomorphism (i.e. an equivalence relation) between two topological spaces if there exists a function f:X→Y, where X and Y are topological spaces (X,τX) and (Y,τY) with the following properties This should be "homeomorphism", not "homomorphism". A homomorphism is a structure-preserving map, like a continuous function (in the context of topological spaces) or a linear map (in the context of vector spaces). Homomorphisms are very much one-directional. Homeomorphisms, on the other hand, are specifically equivalences between topological spaces, and are defined as continuous functions with continuous inverses. Edit: finished reading it. I'm impressed by how much you cover in such a short space. Overall it looks good, so thanks for taking the time to write it. Some of these ideas are at a pretty high level of abstractness, so I sympathize with anyone who struggles to get any kind of intuition for them at a first go.
- outlace 6y ago
  Thanks for the correction!

Koshkin 6y ago

These notes (on a different yet somewhat related subject) seem a little more friendly in the way they explain the basics: https://www.cs.cmu.edu/~kmcrane/Projects/DDG/ https://www.cs.cmu.edu/~kmcrane/Projects/DDG/