13
$\begingroup$

I was searching about Matrix multiplication, So I first visit wiki matrix multiplication algorithms, In references I found a paper which claim that uses $O(n^2 log(n))$ algorithm , I'd going to read article but it's complicated and will takes too many time to read it, but if there is anyone who reads this article or knows about this algorithm, Is this true? and are you knowing about the base Idea of this to describe it a little.

Thanks in advance, I know it's a bit general question but, if I found it's good approach I'll going to learn details.

$\endgroup$
  • 4
    $\begingroup$ I think that it is useful to understand your own question better. Are you looking for a sequential algorithm or a parallel algorithm? No sequential algorithms for matrix multiplication with time O(n^2 log n) are known, and the paper by Eve is a partial result toward such algorithms (I did not read the paper, I just skimmed it). If you care about parallel time, then parallel time O(log n) (assuming scalar addition and scalar multiplication in constant time) is standard and you can find explanation in e.g. the book Computational Complexity by Papadimitriou. $\endgroup$ – Tsuyoshi Ito Nov 27 '10 at 16:18
  • 2
    $\begingroup$ (1) Please edit your question so that it is clear that you are asking about sequential algorithms. (2) I realized that you added the tag [quantum-computing]. Please edit your question to explain the relation to quantum computing. (My guess is that your question is motivated by quantum computing, but your own explanation is far more useful than any guess.) $\endgroup$ – Tsuyoshi Ito Nov 27 '10 at 17:03
  • 2
    $\begingroup$ I'd recommend you delete this question first then, and then repost later if you find that you do have a question. $\endgroup$ – Suresh Venkat Nov 27 '10 at 17:21
  • 3
    $\begingroup$ @Saeed: This issue has been discussed on the meta and currently this is the site's policy, if you want to discuss the policy use the meta. On the other hand, you can modify the question and avoid mentioning the paper to make it on-topic, e.g. modifying the question to become "what is the best known algorithm for matrix multiplication in model X?" and that would be on-topic. (side note: if you cannot verify correctness of an unpublished paper yourself and want to cite it, you should wait till it is peer-reviewed and published.) $\endgroup$ – Kaveh Nov 27 '10 at 19:37
  • 3
    $\begingroup$ Related discussion on Meta: Is it ok to ask about the correctness of preprints on crank-friendly topics? I am not claiming that everything written on that page will apply to this question, but it is at least closely related. $\endgroup$ – Tsuyoshi Ito Nov 27 '10 at 19:42
34
$\begingroup$

I came across this paper about a year ago, but have not gotten around to reading it closely. I can tell you that the approach is not believed to be correct. On page 36 of the same paper, there is an attached comment by Don Knuth, who points out what looks to be a serious shortcoming of the approach.

To understand this paper, you will need to learn about group algebra and representation theory. It will be tough if you haven't seen that kind of material before.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.