3 ms·
LolWolf, thank you very much for 'defending' the algebra much better than I could possibly have defended it myself :-) Just to add: I don't understand why we s
by sn0wleopard 10y ago
LolWolf, thank you very much for 'defending' the algebra much better than I could possibly have defended it myself :-)
Just to add: I don't understand why we should compare the algebra and the matrix encoding suggested above. The latter is just one possible implementation (a model) of the former. It's a good, useful model. But the point of having an algebra is that we can abstract of details of particular implementation and instead focus on the laws that all such implementations satisfy. Sometimes these laws can be interesting by themselves (at least they are interesting to me).
- LolWolf 10y agoI agree: I don't really see what the obsession is with linear-algebra based graph theory. Yes, it's cool, yes it has interesting results, but it's not everything and we've got tools for semigroups and general algebras that may be useful here, along with natural generalizations that may emerge which may not be obvious in the linear-algebraic picture. Anyways, thanks for the interesting blog post!
- SomeStupidPoint 10y agoAlmost every time I've implemented a graph algorithm professionally, it's been using matrix operations because they came with a GPU implementation and smashed the performance of a naive implementation. But from a design and theory standpoint, I prefer to work independent of the representation as much as possible, and only switch in the matrix language as an implementation of a type in already working code. (Sometimes, this isnt quite possible and you need to, eg, reorder operations to make it efficient to calculate in your representation.) So I would say that linear algebra is a big deal for implementations, if not as much of one theoretically. (Mostly cause my computer has really fast linear algebra chips/code, and not so much for random graph traversal.)
- LolWolf 10y agoSure, I agree; in this case I refer to "tools" as theoretical tools rather than computational ones. There's no debate on the merits of computational tractability by converting problems to linear algebra ones; I was speaking from a purely graph-theoretic standpoint.
- sn0wleopard 10y agoThanks LolWolf! You mentioned a few interesting ideas about monotonicity/fixed-point theorems & computability/hardness and I'd very curious to know if you come up with anything on these fronts -- please drop me an email if you do!
- LolWolf 10y agoCertainly will; thanks again for the interesting post!