Welcome to Geeks Portal Sign in | Join | Help
in
 
 

docx In Search Of Optimal Mathematics Algorithm

Downloads: 24 File Size: 37.5kB
Posted By: norman Views: 113
Date Added: 04-26-2008

In designing an algorithm for a mathematical concept, one may need to look beyond the definition of that mathematical concept in order to get an optimal algorithm. The complexity of an algorithm for a mathematical concept is not necessarily bounded by the complexity of brute-force algorithm as per its mathematical definition. This paper makes this exposition by using matrix multiplication as an example. Straight forward computation as per the definition of matrix multiplication is an algorithm with complexity . It is not optimal. By looking beyond the definition, Strassen could come up with algorithm which complexity is . Further efforts resulting the Coppersmith-Winograd algorithm which complexity is only . Later, Umans and Cohn, together with Kleinberg and Szegedy made two conjectures that either one would imply that the exponent of matrix multiplication is 2. Just like its lower bound.

Comments

No comments exist for this file.

Add Comment

(required) 
(required)
(optional)
(required) 

Enter the numbers above:
Add
 
 
Powered by Community Server (Commercial Edition), by Telligent Systems
Copyright © INDC, 2006. All rights reserved.