Entry tags:
multiplication algorithms
Today, after theory lunch, I got an impromptu, 5-minute private lesson from Daniel Sleator (of splay-tree fame), on fast matrix multiplication.
I was surprised to learn that you can do better than O(n^3) in the worst case, in general. FWIU, Volker Strassen was the first one to propose make an improvement, sometime in the 60's.
If you want to multiply a pair of 2x2 matrices, you would ordinarily do 8 multiplications (the result matrix has 4 entries, each with 2 terms). But it's possible to do it with 7: basically you multiply sums of matrices, and add to the results of other multiplications to get what you need.
If you're using such a divide-and-conquer approach, the fundamental (information-theoretic?) bound is: how many multiplications are necessary to form a basis from which to compute our answer?
To illustrate with a simpler example, imagine you have two 10-digit binary numbers, x and y. To do the divide-and-conquer, we split each of them into two halves.
Let x = [01010|00111] = [a | b]
In decimal, x = 2^5 a + b
Likewise, y = 2^5 c + d
x*y is going to be a 20-digit number:
x*y = 2^10ac + 2^5 (ad+bc) + bd (note that we can compute the last 5 digits of x*y from b and d alone)
So it looks like we need 4 multiplications: a*c, a*d, b*c, b*d.
But in fact, if we do (a+b)*(c+d) = ac+ad+bc+bd
we don't need to multiply ad and bc, since they can be calculated using only additions with the above and ac and bd (3 multiplications).
At first sight, this may not seem like a very good deal, since additions cost the same as multiplications.
But the point is that somehow, this generalizes to matrix multiplications, whose complexity asymptotically dominates the complexity of matrix addition. Therefore, the fewer multiplications, the more efficient you are in the limit.
The complexity of matrix multiplication is O(n^omega). Omega today is around 2.3, which is what you get by solving a recurrence.
---
Given the kind of problem that this is, I'm surprised these algorithms aren't being discovered by computers. Going to these theory talks, and seeing clever (but hairy) tricks just keeps feeding my desire to automate the discovery of these theorems/algorithms.
The search for algorithms must constrain the hypothesis-space to algorithms that *might* possibly work (do there exist kinds of genetic programming where the search is constrained by logical constraints, like e.g. symmetry?). Given such a constrained search, some empirical testing may still be needed to "debug" the hypothesis, do some parameter-adjusting, etc.
Also, there's no reason we can't feed it some background knowledge that human computer scientists benefit from. For instance, I would to formalize strategies like "divide-and-conquer". It's an interesting problem how to make such a general idea applicable to different kinds of representations / data-structures.
As a cognitive AI person, I feel like it's my duty to relieve mathematicians from the burden of thinking. But in my experience, theory people don't like to hear this.
I was surprised to learn that you can do better than O(n^3) in the worst case, in general. FWIU, Volker Strassen was the first one to propose make an improvement, sometime in the 60's.
If you want to multiply a pair of 2x2 matrices, you would ordinarily do 8 multiplications (the result matrix has 4 entries, each with 2 terms). But it's possible to do it with 7: basically you multiply sums of matrices, and add to the results of other multiplications to get what you need.
If you're using such a divide-and-conquer approach, the fundamental (information-theoretic?) bound is: how many multiplications are necessary to form a basis from which to compute our answer?
To illustrate with a simpler example, imagine you have two 10-digit binary numbers, x and y. To do the divide-and-conquer, we split each of them into two halves.
Let x = [01010|00111] = [a | b]
In decimal, x = 2^5 a + b
Likewise, y = 2^5 c + d
x*y is going to be a 20-digit number:
x*y = 2^10ac + 2^5 (ad+bc) + bd (note that we can compute the last 5 digits of x*y from b and d alone)
So it looks like we need 4 multiplications: a*c, a*d, b*c, b*d.
But in fact, if we do (a+b)*(c+d) = ac+ad+bc+bd
we don't need to multiply ad and bc, since they can be calculated using only additions with the above and ac and bd (3 multiplications).
At first sight, this may not seem like a very good deal, since additions cost the same as multiplications.
But the point is that somehow, this generalizes to matrix multiplications, whose complexity asymptotically dominates the complexity of matrix addition. Therefore, the fewer multiplications, the more efficient you are in the limit.
The complexity of matrix multiplication is O(n^omega). Omega today is around 2.3, which is what you get by solving a recurrence.
---
Given the kind of problem that this is, I'm surprised these algorithms aren't being discovered by computers. Going to these theory talks, and seeing clever (but hairy) tricks just keeps feeding my desire to automate the discovery of these theorems/algorithms.
The search for algorithms must constrain the hypothesis-space to algorithms that *might* possibly work (do there exist kinds of genetic programming where the search is constrained by logical constraints, like e.g. symmetry?). Given such a constrained search, some empirical testing may still be needed to "debug" the hypothesis, do some parameter-adjusting, etc.
Also, there's no reason we can't feed it some background knowledge that human computer scientists benefit from. For instance, I would to formalize strategies like "divide-and-conquer". It's an interesting problem how to make such a general idea applicable to different kinds of representations / data-structures.
As a cognitive AI person, I feel like it's my duty to relieve mathematicians from the burden of thinking. But in my experience, theory people don't like to hear this.