Group theory and matrix multiplication

Posted by James Lee on October 26, 2009

I mentioned in class that there was a group-theoretic approach to matrix multiplication in $O(n^{2+\varepsilon})$ -time developed by Cohn and Umans. This followup paper is able to obtain an $O(n^{2.41})$ -time algorithm using the Cohn-Umans framework.

Like this:

Be the first to like this post.

This entry was posted on October 26, 2009 at 7:55 pm and is filed under Extraneous. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply Cancel reply

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out / Change )

You are commenting using your Twitter account. ( Log Out / Change )

You are commenting using your Facebook account. ( Log Out / Change )

Cancel

Connecting to %s

« Homework #3: Greedy Algorithms

Homework #4 »

Design and Analysis of Algorithms

CSE 421, Autumn 2009, University of Washington

External Resources

Past incarnations

Mailing list archives

Anonymous feedback

Academic calendar

Related Material

UIUC course

DPV book

Recent Comments

Recent Posts

Blogroll

Subscribe

Categories