dc.contributor.advisor Davie, Alexander en dc.contributor.advisor Gyongy, Istvan en dc.contributor.author Stothers, Andrew James en dc.date.accessioned 2011-02-01T10:14:31Z dc.date.available 2011-02-01T10:14:31Z dc.date.issued 2010 dc.identifier.uri http://hdl.handle.net/1842/4734 dc.description.abstract The evaluation of the product of two matrices can be very computationally expensive. en 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. dc.contributor.sponsor Engineering and Physical Sciences Research Council (EPSRC) en dc.language.iso en dc.publisher The University of Edinburgh en dc.subject algebra en dc.subject complexity en dc.subject maxtrix en dc.subject rank en dc.subject Coppersmith en dc.subject Winograd en dc.subject algorithm en dc.subject Salem-Spencer en dc.title On the complexity of matrix multiplication en dc.type Thesis or Dissertation en dc.type.qualificationlevel Doctoral en dc.type.qualificationname PhD Doctor of Philosophy en
﻿