Hacker News Reader

Comment by cabinpark | Hacker News Reader

I would argue that almost every single linear algebra routine can be interpreted in some form as a matrix-matrix or matrix-vector multiplication. Considering that matrix-matrix and matrix-vector are fundamental numerical operations (they are part of BLAS which are the basic API functions called by every single linear algebra routine I know of) having a concise notation is key.

And since formulas can get complicated quickly, having a closer 1-1 correspondence with the mathematics is critical for understanding the meaning of the code. The PEP contains a nice example from statistics. And trust me, when you are writing numerical code, being able to read the mathematical formula clearly is essential, especially when you have a lot of formulas and need to figure out why your code is giving you numerical non-sense.

View on HN

>I would argue that almost every single linear algebra routine can be interpreted in some form as a matrix-matrix or matrix-vector multiplication.

It's not really necessary to argue. Cayley's theorem guarantees that every group is a subgroup of a symmetric group:

http://en.wikipedia.org/wiki/Cayley's_theorem

A symmetric group is then a subgroup of the general linear group in any field, where the general linear group GL(K, N) is the set of invertible NxN matrices with entries from a "field" (just think "numbers") and therefore any [finitely generated] group is isomorphic to a group of matrices under matrix multiplication; this is the underlying concept of representation theory.

If we back up a little, a group is a very general sort of algebraic structure; many important concepts have an underlying group structure, such as rotations, permutations, and any sort of reversible computation. This latter case implies that matrix multiplication is Turing complete; the simplest such set of matrices is generated by the Toffoli gate matrix. The relationship of groups to geometry is due to the underlying correspondence between the axioms of a group and those of geometrical transformations. A set of reversible geometric transformations includes an identity element -- do nothing -- and obeys associativity (sorta complicated, but it makes sense if you think about it) and inverse operations (by assumption): this makes it a group, and it can be represented by matrices. If we remove "reversible", we get exceptions -- like the cross product -- but these are usually related to groups (cross product -> quaternion algebra).

So matrix multiplication is actually really, really fundamental in a lot of mathematics. It's also a special case of tensor contraction, which could justify another tower post (but won't).

>And trust me, when you are writing numerical code, being able to read the mathematical formula clearly is essential, especially when you have a lot of formulas and need to figure out why your code is giving you numerical non-sense.

(spent three months chasing a bug where two commands were out of order)

> A symmetric group is then a subgroup of the general linear group in any field, where the general linear group GL(K, N) is the set of invertible NxN matrices with entries from a "field" (just think "numbers") and therefore any [finitely generated] group is isomorphic to a group of matrices under matrix multiplication; this is the underlying concept of representation theory.

As a representation theorist, I am very sympathetic to this point of view, but I'm not sure that it proves that "[almost] every single linear algebra routine can be interpreted as a matrix-matrix multiplication"—unless one first has some reduction from an arbitrary linear-algebra routine to a group action.

Also, as a very minor nitpick, I think that you want 'finite' instead of 'finitely generated'; even infinite groups embed in (infinite) symmetric groups, but it's not obvious to me that infinite symmetric groups embed in (finite-dimensional) matrix groups, and it's certainly not true (just by counting cardinality) that infinite but finitely generated groups embed in finite symmetric groups.

What you say about almost all linear algebra routines being multiplication sounds crazy to me. How are the following supposed to be multiplication: (1) computing the transpose, (2) finding a basis for the kernel of a matrix, (3) factorizations, such as QR, LU or SVD (3) computing the Jordan normal form of a matrix, etc.?

It's not as crazy as it sounds, though I wouldn't make such a blanket statement. Things can be phrased in terms of matrix multiplication (maybe not a single matrix multiplication), it's just not the most efficient way to go about it.

1. Transpose is a linear map on matrices (vectors in R^nm), so in a very concrete sense it is precisely a matrix multiplication. And it's not hard to figure out the matrix, because it's analogous to the matrix that swaps entries in vectors.

2. Finding the first eigenvalue can be approximated via matrix multiplication, and for sparse matrices with good spectral gap this extends to all of them.

3. Row reduction can be phrased as matrix multiplication, and hence finding the basis for the kernel of a matrix is a byproduct of it, as is computing eigenvectors when given eigenvalues.

4. Computing orthonormal basis is a sequence of projection operators (and all linear maps are matrix multiplications)

5. I'm pretty sure nobody computes the Jordan canonical form on computers.

The point is that the connection between matrices and linear maps is the spirit of linear algebra.

It is as crazy as it sounds because we were talking about implementing an actual language/library, not about doing the linear-algebra equivalent of restating Turing's thesis.

> not the most efficient way to go about it

understatement of the century.

> we were talking about implementing an actual language/library

No, we're talking about language-level syntactic standardization of the most fundamental computational concept in linear algebra (and I would argue all of mathematics). My list just gives evidence to how unifying the concept is.

If you want supercomputing-grade efficiency you won't stop using numpy/scipy just because of this update, or you've already rewritten your Python prototype in C/Fortran anyway.

> If you want supercomputing-grade efficiency you won't stop using numpy/scipy just because of this update

Especially since the update is just creating a language feature for numpy and similar libraries to leverage -- there is still no matrix implementation (and thus no matrix multiplication) in the standard library, just an overloadable operator so that numerical libraries can consistently use it for matrix multiplication and use * for elementwise multiplication, providing a standard API for those libraries.

Lots of factorizations such as the NMF can be implemented as a hill climb where you just multiply things against other things (and normalize elementwise)

Reply on news.ycombinator.com