For the particular problem discussed in the original article, there are at least two ways the multiplication A'A could potentially be made faster:
1) The blas _GEMM matrix multiplication routine lets you specify whether input matrix arguments are supposed to be transposed. This gets rid of the explicit transposition, AND in this problem, it lets you compute each element as the dot product of two unit stride vectors, instead of a dot product of an unit stride vector with a nonunit stride vector. For SSE, this makes a huge difference.
2) For the particular case A'A, there is the even more specialized _SYRK routine, which at the very least should be cache friendlier than a naive _GEMM (_GEMM could also figure out that it can use _SYRK for this problem, and presumably it does so in some implementation)
I would also hazard a guess that the tuning that you mention does not involve a change in the algorithm but are essentially reordering the steps of the algorithm to obtain better caching. I was responding to the parent post which conjectured that BLAS implementations use different algorithms. If you look at your two suggestions, none of them actually change the complexity class of the number of floating operations, but wall clock time oh absolutely.
Although there are matrix multiplication algorithms that have a complexity less than O(N^3) the constants for these are so large enough that the sizes of matrices for which there will be any appreciable benefit are extremely rare to come by.
I havent looked at the actual code in a while, but from what I have seen they use the standard vanilla matrix multiplication algorithm whose complexity is no less than O(N^3) (for square matrices).
They achieve the speed by exploiting the deep cache structure of modern machines. Essentialy by blocking (sometimes unrolling) loops and consuming data in a cache aware fashion. Given the latency in accessing the data directly from memory, getting the data off the cache can easily speed things up by 10s if not 100s of folds.
In otherwords, its the same algorithm just implemented more efficiently.
On the other hand is the interesting question if linear algebra can be done fast in a lisp without calling BLAS. I do not have the reference on the top of my head but there were a few papers on ACM where it was shown that lisp can indeed rival fortran speed in linear algebraic computation. I will try and dig it up later. In anycase I suspect that stalin will do a decent job optimizing a matrix multiplication routine written in lisp. I suspect that a part of the slowdown in clojure is also because it runs on jvm whose safety guarantees (bounds checking and no reordering of instructions) can come with a speed hit.
EDIT: here it is http://www.cs.berkeley.edu/~fateman/papers/lispfloat.ps
From the abstract:
And the conclusion: Should be read with http://dl.acm.org/citation.cfm?id=235815.235824 (this is probably pay-walled).