14
$\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$
16
  • 5
    $\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$ Commented Nov 27, 2010 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$ Commented Nov 27, 2010 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$ Commented Nov 27, 2010 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
    Commented Nov 27, 2010 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$ Commented Nov 27, 2010 at 19:42

1 Answer 1

36
$\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$
3
  • $\begingroup$ In the newest version of this paper in arxiv.org/abs/1612.04208, the author claims to find an $O(n^2\log^c{n})$ algorithm for matrix multiplication. Have you ever read it? Is it correct? $\endgroup$
    – Mengfan Ma
    Commented Apr 22, 2021 at 9:55
  • 1
    $\begingroup$ I have not read the latest version. But I see there are 15 posted revisions of the paper over a span of 4 years, each of which claim to have fixed the errors in previous revisions. It seems unlikely that the 16th one is finally the correct one. But I encourage any interested students with spare time and enthusiasm to read it to find the error and report it. $\endgroup$ Commented Apr 22, 2021 at 19:12
  • $\begingroup$ I'm trying to figure it out. I'd like to know what's the prerequisite knowledge needed to understand this paper? I have some basics in algebra and algorithm design, do you think it's enough? $\endgroup$
    – Mengfan Ma
    Commented Apr 23, 2021 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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