7 ms·

Leave it to a Haskell coder to make an incomprehensible mess of matrices under addition.

by ajamesm 10y ago

LolWolf 10y ago
Matrices under addition? I know very little of Haskell, but I think this blog post is quite interesting; it's not obvious to me how you would translate the 'join' operator (->) into a matrix formulation that preserves nice structure (you'd have to be weird about dimensions and such). Sure, the 'add' operation is nice (+) since it's just an OR over F_2 (e.g. 0+0=0, 1+0=0+1=1+1=1 [1]) in the matrix representation, but even this involves some bending-over-backwards by noting that you still have to extend the dimensions of the matrices in question in order to even make sense (think about, say (1->2) + (3->4)). I think the minimal axioms are quite elegant if you ask me. ------ [1] Over F_2, this isn't quite the same addition; I define a+b ≡ a⊕b + a·b where ⊕ is XOR and · is AND, which are the usual, defined operations. EDIT: I guess I didn't mean to say it's not obvious to do these things per se, but rather, a simplistic approach without defining a universe of possible vertices and a mapping from these into indices can't really be done in the linear-algebraic picture.
- JadeNB 10y ago
  With an obvious notion of negation of graphs, wouldn't the `connect` operation be \g1 g2 -> not $ (not g1) `overlay` (not g2)? (I've already asked about lattice theory elsewhere (https://news.ycombinator.com/item?id=13125334 https://news.ycombinator.com/item?id=13125334 ); this thought makes me wonder if there's any connection to modal logic https://en.wikipedia.org/wiki/Modal_logic https://en.wikipedia.org/wiki/Modal_logic, where modalities are often defined in these sort of "de Morgan pairs".) EDIT: I originally typo'd and proposed the above as a definition of the `overlay` operation, which would be both a pointless circularity and wrong.
  - LolWolf 10y ago
    I'm afraid I don't quite understand what the negation of a graph is in this case and what you mean by 'overlay,' perhaps elaborate a bit?
    - taejo 10y ago
      overlay or + is the operation from the article; not is the graph with the complementary edge set (i.e. `not (V, E) = (V, E \ (V × V))`)
      - JadeNB 10y ago
        Yup, that's what I meant (except that I think your set complement is backwards). Sorry for not replying earlier; I was "submitting too fast."
        taejo 10y ago
        > I think your set complement is backwards It is. Unfortunately I can't fix it now.
  - sn0wleopard 10y ago
    JadeNB: This works but I believe only in the case with undirected graphs and if the graphs being connected do not have common vertices. So, indeed there is a sort of de Morgan law: a -- b = !(!a + !b) where ! is the graph edge-complement, a and b do not have common vertices, and -- is a commutative version of ->. (Responding so late, because I was also "submitting too fast"!)
    - JadeNB 10y ago
      > JadeNB: This works but I believe only in the case with undirected graphs and if the graphs being connected do not have common vertices. Agreed; I thought that your `overlay` was the "(forced) disjoint union". I had missed that "(vertex x) `overlay` (vertex y)" was not isomorphic to "(vertex x) `overlay` (vertex x)". I don't even know what negation would mean for directed graphs. (By the way, your code doesn't seem to give any way of producing inhabitants of `Vertex g`. Since the displayed code only ever uses `Vertex g` in order to promote it immediately to `Graph g`, does it make sense just to have them as a separate type? (Maybe I'm misreading; it's been a while since I've Haskell'd.) Also, am I wrong to read `vertex` as a kind of `return`? (I hope that I am not wrong to think that graphs should serve as just as good instances of monads as lists, if not better.)) While we're talking: thanks for this article; I enjoyed it a lot. My one suggestion is that I think that what you call a "clique" is usually called a "complete graph", with "clique" (implicitly, in G) reserved for subgraphs of G that happen to be complete. https://en.wikipedia.org/wiki/Clique_(graph_theory) https://en.wikipedia.org/wiki/Clique_(graph_theory)
      - sn0wleopard 10y ago
        > By the way, your code doesn't seem to give any way of producing inhabitants of `Vertex g`. In fully polymorphic code (like clique) you indeed can't produce new inhabitants, or do anything else with the values of type `Vertex g`. However, if you know something about `Vertex g` then you can do certain things. For example, if we know that the type of vertices has `Ord` instance then we can compare them (as we do in `Relation`). And in very concrete code, e.g. operating on `Basic Int` values, you can create new inhabitants freely -- any number will do. > Also, am I wrong to read `vertex` as a kind of `return`? It is indeed very much like `return` or `pure`! We use it to inject a type into a sort of container type, in this case, into a graph type. > I hope that I am not wrong to think that graphs should serve as just as good instances of monads as lists, if not better Many `Graph` instances are `Monad`s. For example, `Basic` is a `Monad` (and many other things too). But on the other hand `Relation` is not a `Monad`, because it imposes the `Ord` constraint on the underlying type (and Haskell monads are not allowed that). > While we're talking: thanks for this article; I enjoyed it a lot. Thank you! I didn't expect so much interest to it, so I'm a bit overwhelmed to be honest :) > My one suggestion is that I think that what you call a "clique" is usually called a "complete graph", with "clique" (implicitly, in G) reserved for subgraphs of G that happen to be complete. Thanks, indeed "clique" may be not the best name... I decided to use it, because I would like to reserve "complete graph" to mean something like `clique [1..]` i.e. the complete graph on the whole universe. If we look from this perspective then something like `clique [1..10]` may look like a clique within some bigger graph. Anyway, I admit this may be confusing.
- ajamesm 10y ago
  It's not really 'extending the dimensions of the matrices' -- we live in a universe with an infinite number of distinct vertices, so the matrices are necessarily of infinite degree. It's only the sake of notation that we project them to finite dimensions. A: x x x B: y y y x x x y y y x x x y y y A join B: x x x 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 x x x 1 1 1 x x x 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 x x x 1 1 1 x x x 0 0 0 + 0 0 0 0 0 0 + 0 0 0 1 1 1 = x x x 1 1 1 0 0 0 0 0 0 0 0 0 y y y 1 1 1 0 0 0 1 1 1 y y y 0 0 0 0 0 0 0 0 0 y y y 1 1 1 0 0 0 1 1 1 y y y 0 0 0 0 0 0 0 0 0 y y y 1 1 1 0 0 0 1 1 1 y y y This becomes much less accessible when dressing this up as a novel 'algebra of graphs' and obscuring it in Haskell syntax.
  - LolWolf 10y ago
    That's fine, but then in the 'infinite vertices case' we require an associated numbering scheme and defining an ordering over vertices which requires a bijection from whatever set you're working with into an index labeling (⊆ ℕ), etc, when this could just be abstracted away. In general, I don't think this is any cleaner than the few axioms defined whose structure we can attack with the tools of semirings. Overall, I think both cases have their uses; matrices in the area of computation and abstract algebras where manipulations are straightforward. In particular, I'm interested here since the axioms can be written as a language and operations can be done over finite sets which may yield some nice computability results over this 'language of graphs.'
    - 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).
- rjtobin 10y ago
  Just a side note: The join of two graphs does correspond to a reasonably nice matrix operation: take the two adjacency matrices A and B (of dim m and n respectively, say), then form an (n+m)x(n+m) block matrix: A J J B where J is the all one matrix (of the appropriate sizes to make the above matrix square). Further aside: this block form might seem unnatural, but it pops up all the time in adjacency matrices of graphs. For example, bipartite graphs are exactly those that can be written in the form 0 A B 0 (Where B = transpose(A))
  - LolWolf 10y ago
    Yep, I definitely agree! Nominally, there are plenty of interesting results in spectral graph theory which make use of operations like these (esp. when computing laplacians/spectral partitions, etc), but, like most tools, while we can represent many groups/associated structures as linear-algebraic operations, there are subtle results that emerge from looking at an axiomatic treatment which aren't as clear when working with the linear-algebraic picture.
    - ajamesm 10y ago
      Like what?
      - LolWolf 10y ago
        Prove that a topological sort exists for a given graph using only linear algebraic properties of the adjacency matrix or the laplacian. Or even, give a proof that a graph is a DAG iff there exists a topological sort using only linear algebraic operations on the adjacency matrix. The point is, I'm sure you can do this; in some sense, we can perform every operation on a graph as we can its adjacency matrix, but why make it so complicated when there are easier pictures to work with? Why perform surgery with a chainsaw when a scalpel will do without such a mess?
        ajamesm 10y ago
        https://cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.pdf https://cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.pd... I get that lin alg maybe isn't your picture of elegance, but you can't say that proof is laborious or esoteric. Any intro-level LA course is enough to grok it.
JadeNB 10y ago
> Leave it to a Haskell coder to make an incomprehensible mess of matrices under addition. Since we are supposed to explain downvotes: this seems to me like useless anti-snobbery. Even a minor variation like "Although I believe that I understand matrix addition well, I had difficulty understanding the translation into Haskell" seems more constructive. (On the other hand, CTRL+Fing the article, which I haven't yet read, doesn't show any mention of addition. Are you pointing out that this is matrix addition in a cumbersome disguise? That, too, would have been more useful, without even having to make any linguistic slurs.)
- pvg 10y ago
  Since we are supposed to explain downvotes We aren't. If anything, we're encouraged not to talk about vote meta stuff. You can just reply if you want to reply and vote however you want (or not at all), independently of that.
- ajamesm 10y ago
  Yes, this is matrix addition in a cumbersome disguise. Haskell is a fine language, it's the authors I can't stand. I'm anti-snobbery because snobbery keeps people from understanding stuff. Programming languages are about building a standard and a foundation for common understanding -- Haskell articles are all CV-fodder about byzantine type algebras.
  - LolWolf 10y ago
    I do agree with the anti-snobbery part, but, again, as someone who totally skipped over the Haskell parts (which were mostly gibberish to me), I still think the article was quite enlightening. Of course, it's also a matter of the audience you're picking, I wouldn't talk about optimization algorithms, convexity, and computational hardness to an audience of 10-year-olds first learning to program (even though it underlies everything they will do in any first programming class which can be done efficiently), but I also wouldn't discuss introductory programming topics and the definition of a Turing machine to an audience of theoretical computer scientists, even if that's what we end up talking about in a very abstracted sense.
  - 10y ago
wyager 10y ago
Ironically, I think you failed to comprehend the article. Adjacency matrices (which you are presumably referring to, but were not mentioned in the article) are neither efficient nor algebraicly convenient. No one represents graphs as matrices in computer science, and graph theorists rarely touch representation theory. It's not that useful when the natural representations are normally much simpler and easier to work with.
- rjtobin 10y ago
  Not sure it's fair to say that graph theorists rarely use matrices to represent graphs: for many problems in graph theory some of the simplest solution involves representing the graph as a matrix (eg Hoffman-Singleton theorem).
- ajamesm 10y ago
  Oh, yes, we should definitely draw lessons from academic mathematicians about what is accessible and convenient to understand. THAT's a field that's never had a problem connecting to laymen.
  - Retra 10y ago
    Hard to imagine doing anything interesting if you've got to appeal to laymen with every word.
- GFK_of_xmaspast 10y ago
  Meanwhile: http://epubs.siam.org/doi/book/10.1137/1.9780898719918 http://epubs.siam.org/doi/book/10.1137/1.9780898719918 https://www.cs.ucsb.edu/~gilbert/talks/GilbertGABB19May2014.pdf https://www.cs.ucsb.edu/~gilbert/talks/GilbertGABB19May2014.... http://graphblas.org/index.php/Graph_BLAS_Forum http://graphblas.org/index.php/Graph_BLAS_Forum http://www.netlib.org/utk/people/JackDongarra/PAPERS/GraphPrimitives-HPEC.pdf http://www.netlib.org/utk/people/JackDongarra/PAPERS/GraphPr... https://people.cs.clemson.edu/~isafro/na13/l12.pdf https://people.cs.clemson.edu/~isafro/na13/l12.pdf
- JadeNB 10y ago
  > No one represents graphs as matrices in computer science, and graph theorists rarely touch representation theory. Are you conflating linear algebra and representation theory, or did you really mean to refer to representation theory in particular? The notion of a quiver (https://en.wikipedia.org/wiki/Quiver_(mathematics) https://en.wikipedia.org/wiki/Quiver_(mathematics) ) seems to me to be a unification of the two fields; I'm not a graph theorist, but I have a hard time imagining that they don't at least consider these structures.

Leave it to a Haskell coder to make an incomprehensible mess of matrices under addition.

by ajamesm 10y ago

Leave it to a Haskell coder to make an incomprehensible mess of matrices under addition.

Matrices under addition? I know very little of Haskell, but I think this blog post is quite interesting; it's not obvious to me how you would translate the 'join' operator (->) into a matrix formulation that preserves nice structure (you'd have to be weird about dimensions and such). Sure, the 'add' operation is nice (+) since it's just an OR over F_2 (e.g. 0+0=0, 1+0=0+1=1+1=1 [1]) in the matrix representation, but even this involves some bending-over-backwards by noting that you still have to extend the dimensions of the matrices in question in order to even make sense (think about, say (1->2) + (3->4)). I think the minimal axioms are quite elegant if you ask me. ------ [1] Over F_2, this isn't quite the same addition; I define a+b ≡ a⊕b + a·b where ⊕ is XOR and · is AND, which are the usual, defined operations. EDIT: I guess I didn't mean to say it's not obvious to do these things per se, but rather, a simplistic approach without defining a universe of possible vertices and a mapping from these into indices can't really be done in the linear-algebraic picture.

JadeNB 10y ago
With an obvious notion of negation of graphs, wouldn't the `connect` operation be \g1 g2 -> not $ (not g1) `overlay` (not g2)? (I've already asked about lattice theory elsewhere (https://news.ycombinator.com/item?id=13125334 https://news.ycombinator.com/item?id=13125334 ); this thought makes me wonder if there's any connection to modal logic https://en.wikipedia.org/wiki/Modal_logic https://en.wikipedia.org/wiki/Modal_logic, where modalities are often defined in these sort of "de Morgan pairs".) EDIT: I originally typo'd and proposed the above as a definition of the `overlay` operation, which would be both a pointless circularity and wrong.
- LolWolf 10y ago
  I'm afraid I don't quite understand what the negation of a graph is in this case and what you mean by 'overlay,' perhaps elaborate a bit?
  - taejo 10y ago
    overlay or + is the operation from the article; not is the graph with the complementary edge set (i.e. `not (V, E) = (V, E \ (V × V))`)
    - JadeNB 10y ago
      Yup, that's what I meant (except that I think your set complement is backwards). Sorry for not replying earlier; I was "submitting too fast."
      - taejo 10y ago
        > I think your set complement is backwards It is. Unfortunately I can't fix it now.
- sn0wleopard 10y ago
  JadeNB: This works but I believe only in the case with undirected graphs and if the graphs being connected do not have common vertices. So, indeed there is a sort of de Morgan law: a -- b = !(!a + !b) where ! is the graph edge-complement, a and b do not have common vertices, and -- is a commutative version of ->. (Responding so late, because I was also "submitting too fast"!)
  - JadeNB 10y ago
    > JadeNB: This works but I believe only in the case with undirected graphs and if the graphs being connected do not have common vertices. Agreed; I thought that your `overlay` was the "(forced) disjoint union". I had missed that "(vertex x) `overlay` (vertex y)" was not isomorphic to "(vertex x) `overlay` (vertex x)". I don't even know what negation would mean for directed graphs. (By the way, your code doesn't seem to give any way of producing inhabitants of `Vertex g`. Since the displayed code only ever uses `Vertex g` in order to promote it immediately to `Graph g`, does it make sense just to have them as a separate type? (Maybe I'm misreading; it's been a while since I've Haskell'd.) Also, am I wrong to read `vertex` as a kind of `return`? (I hope that I am not wrong to think that graphs should serve as just as good instances of monads as lists, if not better.)) While we're talking: thanks for this article; I enjoyed it a lot. My one suggestion is that I think that what you call a "clique" is usually called a "complete graph", with "clique" (implicitly, in G) reserved for subgraphs of G that happen to be complete. https://en.wikipedia.org/wiki/Clique_(graph_theory) https://en.wikipedia.org/wiki/Clique_(graph_theory)
    - sn0wleopard 10y ago
      > By the way, your code doesn't seem to give any way of producing inhabitants of `Vertex g`. In fully polymorphic code (like clique) you indeed can't produce new inhabitants, or do anything else with the values of type `Vertex g`. However, if you know something about `Vertex g` then you can do certain things. For example, if we know that the type of vertices has `Ord` instance then we can compare them (as we do in `Relation`). And in very concrete code, e.g. operating on `Basic Int` values, you can create new inhabitants freely -- any number will do. > Also, am I wrong to read `vertex` as a kind of `return`? It is indeed very much like `return` or `pure`! We use it to inject a type into a sort of container type, in this case, into a graph type. > I hope that I am not wrong to think that graphs should serve as just as good instances of monads as lists, if not better Many `Graph` instances are `Monad`s. For example, `Basic` is a `Monad` (and many other things too). But on the other hand `Relation` is not a `Monad`, because it imposes the `Ord` constraint on the underlying type (and Haskell monads are not allowed that). > While we're talking: thanks for this article; I enjoyed it a lot. Thank you! I didn't expect so much interest to it, so I'm a bit overwhelmed to be honest :) > My one suggestion is that I think that what you call a "clique" is usually called a "complete graph", with "clique" (implicitly, in G) reserved for subgraphs of G that happen to be complete. Thanks, indeed "clique" may be not the best name... I decided to use it, because I would like to reserve "complete graph" to mean something like `clique [1..]` i.e. the complete graph on the whole universe. If we look from this perspective then something like `clique [1..10]` may look like a clique within some bigger graph. Anyway, I admit this may be confusing.
ajamesm 10y ago
It's not really 'extending the dimensions of the matrices' -- we live in a universe with an infinite number of distinct vertices, so the matrices are necessarily of infinite degree. It's only the sake of notation that we project them to finite dimensions. A: x x x B: y y y x x x y y y x x x y y y A join B: x x x 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 x x x 1 1 1 x x x 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 x x x 1 1 1 x x x 0 0 0 + 0 0 0 0 0 0 + 0 0 0 1 1 1 = x x x 1 1 1 0 0 0 0 0 0 0 0 0 y y y 1 1 1 0 0 0 1 1 1 y y y 0 0 0 0 0 0 0 0 0 y y y 1 1 1 0 0 0 1 1 1 y y y 0 0 0 0 0 0 0 0 0 y y y 1 1 1 0 0 0 1 1 1 y y y This becomes much less accessible when dressing this up as a novel 'algebra of graphs' and obscuring it in Haskell syntax.
- LolWolf 10y ago
  That's fine, but then in the 'infinite vertices case' we require an associated numbering scheme and defining an ordering over vertices which requires a bijection from whatever set you're working with into an index labeling (⊆ ℕ), etc, when this could just be abstracted away. In general, I don't think this is any cleaner than the few axioms defined whose structure we can attack with the tools of semirings. Overall, I think both cases have their uses; matrices in the area of computation and abstract algebras where manipulations are straightforward. In particular, I'm interested here since the axioms can be written as a language and operations can be done over finite sets which may yield some nice computability results over this 'language of graphs.'
  - 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).
rjtobin 10y ago
Just a side note: The join of two graphs does correspond to a reasonably nice matrix operation: take the two adjacency matrices A and B (of dim m and n respectively, say), then form an (n+m)x(n+m) block matrix: A J J B where J is the all one matrix (of the appropriate sizes to make the above matrix square). Further aside: this block form might seem unnatural, but it pops up all the time in adjacency matrices of graphs. For example, bipartite graphs are exactly those that can be written in the form 0 A B 0 (Where B = transpose(A))
- LolWolf 10y ago
  Yep, I definitely agree! Nominally, there are plenty of interesting results in spectral graph theory which make use of operations like these (esp. when computing laplacians/spectral partitions, etc), but, like most tools, while we can represent many groups/associated structures as linear-algebraic operations, there are subtle results that emerge from looking at an axiomatic treatment which aren't as clear when working with the linear-algebraic picture.
  - ajamesm 10y ago
    Like what?
    - LolWolf 10y ago
      Prove that a topological sort exists for a given graph using only linear algebraic properties of the adjacency matrix or the laplacian. Or even, give a proof that a graph is a DAG iff there exists a topological sort using only linear algebraic operations on the adjacency matrix. The point is, I'm sure you can do this; in some sense, we can perform every operation on a graph as we can its adjacency matrix, but why make it so complicated when there are easier pictures to work with? Why perform surgery with a chainsaw when a scalpel will do without such a mess?
      - ajamesm 10y ago
        https://cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.pdf https://cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.pd... I get that lin alg maybe isn't your picture of elegance, but you can't say that proof is laborious or esoteric. Any intro-level LA course is enough to grok it.

JadeNB 10y ago

> Leave it to a Haskell coder to make an incomprehensible mess of matrices under addition. Since we are supposed to explain downvotes: this seems to me like useless anti-snobbery. Even a minor variation like "Although I believe that I understand matrix addition well, I had difficulty understanding the translation into Haskell" seems more constructive. (On the other hand, CTRL+Fing the article, which I haven't yet read, doesn't show any mention of addition. Are you pointing out that this is matrix addition in a cumbersome disguise? That, too, would have been more useful, without even having to make any linguistic slurs.)

pvg 10y ago
Since we are supposed to explain downvotes We aren't. If anything, we're encouraged not to talk about vote meta stuff. You can just reply if you want to reply and vote however you want (or not at all), independently of that.
ajamesm 10y ago
Yes, this is matrix addition in a cumbersome disguise. Haskell is a fine language, it's the authors I can't stand. I'm anti-snobbery because snobbery keeps people from understanding stuff. Programming languages are about building a standard and a foundation for common understanding -- Haskell articles are all CV-fodder about byzantine type algebras.
- LolWolf 10y ago
  I do agree with the anti-snobbery part, but, again, as someone who totally skipped over the Haskell parts (which were mostly gibberish to me), I still think the article was quite enlightening. Of course, it's also a matter of the audience you're picking, I wouldn't talk about optimization algorithms, convexity, and computational hardness to an audience of 10-year-olds first learning to program (even though it underlies everything they will do in any first programming class which can be done efficiently), but I also wouldn't discuss introductory programming topics and the definition of a Turing machine to an audience of theoretical computer scientists, even if that's what we end up talking about in a very abstracted sense.
- 10y ago

wyager 10y ago

Ironically, I think you failed to comprehend the article. Adjacency matrices (which you are presumably referring to, but were not mentioned in the article) are neither efficient nor algebraicly convenient. No one represents graphs as matrices in computer science, and graph theorists rarely touch representation theory. It's not that useful when the natural representations are normally much simpler and easier to work with.

rjtobin 10y ago
Not sure it's fair to say that graph theorists rarely use matrices to represent graphs: for many problems in graph theory some of the simplest solution involves representing the graph as a matrix (eg Hoffman-Singleton theorem).
ajamesm 10y ago
Oh, yes, we should definitely draw lessons from academic mathematicians about what is accessible and convenient to understand. THAT's a field that's never had a problem connecting to laymen.
- Retra 10y ago
  Hard to imagine doing anything interesting if you've got to appeal to laymen with every word.
GFK_of_xmaspast 10y ago
Meanwhile: http://epubs.siam.org/doi/book/10.1137/1.9780898719918 http://epubs.siam.org/doi/book/10.1137/1.9780898719918 https://www.cs.ucsb.edu/~gilbert/talks/GilbertGABB19May2014.pdf https://www.cs.ucsb.edu/~gilbert/talks/GilbertGABB19May2014.... http://graphblas.org/index.php/Graph_BLAS_Forum http://graphblas.org/index.php/Graph_BLAS_Forum http://www.netlib.org/utk/people/JackDongarra/PAPERS/GraphPrimitives-HPEC.pdf http://www.netlib.org/utk/people/JackDongarra/PAPERS/GraphPr... https://people.cs.clemson.edu/~isafro/na13/l12.pdf https://people.cs.clemson.edu/~isafro/na13/l12.pdf
JadeNB 10y ago
> No one represents graphs as matrices in computer science, and graph theorists rarely touch representation theory. Are you conflating linear algebra and representation theory, or did you really mean to refer to representation theory in particular? The notion of a quiver (https://en.wikipedia.org/wiki/Quiver_(mathematics) https://en.wikipedia.org/wiki/Quiver_(mathematics) ) seems to me to be a unification of the two fields; I'm not a graph theorist, but I have a hard time imagining that they don't at least consider these structures.