How can I implement matrix multiplication (X1, X2......)in C?

Question

1.00/5 (1 vote)

See more:

Divide and conquer algorithm for matrix multiplication:

MMult(A, B, n)

If  n= 1  Output  A×B

Else  Compute A11,B11, . . . , A22,B22 % by computing  m=n/2

X1←MMult(A11, B11, n/2)

X2←MMult(A12, B21, n/2)

X3←MMult(A11, B12, n/2)

X4←MMult(A12, B22, n/2)

X5←MMult(A21, B11, n/2)

X6←MMult(A22, B21, n/2)

X7←MMult(A21, B12, n/2)

X8←MMult(A22, B22, n/2)

C11←X1+X2

C12←X3+X4

C21←X5+X6

C22←X7+X8

Output C

End If

What I have tried:

I don't understand what data structure can i use here or, how the above algorithm can be implemented...plz help me giving some pieces of c code.
#Thanks...experts

Posted 5-Apr-16 7:52am

Member 12378355we

Updated 5-Apr-16 9:11am

Matt T Heffron

v3

Add a Solution

Comments

Matt T Heffron 5-Apr-16 14:48pm

Richard's solution is right. You just need to declare, allocate, use and free arrays (A??, B??, X??, C??) locally to your MMult function.
However, the algorithm you show will work correctly only for square matrices with rank equal to a power of 2!
Is it really more efficient than the triple-nested loop that handles the general case of an NxK mult KxM giving a NxM?

Member 12378355we 5-Apr-16 15:07pm

So I need to compute those matrix A??B?? in my recursive function?

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Matt T Heffron · Answer 1 · 2016-04-05T09:11:00

But how could I Compute A11,B11, . . . , A22,B22 % by computing m=n/2 in c?

The easy way:
You allocate your local A?? and B?? and copy the appropriate pieces of the A and B matrices into these and then call MMult recursively. This will use lots of additional memory.

The harder (more thinking!) way:
Use a different function for the recursive calls to MMult (e.g., InternalMMult)
This function will take as parameters the original A and B but will also include the information about the row and column ranges of interest for A and B at each recursive call. This function will do its calculations based on the specified regions of interest of the A and B.

It may be possible to pass common intermediate (X) and result (C) matrices with ranges in a similar manner. This would take some serious analysis! (Are you "up" for a challenge?!)

Note:
As I noted in my comment above on the original question:
However, the algorithm you show will work correctly only for square matrices with rank equal to a power of 2.
Is it really more efficient than the triple-nested loop that handles the general case of an NxK mult KxM giving a NxM?

Richard MacCutchan · Answer 2 · 2016-04-05T08:37:00

Solution 1

You can use arrays to hold the values of each matrix, and then just multiply according to the rules.

Posted 5-Apr-16 8:37am

Richard MacCutchan

Comments

Member 12378355we 5-Apr-16 14:42pm

But how could I Compute A11,B11, . . . , A22,B22 % by computing m=n/2 in c?