Matrix Multiplication O(nlgn) problems
Posted: Sat Aug 05, 2006 11:08 am
Can somebody give us some very good problems where O(nlgn) matrix multiplication is needed.
Thanks
Thanks
OJ Board
The Online Judge board
https://onlinejudge.org/board/
Matrix Multiplication O(nlgn) problems
Page 1 of 1
Posted: Sun Aug 06, 2006 9:58 pm
Matrix multiplication can not be done in O(n log n). Perhaps you are thinking of polynomial multiplication?
Posted: Mon Aug 07, 2006 3:07 pm
I think he was referring to the problem of optimally using parenthesis so that evaluating a product of an array of matrices would finish in the minimal amount of time.
Posted: Mon Aug 07, 2006 10:14 pm
And can that be done in O(n log n)? 
Posted: Tue Aug 08, 2006 1:28 pm
Posted: Tue Aug 08, 2006 8:30 pm
We live to learn
I didn't know this result before. So far I only read the abstract, but it seems pretty interesting. I will surely read the entire article when I have the time. Thanks for the link!
I didn't know this result before. So far I only read the abstract, but it seems pretty interesting. I will surely read the entire article when I have the time. Thanks for the link!