Matrix Multiplication O(nlgn) problems

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Matrix Multiplication O(nlgn) problems

Post by rushel »

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

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

Matrix multiplication can not be done in O(n log n). Perhaps you are thinking of polynomial multiplication?

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post 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.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

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

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA

Post by chrismoh »

Yes, due to Hu and Shing.

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

Its a long paper.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post 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!

Post Reply

Return to “Algorithms”