What is...the Complexity of Matrix Multiplication?

This page hosts information on Pierre Lairez' talk "What is … the Complexity of Matrix Multiplication?" at the "What is …?" seminar. The talk will take place on Friday, April 24, 1:00pm at the BMS Loft at Urania. This talk will help you better understand the talk by Peter Bürgisser, which will start at 2pm.

Abstract

Studies in computer algebra led to numerous efficient algorithms to solve many kinds of difficult problems (e.g., large integer multiplication). Complexity theory focuses on problems for which an efficient solution is not known and tries to grasp the intrinsic difficulty of problems. This involves both searching for lower bounds and upper bounds. Matrix multiplication is one of these hard problems. The obvious algorithm needs n^3 scalar multiplications to multiply two n by n matrices, and it is far from optimal. Simple methods and sophisticated tools allow to lower this bound, but it seems likely that we are still not close to optimal.

Comments