Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Graph Theory and Linear Algebra [pdf]

math.utah.edu

Post reply on HN
Print view View original

11–20 of 40 posts

Re: Graph Theory and Linear Algebra [pdf]

#11

Post by orange3xchicken »

aghilmort wrote: post #8

awesome - spent couple of years deep in this space for dissertation using graph theory to boost linear algebra computes; lots of room to extend our discrete result into approximate / continuous computes and boost AI, GPUs, etc. similar result came out around the same time using category theory as basis; our work was intentionally simpler / more applied, partly to make it more accessible from an algorithmic perspectiv…

That's really cool. These days similar strategies based on graph coarsening and vertex ordering are really popular for improving the sparsity pattern of preconditioners- e.g. incomplete lu decompositions for iterative linear solvers.

Re: Graph Theory and Linear Algebra [pdf]

#12

Post by activatedgeek »

A question for the more informed:

"What are recent developments in linear algebra?"

Perhaps, we can broaden the scope and include numerical/randomized linear algebra.

I come from a machine learning background, and the most recent directions I am aware of are in applications of Krylov subspace methods to very large number of data points and low-precision training (both in the context of Gaussian processes).

Re: Graph Theory and Linear Algebra [pdf]

#13

Post by WoahNoun »

activatedgeek wrote: post #12

A question for the more informed: "What are recent developments in linear algebra?" Perhaps, we can broaden the scope and include numerical/randomized linear algebra. I come from a machine learning background, and the most recent directions I am aware of are in applications of Krylov subspace methods to very large number of data points and low-precision training (both in the context of Gaussian processes).

Depends on how you define "linear algebra." Representation theory, lie groups, and grassmannians can all be considered "linear algebra" and are active areas of math research, but it probably isn't what you are looking for.

Re: Graph Theory and Linear Algebra [pdf]

#14

Post by hwers »

dpflan wrote: post #2

Perhaps I was wrong to expect mention of explicit discsussion of spectral graph theory? Anyway, always interesting topics to me. On a related note: Gilbert Strang (MIT) has a relatively new class in the area of Linear Algebra (of course!) and learning: from data: "Matrix Methods in Data Analysis, Signal Processing, and Machine Learning" > https://ocw.mit.edu/courses/mathematics/18-065-matrix-method... With Part IV: S…

The laplacian of a matrix also has cool applications in computer graphics, if anyone is curious (about further connections). Think of the mesh of an object as a graph and compute the lapacian. (You get natural unsupervised segmentations of the mesh for instance if you look at it as a spectral clustering problem.) Look up resources by Keenan Crane. If you've played with 'smooth normals' in blender I believe it uses techniques like that as well.

Re: Graph Theory and Linear Algebra [pdf]

#15

Post by vermarish »

I opened this pdf expecting to see a section on total unimodularity (TU).

For example, if an undirected graph is bipartite, its node-edge incidence matrix is TU. Any linear program operating on a TU matrix is guaranteed to have an integer solution. This means that any integer program can be relaxed to a linear program. Thus, the problems of bipartite matching and maximum flow can be easily solved using Simplex.

Some of the interesting results are described here: https://en.wikipedia.org/wiki/Unimodular_matrix#Examples_of_...

That wikipedia page does not do a great job at presenting the optimization connection. These slides are better: http://eaton.math.rpi.edu/faculty/Mitchell/courses/matp6620/...

Re: Graph Theory and Linear Algebra [pdf]

#16

Post by Py-o7 »

actually_a_dog wrote: post #10
enriquto wrote: post #7

Earlier quoted context omitted.

> Among other things, almost all trees are cospectral This does not really mean that the spectrum is not interesting, does it? Only that all trees have nearly the same spectrum. Sure, there's not much variability inside the class of trees, but almost no graphs are trees. After all, the matrix associated to a tree is basically a permutation of the identity.

You're right, of course. I should have said that the spectrum isn't all that useful for telling two graphs of the same order apart. Certain eigenvalues are frequently useful by themselves ( e.g. the largest, second largest, and smallest eigenvalues often contain some information). But, speaking of information, consider this: the adjacency matrix of a simple, loopless graph of order n is a symmetric n x n matrix with…

I don't understand why you are linking to something about labelled graphs when people are (presumably) trying to distinguish between graphs up to isomorphism i.e. after modd'ing out the labeling.

Re: Graph Theory and Linear Algebra [pdf]

#18

Post by activatedgeek »

WoahNoun wrote: post #13
activatedgeek wrote: post #12

A question for the more informed: "What are recent developments in linear algebra?" Perhaps, we can broaden the scope and include numerical/randomized linear algebra. I come from a machine learning background, and the most recent directions I am aware of are in applications of Krylov subspace methods to very large number of data points and low-precision training (both in the context of Gaussian processes).

Depends on how you define "linear algebra." Representation theory, lie groups, and grassmannians can all be considered "linear algebra" and are active areas of math research, but it probably isn't what you are looking for.

Fair enough.

I don't quite care about obscure and beautiful theoretical problems. I am looking for new developments that have shown promise to make big practical impact.

For what it's worth, I am no linear algebra definition police so feel free to list what you think is reasonably relevant.

Re: Graph Theory and Linear Algebra [pdf]

#20

Post by aghilmort »

orange3xchicken wrote: post #11
aghilmort wrote: post #8

awesome - spent couple of years deep in this space for dissertation using graph theory to boost linear algebra computes; lots of room to extend our discrete result into approximate / continuous computes and boost AI, GPUs, etc. similar result came out around the same time using category theory as basis; our work was intentionally simpler / more applied, partly to make it more accessible from an algorithmic perspectiv…

That's really cool. These days similar strategies based on graph coarsening and vertex ordering are really popular for improving the sparsity pattern of preconditioners- e.g. incomplete lu decompositions for iterative linear solvers.

yeah, there's so much room to extend this work in terms of graph coarsening / sparsifying, especially for progressive / approximate approaches

there's lots of overlap with entropy binning as well and likely some sort of combo for win -- figure out "max frequency" with some sort of FFT / wavelet like meta technique or somehow bin edges based on entropy contribution, etc.

or, lots of pathways to make coontinuous / numerical in JPEG like way

basically JPEGs for graphs -- with big impacts in AI / ML computes

Post reply on HN