Matrix Multiplication O(nlgn) problems

rushel · Post by **rushel** » Sat Aug 05, 2006 11:08 am

Can somebody give us some very good problems where O(nlgn) matrix multiplication is needed.
Thanks

Per · Post by **Per** » 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?

Cosmin.ro · Post by **Cosmin.ro** » 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.

misof · Post by **misof** » Mon Aug 07, 2006 10:14 pm

And can that be done in O(n log n)?

chrismoh · Post by **chrismoh** » Tue Aug 08, 2006 1:28 pm

Yes, due to Hu and Shing.

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

Its a long paper.

misof · Post by **misof** » 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!