UCL  IRIS
Institutional Research Information Service
UCL Logo
Please report any queries concerning the funding data grouped in the sections named "Externally Awarded" or "Internally Disbursed" (shown on the profile page) to your Research Finance Administrator. Your can find your Research Finance Administrator at http://www.ucl.ac.uk/finance/research/post_award/post_award_contacts.php by entering your department
Please report any queries concerning the student data shown on the profile page to:

Email: portico-services@ucl.ac.uk

Help Desk: http://www.ucl.ac.uk/ras/portico/helpdesk
Publication Detail
A New General-Purpose Method to Multiply 3x3 Matrices Using Only 23 Multiplications
  • Publication Type:
    Report
  • Authors:
    COURTOIS N, Bard GV, Hulme D
  • publication date:
    14/08/2011
  • Place of publication:
    USA
  • Report number:
    http://arxiv.org/abs/1108.2830
  • Status:
    Published
  • Commisioning body:
    arxiv
  • Keywords:
    Linear Algebra, Fast Matrix Multiplication, Strassen's algorithm, Laderman's Method, Tensor Rank, Multiplicative Complexity
Abstract
One of the most famous conjectures in computer algebra is that matrix multiplication might be feasible in nearly quadratic time. The best known exponent is 2.376, due to Coppersmith and Winograd. Many attempts to solve this problems in the literature work by solving, fixed-size problems and then apply the solution recursively. This leads to pure combinatorial optimisation problems with fixed size. These problems are very hard and are unlikely to be solvable in polynomial time. In 1976 Laderman published a method to multiply two 3x3 matrices using only 23 multiplications. This result is non-commutative, and therefore can be applied recursively to smaller sub-matrices. In 35 years nobody was able to do better and it remains an open problem if this can be done with 22 multiplications. We proceed by solving the so called Brent equations. We have implemented a method to converting this very hard problem to a SAT problem, and we have attempted to solve it, with our portfolio of some 500 SAT solvers. With this new method we were able to produce new solutions to the Laderman's problem. We present a new fully general non-commutative solution with 23 multiplications and show that this solution is new and is NOT equivalent to any previously known solution. This result demonstrates that the space of solutions to Laderman's problem is larger than expected, and therefore it becomes now more plausible that a solution with 22 multiplications exists. If it exists, we might be able to find it just by running our algorithms longer, or due to further improvements in the SAT solver algorithms.
Publication data is maintained in RPS. Visit https://rps.ucl.ac.uk
 More search options
UCL Researchers
Author
Dept of Computer Science
University College London - Gower Street - London - WC1E 6BT Tel:+44 (0)20 7679 2000

© UCL 1999–2011

Search by