| dc.description.abstract | The evaluation of the product of two matrices can be very computationally expensive.
The multiplication of two n×n matrices, using the “default” algorithm can take O(n3)
field operations in the underlying field k. It is therefore desirable to find algorithms to
reduce the “cost” of multiplying two matrices together. If multiplication of two n × n
matrices can be obtained in O(nα) operations, the least upper bound for α is called
the exponent of matrix multiplication and is denoted by ω.
A bound for ω < 3 was found in 1968 by Strassen in his algorithm. He found
that multiplication of two 2 × 2 matrices could be obtained in 7 multiplications in the
underlying field k, as opposed to the 8 required to do the same multiplication previously.
Using recursion, we are able to show that ω ≤ log2 7 < 2.8074, which is better than the
value of 3 we had previously.
In chapter 1, we look at various techniques that have been found for reducing
ω. These include Pan’s Trilinear Aggregation, Bini’s Border Rank and Sch¨onhage’s
Asymptotic Sum inequality.
In chapter 2, we look in detail at the current best estimate of ω found by Coppersmith
and Winograd. We also propose a different method of evaluating the “value” of
trilinear forms.
Chapters 3 and 4 build on the work of Coppersmith and Winograd and examine how
cubing and raising to the fourth power of Coppersmith and Winograd’s “complicated”
algorithm affect the value of ω, if at all.
Finally, in chapter 5, we look at the Group-Theoretic context proposed by Cohn
and Umans, and see how we can derive some of Coppersmith and Winograd’s values
using this method, as well as showing how working in this context can perhaps be more
conducive to showing ω = 2. | en |
