I've always found the bipartite graph conceptualization of matrix multiplication the most intuitive, and especially so if you're familiar with neural networks: https://www.math3ma.com/blog/matrices-probability-graphs
[deleted]
A Programmer’s Intuition for Matrix Multiplication
31–40 of 95 posts
Re: A Programmer’s Intuition for Matrix Multiplication
#32Earlier quoted context omitted.
Today I learned! I'm fairly familiar with "regular" spectral analysis techniques, ie FFTs and DCTs, with some CWT waveletty goodness thrown in here and there but I never heard about spectral graph analysis. That's what you get for staying in EE land too long I guess.
Fourier & Friends are excellent analytical tools for the nature of patterns, regardless of where they occur! In EE-land we think too much about real and complex numbers, where Fourier analysis is more concrete. But spectral graph theory makes a lot of sense when you think of Fourier analysis as a way of decomposing patterns into their constituent parts, it just looks a bit funny when those patterns aren't numbers.
Indeed. By using tools of linear algebra on the adjacency matrices of a graph, you can tell a lot about the structure of the graph.
For instance, if A is the adjacency matrix of a graph G, with n vertices (we say 'vertices' in the math department almost exclusively -- rarely do we say 'nodes'), and k edges, denoting the trace of A by Tr(A), we can find the number of triangles in A by computing Tr(A^3)/6. We can also tell if G is connected by computing A^n. [0]
OTOH, the spectrum doesn't tell you nearly everything you'd want to know about a graph. There are many examples of non-isomorphic graphs that are nonetheless cospectral. For instance, one of my professors from grad school wrote a landmark paper in spectral graph theory in 1973, showing that almost all trees are cospectral. [1]
---
[0]: Of course, you'd probably never actually do this, because it's horribly inefficient, but here's how it goes.
First, you prove easily by induction that A^c_{i,j} is the number of paths of length c starting at vertex i and ending at vertex j. With that in mind, we see that if there is a row of all nonzero numbers in any matrix A^c for c [1]: Unsurprisingly, the paper is titled "Almost all trees are cospectral". See: https://www.semanticscholar.org/paper/Almost-all-trees-are-c...
Re: A Programmer’s Intuition for Matrix Multiplication
#33This comes up occasionally. I don't find it to be particularly helpful, even though I do think betterexplained has been a strong source of gaining intuition into various subjects.
Recognizing though that method of understanding something is pretty personal, I will say that what really helped me refresh was the 3Blue1Brown Essence of Linear Algebra series on Youtube. If you're trying to better grasp the subject, do yourself a favor and check out those videos.
Re: A Programmer’s Intuition for Matrix Multiplication
#34Earlier quoted context omitted.
Purist test: aren't vectors just Nx1 matrices? Joking aside, matrices are linear maps in the context of multiplication. They can absolutely have meanings assigned outside the usual "when multiplied by a vector" type of calculations. For example the "adjacency matrix" representation of a graph is very often never multiplied by a vector even in academic algorithm descriptions. YMMV if you call it a (lookup) table in th…
> aren't vectors just Nx1 matrices? It's been a while since I formally studied maths, but - can you describe a situation in which this is _not_ true? (modulo transposition)
In an N dimensional vector space, yes, you can always choose a basis and write vectors down that way, but it turns out to often be a bad way to work. For example, picture a surface. At any point on the surface, there is a plane of vectors tangent to that surface. It's unnatural to describe the vectors there in terms of a 2x1 matrix, since that requires the choice of a basis of the tangent space. And if you try to choose a basis of the tangent space, you'd probably want it to vary continuously from one point on the surface to the next, but that's not possible to do on many surfaces, such as a sphere, thanks to the Hairy Ball Theorem. [1]
Re: A Programmer’s Intuition for Matrix Multiplication
#35I wholehearted endorse 3B1B, The linear algebra series is excellent, the rest of his work is too!
Re: A Programmer’s Intuition for Matrix Multiplication
#36Matrix multiplication is like convolution.
To be sure there isn't a perspective here that I may be unaware of, is this a reference to circulant matrices, which bear the Toeplitz sparsity structure?
Re: A Programmer’s Intuition for Matrix Multiplication
#37In some applications, e.g. modelling something defined by PDE, you might need to solve a very large linear system of equations Ax=b, where the vector b has 100,000,000 elements, and A is a 100,000,000 by 100,000,000 element matrix. So for a naive dense matrix representation of A using 1 byte per entry you'd need around 9 petabytes of storage. In practise, for many interesting systems of equations that encode "local"…
And what happens if indeed the huge matrix elements are all non-zero? Like, let's say, satellite scan data for a given country when you want to spy on their underground systems (think North Korea facilities)? Wouldn't storing that data as COO would actually triple the amount of memory?
[deleted]
Re: A Programmer’s Intuition for Matrix Multiplication
#38In some applications, e.g. modelling something defined by PDE, you might need to solve a very large linear system of equations Ax=b, where the vector b has 100,000,000 elements, and A is a 100,000,000 by 100,000,000 element matrix. So for a naive dense matrix representation of A using 1 byte per entry you'd need around 9 petabytes of storage. In practise, for many interesting systems of equations that encode "local"…
For the more machine learning-minded folks, this happens almost always in doing inference with Exact Gaussian Processes (GP), where because of the non-parametric nature of a GP model, the covariance matrix grows with the size of data points. The inference routine is cubic in the number of data points. Hence, sparsity in the posited covariance matrix is _extremely_ important for fast inference.
Re: A Programmer’s Intuition for Matrix Multiplication
#39Earlier quoted context omitted.
> Purist test The short answer is. Yes, but if your PL treats it that way you will wind up in trouble [0]. The long answer is: https://www.youtube.com/watch?v=C2RO34b_oPM (but seriously take the time to watch this, it's fantastic). [0] Separately C- and often C-derived languages/frameworks like numpy also treat them as 1xN matrices, but that's a nearly tabs-vs-spaces level religious war, with actual consequences. I t…
Besides needing to change the order of multiplication (y = xM vs y = Mx) and use the right transposition of the matrix, do any other actual consequences come from the choice of "row vector" vs "column vector"?
Mathematically speaking, no. They are isomorphic duals. But ergonomics are important to prevent errors. I personally think Matrix-in-front is nice because it evokes the idea that the matrix is a function acting on the vector.
In the real world, When you start doing matrix-vector, if you aren't careful with row-major vs column-major storage you can introduce performance regressions. Let's say the architecture can do 256 bit memory move into 4xf64 mmx registers, you have to think carefully about what is going where before proceeding. Some architectures might be able to do an arbitrary stride so that those f64s can be nonadjacent in a simultaneous move. I suspect not handling this correctly is part of what holds back really good fp8, fp16 performance, and I suspect for example the TPUs struggle with this.
Of course optimizing for matrix-vector can be different for optimizing for matrix-matrix, since the column vs row memory access preference for the front matrix is exactly the opposite of the back matrix.
Re: A Programmer’s Intuition for Matrix Multiplication
#40I'd prefer stating that matrices actually don't mean anything in isolation. They are simply representations of linear maps. What happens to the elements of a matrix before the elements are formed is irrelevant to the matrix itself. ..And to be clear, I am not a purist.
Purist test: aren't vectors just Nx1 matrices? Joking aside, matrices are linear maps in the context of multiplication. They can absolutely have meanings assigned outside the usual "when multiplied by a vector" type of calculations. For example the "adjacency matrix" representation of a graph is very often never multiplied by a vector even in academic algorithm descriptions. YMMV if you call it a (lookup) table in th…
I think if in any context one uses the usual matrix algebra, it is the same linear map, just in a more abstract setting.
If you tell me storing a lookup table is matrix, I think that is sort of out of context. But then again, I could be labelled a purist here, and I'm trying really hard to not fall into the trap.