<p>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. </p>

<p>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.</p>

CC BY-SA 4.0
2021-04-22T09:55:52.047Z
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?
Mengfan Ma
CC BY-SA 4.0
2021-04-22T19:12:04.613Z
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.
Ryan Williams
CC BY-SA 4.0
2021-04-23T04:18:33.800Z
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?
Mengfan Ma
CC BY-SA 2.5
2010-11-27T18:25:29.470Z
2010-11-27T18:25:29.470Z
Ryan Williams
<p>I was searching about Matrix multiplication, So I first visit <a href="http://en.wikipedia.org/wiki/Matrix_multiplication" rel="noreferrer">wiki</a> matrix multiplication algorithms, In references I found a paper which claim that uses <a href="http://www.cs.ncl.ac.uk/publications/trs/papers/1169.pdf" rel="noreferrer">$O(n^2 log(n))$ algorithm</a> , 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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-03-31T17:40:35.877Z
invitation to everyone interested/qualified to freely discuss/analyze the paper on [area51](http://discuss.area51.stackexchange.com/questions/13925/on-on2-log-n-algorithms-for-nn-matrix-operation-tcs-paper-review) or in [chat]. also suggest emailing Brian Randell who wrote the introduction & was apparently instrumental in publishing it posthumously.
vzn
CC BY-SA 3.0
2014-04-03T20:21:51.530Z
re the Eve work. it seems like a lot of sophisticated analysis and maybe some of it is wrong as suggested by Knuth (re RWs answer below), but it seems some shame to let it molder. are any experts looking at it? does it have any redeeming value? presumably there could be something salvagable by an expert in all the analysis even if some part of it is wrong, its on a key/premiere problem & it seems distasteful that experts would avoid looking at it entirely. also there are other papers linking multiplication complexity & group theory...
vzn
CC BY-SA 2.5
2010-11-27T16:18:07.790Z
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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-27T16:31:50.460Z
@Tsuyoshi Ito, I was Searching for parallel, I have a Quinn book on parallel algorithms, and in there I can see the `Dekel, Nassimi, and Sahni` algorithm (I didn't read it yet) which is O(log(n)), but I think if this is true, there is an algorithm with O(n^2 log(n)), If I going to make some modification on it, It can be useful for parallel algorithm, I read a little the paper, In the paper assumes n = p^t where `p` is prime and then ..., How you are sure there is no O(n^2 log(n)) algorithm, I was sure before seeing this but not right now.
Saeed
CC BY-SA 2.5
2010-11-27T16:36:13.637Z
@Tsuyoshi Ito, I didn't read your last sentence, `O(log(n)) is standard`? What the `standard` means? there is no algorithm with better performance? there is a mathematical reason, So if is I should to learn it.
Saeed
CC BY-SA 2.5
2010-11-27T16:51:13.063Z
(1) Please distinguish sequential time and parallel time.  (2) I did not say that sequential time O(n^2 log n) is impossible.  I just said such algorithms are not known.  I do not know how you came to think that the paper by Eve showed such an algorithm.  The author did not claim that he found such an algorithm.  (more)
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-27T16:52:09.007Z
(cont’d)  (3) What I meant by a standard parallel algorithm with O(log n) parallel time is in the model where every node can communicate to every node in a constant time, which was traditional in complexity theory in older time but turned out not to be practical.  My apologies for confusion.  I do not know about other parallel matrix multiplication algorithms, (and as you know, there are many more practical parallel algorithms for matrix multiplication).
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-27T16:58:35.723Z
@Tsuyoshi Ito, I'm not expert in parallel algorithms, I think first is better to read the `Dekel` algorithm and then think about improvement or other paradigms, but my current question is about sequential. thanks.
Saeed
CC BY-SA 2.5
2010-11-27T17:03:08.220Z
(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.)
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-27T17:06:08.573Z
I will delete the tag, at last I want to go throw quantum computing, but first I'll try to find some thing good in sequential, (and in parallel) I'll going to read the related articles, next if My base question exist I'll going to ask it in another thread.
Saeed
CC BY-SA 2.5
2010-11-27T17:21:43.147Z
I'd recommend you delete this question first then, and then repost later if you find that you do have a question.
Suresh Venkat
CC BY-SA 2.5
2010-11-27T18:46:41.613Z
@Suresh vankat, I have a question, I want to see is it true or not, how you find I have no question? I gonna read this article, so It's better to know about correctness of this before reading. and if it's not useful left it.
Saeed
CC BY-SA 2.5
2010-11-27T19:18:28.517Z
Voting to close as discussions on correctness of papers which are not peer-reviewed are off-topic.
Kaveh
CC BY-SA 2.5
2010-11-27T19:30:05.583Z
@Kaveh, It's your idea, I think this site should be a place for using others knowledge, this paper is heavy (for me) so my review takes long time, so i decide to gather other information about it, If you like to close it, It's not important to me. you and your friend can manage site in a way you like instead of scientific and logical, and It's not important to me, If you do it like your downvotes, I'll going to quit this non logical site. It's not an academic and scientific manner.
Saeed
CC BY-SA 2.5
2010-11-27T19:37:07.540Z
@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.)
Kaveh
CC BY-SA 2.5
2010-11-27T19:42:49.907Z
Related discussion on Meta: [Is it ok to ask about the correctness of preprints on crank-friendly topics?](http://meta.cstheory.stackexchange.com/questions/274/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.
Tsuyoshi Ito
<ds.algorithms><linear-algebra><matrix-product>
Matrix multiplication in $O(n^2 \log n)$
Saeed
# Matrix multiplication in $O(n^2 \log n)$

(Asked by: username_0 on 2010-11-27)

I was searching about Matrix multiplication, So I first visit [wiki](http://en.wikipedia.org/wiki/Matrix_multiplication) matrix multiplication algorithms, In references I found a paper which claim that uses [$O(n^2 log(n))$ algorithm](http://www.cs.ncl.ac.uk/publications/trs/papers/1169.pdf) , 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.

**Tags:** ds.algorithms, linear-algebra, matrix-product
> **Comments:**
> **username_2**: 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.  
> **username_0**: @Tsuyoshi Ito, I was Searching for parallel, I have a Quinn book on parallel algorithms, and in there I can see the `Dekel, Nassimi, and Sahni` algorithm (I didn't read it yet) which is O(log(n)), but I think if this is true, there is an algorithm with O(n^2 log(n)), If I going to make some modification on it, It can be useful for parallel algorithm, I read a little the paper, In the paper assumes n = p^t where `p` is prime and then ..., How you are sure there is no O(n^2 log(n)) algorithm, I was sure before seeing this but not right now.  
> **username_0**: @Tsuyoshi Ito, I didn't read your last sentence, `O(log(n)) is standard`? What the `standard` means? there is no algorithm with better performance? there is a mathematical reason, So if is I should to learn it.  
> **username_2**: (1) Please distinguish sequential time and parallel time.  (2) I did not say that sequential time O(n^2 log n) is impossible.  I just said such algorithms are not known.  I do not know how you came to think that the paper by Eve showed such an algorithm.  The author did not claim that he found such an algorithm.  (more)  
> **username_2**: (cont’d)  (3) What I meant by a standard parallel algorithm with O(log n) parallel time is in the model where every node can communicate to every node in a constant time, which was traditional in complexity theory in older time but turned out not to be practical.  My apologies for confusion.  I do not know about other parallel matrix multiplication algorithms, (and as you know, there are many more practical parallel algorithms for matrix multiplication).  
> **username_0**: @Tsuyoshi Ito, I'm not expert in parallel algorithms, I think first is better to read the `Dekel` algorithm and then think about improvement or other paradigms, but my current question is about sequential. thanks.  
> **username_2**: (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.)  
> **username_0**: I will delete the tag, at last I want to go throw quantum computing, but first I'll try to find some thing good in sequential, (and in parallel) I'll going to read the related articles, next if My base question exist I'll going to ask it in another thread.  
> **username_3**: I'd recommend you delete this question first then, and then repost later if you find that you do have a question.  
> **username_0**: @Suresh vankat, I have a question, I want to see is it true or not, how you find I have no question? I gonna read this article, so It's better to know about correctness of this before reading. and if it's not useful left it.  
> **username_4**: Voting to close as discussions on correctness of papers which are not peer-reviewed are off-topic.  
> **username_0**: @Kaveh, It's your idea, I think this site should be a place for using others knowledge, this paper is heavy (for me) so my review takes long time, so i decide to gather other information about it, If you like to close it, It's not important to me. you and your friend can manage site in a way you like instead of scientific and logical, and It's not important to me, If you do it like your downvotes, I'll going to quit this non logical site. It's not an academic and scientific manner.  
> **username_4**: @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.)  
> **username_2**: Related discussion on Meta: [Is it ok to ask about the correctness of preprints on crank-friendly topics?](http://meta.cstheory.stackexchange.com/questions/274/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.  
> **username_1**: invitation to everyone interested/qualified to freely discuss/analyze the paper on [area51](http://discuss.area51.stackexchange.com/questions/13925/on-on2-log-n-algorithms-for-nn-matrix-operation-tcs-paper-review) or in [chat]. also suggest emailing Brian Randell who wrote the introduction & was apparently instrumental in publishing it posthumously.  
> **username_1**: re the Eve work. it seems like a lot of sophisticated analysis and maybe some of it is wrong as suggested by Knuth (re RWs answer below), but it seems some shame to let it molder. are any experts looking at it? does it have any redeeming value? presumably there could be something salvagable by an expert in all the analysis even if some part of it is wrong, its on a key/premiere problem & it seems distasteful that experts would avoid looking at it entirely. also there are other papers linking multiplication complexity & group theory...  

---

## 1 answers

### Answer by username_5 on 2010-11-27. Score: 36 | Accepted answer

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.

> **Comments:**
> **username_6**: 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?  
> **username_5**: 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.  
> **username_6**: 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?  

---

