Monday, July 9, 2007

Is there a way to multiply matrices in lesser than o(n^3) time complexity?

Yes. Divide and conquer method suggests Strassen's matrix multiplication method to be used. If we follow this method, the time complexity is O(n^2.81) times rather O(n^3) times.

Here are some more details about this method.

Suppose we want to multiply two matrices of size N x N: for example A x B = C


[C11 C12] [A11 A12] [B11 B12]
[C21 C22] = [A21 A22] [B21 B22]


Now, this guy called Strassen's somehow :) came up with a bunch of equations to calculate the 4 elements of the resultant matrix


C11 = a11*b11 + a12*b21
C12 = a11*b12 + a12*b22
C21 = a21*b11 + a22*b21
C22 = a21*b12 + a22*b22



If you are aware, the rudimentary matrix multiplication goes something like this


void matrix_mult()
{
for (i = 1; i <= N; i++)
{
for (j = 1; j <= N; j++)
{
compute Ci,j;
}
}
}


So, essentially, a 2x2 matrix multiplication can be accomplished using 8 multiplications. And the complexity becomes


2^log 8 =2^3


Strassen showed that 2x2 matrix multiplication can be accomplished in 7 multiplications and 18 additions or subtractions. So now the complexity becomes


2^log7 =2^2.807


This is how he did it


P1 = (A11+ A22)(B11+B22)
P2 = (A21 + A22) * B11
P3 = A11 * (B12 - B22)
P4 = A22 * (B21 - B11)
P5 = (A11 + A12) * B22
P6 = (A21 - A11) * (B11 + B12)
P7 = (A12 - A22) * (B21 + B22)

C11 = P1 + P4 - P5 + P7
C12 = P3 + P5
C21 = P2 + P4
C22 = P1 + P3 - P2 + P6


Now, there is no need to memorize this stuff!

52 comments:

Anonymous said...

get viagra watermelon viagra cost of viagra cheapest place to buy viagra online can viagra causes legs to ache viagra and alternatives viagra suppliers in the uk viagra 34434 viagra rrp australia cost splitting viagra viagra substitute legal viagra buy viagra cheap viagra online no prescription

Uttam Agrawal said...

Sample C Program To Accept A String & Display Number Of Vowels.

Sample C Program To Accept A String & Display Number Of Each Vowels.

Sample C Program To Accept A String & Find Out Whether This Character Is Present In The String.

Sample C Program To Find Out The No. Of Times A Character Is Present In The String.

Sample C Program To Understand Working Of Address Concept.

Sample C Program On Use Of Array & Pointer Concept Together.

Sample C Program On Pointers & 2 - Dimensional Array.

Sample C Program On Strings Into Array Of Pointers.

Sample C Program To Accept & Add Ten Numbers Using Pointers.

Sample C Program To Implement Recursive Algorithm Using Pointers.

Sample C Program With Algorithm To Implement Bubble Sort Using Pointers.

Sample C Program To Implement Selection Sort Using Pointers, Arrays & Functions.

sandeep kumar said...

Thanks for the info. It is very helpful.
RegardsEducational site
Get jobs info at Educational site

Anonymous said...

Thanks for sharing such a pleasant thought, piece of writing is good, thats why i have read it fully
My web blog :: Victoria _ Amateur Brunette Touching Her Tits And Masturbating Her Pussy Outdoor

Anonymous said...

Your style is so unique in comparison to
other people I have read stuff from. I appreciate you for posting when you've got the opportunity, Guess I will just book mark this web site.
My homepage ; Sexy blondy fucks with three guys

Anonymous said...

Normally I don't learn post on blogs, however I would like to say that this write-up very forced me to try and do so! Your writing taste has been amazed me. Thanks, quite great article.
My webpage ; drunk teens

Anonymous said...

Hey! This is my first comment here so I just wanted to give a quick shout out and say I really enjoy reading your blog posts.
Can you recommend any other blogs/websites/forums that
deal with the same topics? Thank you so much!
Here is my homepage : Hot Anal Action with Lucy Lee

Anonymous said...

Does your blog have a contact page? I'm having a tough time locating it but, I'd like to shoot you an e-mail.
I've got some suggestions for your blog you might be interested in hearing. Either way, great blog and I look forward to seeing it expand over time.
My web site live web cam

Anonymous said...

Wonderful goods from you, man. I've take into account your stuff prior to and you are simply extremely fantastic. I really like what you have bought right here, certainly like what you're saying and the way in which
in which you are saying it. You're making it entertaining and you still take care of to keep it wise. I can't wait to read much more from
you. This is really a terrific website.
Also visit my web blog ; Hardcore Free Porn

Anonymous said...

Hi my loved one! I want to say that this article is awesome,
great written and come with almost all important infos.
I would like to peer extra posts like this .
Also see my web site: amateur porn

Anonymous said...

That is a very good tip particularly to those fresh to the blogosphere.
Short but very precise information… Thanks for sharing
this one. A must read article!
Feel free to surf my blog :: free teen porn

Anonymous said...

What's up to every one, as I am truly keen of reading this website's post to be updated on a regular basis.
It carries fastidious information.
Check out my web site : free teen porn

Anonymous said...

Hello there I am so excited I found your webpage, I really
found you by error, while I was browsing on
Yahoo for something else, Regardless I am here now and would just like to say thanks a lot for a tremendous post
and a all round exciting blog (I also love the theme/design),
I don’t have time to look over it all at the moment but I have book-marked it and also added in your RSS
feeds, so when I have time I will be back to read much more, Please do keep up the superb work.
Also see my page :: Microphone Disable

Anonymous said...

Hi to every , because I am genuinely keen of reading
this web site's post to be updated daily. It consists of good data.
Visit my homepage ; contractors in Orlando

Anonymous said...

Malaysia & Singapore & brunei best internet blogshop for wholesale & supply korean add-ons, accessories, earstuds, locket, rings, hair, bracelet & bangle accessories.

Deal 35 % wholesale price cut. Ship Worldwide
Also see my page: La Fiesta

Anonymous said...

Hello There. I found your blog using msn. This is a really well written article.
I will make sure to bookmark it and come back to read more
of your useful info. Thanks for the post. I'll certainly comeback.

Here is my blog post resveratrol supplements

Anonymous said...

It's genuinely very difficult in this full of activity life to listen news on Television, so I only use world wide web for that reason, and obtain the most up-to-date news.

My web site ... www.emptysea.net

Anonymous said...

I want to to thank you for this great read!! I certainly enjoyed every little bit of it.
I have you book marked to look at new stuff you post…

Here is my blog post: www.Arzuacidadan.Net

Anonymous said...

Asking questions are in fact pleasant thing if you are not understanding anything completely, except
this article presents nice understanding yet.

Look into my webpage traditional life insurance policies

Anonymous said...

What's up to all, it's genuinely a good for me to visit this web site, it consists of priceless
Information.

Feel free to visit my webpage: http://www.minecraftworldexchange.com/
My page > therapy quit smoking

Anonymous said...

Thanks designed for sharing such a pleasant
thought, post is fastidious, thats why i have read it fully

Here is my website :: wiki.underbonesphilippines.com

Anonymous said...

I am regular reader, how are you everybody? This post posted at this web site is
truly pleasant.

Here is my web site; senseo coffee maker

Anonymous said...

Thanks for sharing your thoughts. I truly appreciate your efforts and I
will be waiting for your next write ups thanks once again.



Here is my webpage ... perfume slideshare

Anonymous said...

Fantastic post however , I was wanting to know if you could write a litte
more on this subject? I'd be very grateful if you could elaborate a little bit further. Cheers!

my web blog; kliknij

Anonymous said...

It's appropriate time to make some plans for the longer term and it is time to be happy. I've read this
post and if I may I desire to suggest you some interesting
issues or tips. Maybe you can write subsequent articles referring to this article.
I want to learn even more issues approximately it!

My blog post; kliknij

Anonymous said...

Hi! Do you know if they make any plugins to safeguard against hackers?
I'm kinda paranoid about losing everything I've worked hard on.
Any tips?

Feel free to visit my homepage - http://ves2.ru

Anonymous said...

Hey there great blog! Does running a blog like this require a lot of work?
I've very little understanding of computer programming however I had been hoping to start my own blog in the near future. Anyhow, should you have any suggestions or tips for new blog owners please share. I know this is off topic but I just had to ask. Thank you!

Also visit my blog post; kliknij

Anonymous said...

Attractive section of content. I just stumbled upon your website and in accession capital
to assert that I acquire in fact enjoyed account your blog posts.
Any way I will be subscribing to your augment and even I achievement you access consistently
rapidly.

Here is my blog; kliknij

Anonymous said...

Hi there! This is my first comment here so I just wanted to give a quick shout out and say I truly enjoy reading
your blog posts. Can you recommend any other blogs/websites/forums that deal with
the same subjects? Thanks a lot!

Also visit my website :: kliknij

Anonymous said...

I am really pleased to read this website posts which carries plenty
of useful facts, thanks for providing these kinds
of information.

My web site - kliknij

Anonymous said...

For latest news you have to go to see world wide web and on
web I found this web site as a best web page for most up-to-date updates.


Also visit my blog; kliknij

Anonymous said...

Hello there! This is my first visit to your blog! We are a group of volunteers and starting a new project
in a community in the same niche. Your blog provided us valuable information to work on.
You have done a wonderful job!

Take a look at my homepage; kliknij

Anonymous said...

Yesterday, while I was at work, my cousin stole my iphone and tested to see if
it can survive a twenty five foot drop, just so she can be a youtube sensation.

My apple ipad is now destroyed and she has 83 views. I
know this is totally off topic but I had to share it with someone!


my web page: kliknij

Anonymous said...

Good day! I could have sworn I've been to this site before but after reading through some of the post I realized it's new
to me. Anyhow, I'm definitely delighted I found it and I'll be book-marking and checking back often!


Also visit my homepage - forum.obeczlata.cz

Anonymous said...

This piece of writing gives clear idea designed for the new viewers of blogging, that actually how to do blogging.


Here is my web page ... kliknij

Anonymous said...

Your way of describing everything in this piece of writing is truly good,
every one be able to effortlessly understand it, Thanks a lot.


Feel free to visit my homepage; kerrytownconcerthouse.com

Anonymous said...

I savor, cause I found exactly what I was taking a look for.
You've ended my four day long hunt! God Bless you man. Have a nice day. Bye

Also visit my web site; http://kis-avl.ru/

Anonymous said...

My partner and I stumbled over here coming from a different web page and thought I might check things out.
I like what I see so now i am following you.
Look forward to looking into your web page again.

My web blog; http://www.acnutrition.com/member/124169/

Anonymous said...

Wow, marvelous blog layout! How long have you been blogging
for? you made blogging look easy. The overall look of your website is excellent,
let alone the content!

Feel free to surf to my blog :: kliknij

Anonymous said...

As the admin of this website is working, no question very shortly it will be well-known, due to its feature contents.


My webpage http://abcreditcardpayments.com/regatta-clothing-has-a-new-online-store/

Anonymous said...

Hello, i think that i saw you visited my blog thus i came to “return the favor”.
I'm trying to find things to improve my web site!I suppose its ok to use a few of your ideas!!

Here is my blog - http://whitecoatresearch.com/?p=25

Anonymous said...

Link exchange is nothing else but it is just placing
the other person's webpage link on your page at suitable place and other person will also do similar for you.

Also visit my blog :: www.american-ss.net

Anonymous said...

This post provides clear idea in support of the new users
of blogging, that in fact how to do blogging and site-building.


Also visit my page; http://www.greyscustomgold.com/no-fuss-secrets-for-modcloth-coupon-code-the-inside-track/

Anonymous said...

This info is priceless. Where can I find out more?

Look into my page www.xxxmoviegalls.com

Anonymous said...

I know this website presents quality based articles
and other material, is there any other web page which gives these kinds of
things in quality?

my web blog ... http://www.jnmassage.info

Anonymous said...

Very good info. Lucky me I ran across your site by chance (stumbleupon).
I have saved it for later!

Visit my web blog: xxx-fuck.net

Anonymous said...

After checking out a handful of the articles on your web site, I really appreciate your technique of blogging.
I bookmarked it to my bookmark website list and will be checking
back soon. Take a look at my website as well and tell me your opinion.


Here is my site - xxxsexsite.net

Anonymous said...

Its not my first time to go to see this website, i am visiting this
web page dailly and take good information from here every day.


Feel free to visit my blog :: Free Porn

Anonymous said...

Admiring the dedication you put into your blog and detailed information you
offer. It's good to come across a blog every once in a while that isn't the same out of date rehashed information.

Great read! I've saved your site and I'm including your RSS feeds to my Google account.



Feel free to surf to my web blog ... Free Sex

Anonymous said...

Hello would you mind letting me know which webhost you're utilizing? I've loaded your blog
in 3 completely different web browsers and I must say this blog loads a lot faster then most.
Can you suggest a good internet hosting provider at a
fair price? Thanks, I appreciate it!

Stop by my website; www.onhiddencam.info

Anonymous said...

Hurrah! After all I got a webpage from where I be able to in
fact take useful data concerning my study and knowledge.



Look at my webpage: http://www.cfnmfever.net/videos/Tons-of-sperm-in-blonds-mouth-689/

Anonymous said...

I blog frequently and І genuinely thаnk you for уour
information. Thiѕ аrticle hаѕ truly
peаkеd my interеst. I аm gοing to book maгk your
blog and keep сhecking for new detailѕ аbout οnce a week.

I οpted in for уοur RSS fеed too.



my homеpаge HomePagе ()