### 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

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=22&t=11454

Page **1** of **1**

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

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!