Page 1 of 1

Matrix Multiplication O(nlgn) problems

Posted: Sat Aug 05, 2006 11:08 am
by rushel
Can somebody give us some very good problems where O(nlgn) matrix multiplication is needed.
Thanks

Posted: Sun Aug 06, 2006 9:58 pm
by Per
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
by Cosmin.ro
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
by misof
And can that be done in O(n log n)? :)

Posted: Tue Aug 08, 2006 1:28 pm
by chrismoh
Yes, due to Hu and Shing.

http://historical.ncstrl.org/litesite-d ... 81-875.pdf

Its a long paper.

Posted: Tue Aug 08, 2006 8:30 pm
by misof
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!