Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

fahana1710

  • 2 years ago

let A and B be two symmetric matrices of the same order. Develop an algorithm to compute C=A+B,taking advantage of symmetry for each matrix.Your algorithm should overwrite B with C. What is the flop count?

  • This Question is Closed
  1. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    So we know that this means A[i,j]=A[j,i] , B[i,j]=B[j,i], and C[i,j]=C[j,i]=A[i,j]+B[i,j] A and B are symmetrical. This means A+B is symmetrical.

  2. fahana1710
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    okay, but how to write the pseudo code for the algorithm?

  3. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    You need to make a loop I think the loops usually use something like for...do

  4. fahana1710
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    okay..it is correct if i do like this : Input: Dim n for \[a _{ij}\], j>=i and \[b _{ij}\],j>=i where i,j=1,...,n Output : B=C Step 1 : for j=1,...,n for i=1,...,j \[b _{ij}^{new}=a _{ij}+b _{ij}\]

  5. fahana1710
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    but, i don't have any idea to make this as programming.

  6. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    I'm thinking... Does your algorithm use the fact that A and B are symmetrical? We should be able to do something like Step 1 : for j=1,...,n for i=1,...,j if i does not equal j, then output cij=cji=aij+bij if i equals j, then cij=aij+bij What do you think of this part? Do you think you can use it? Just trying to help.

  7. fahana1710
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yes. it's also correct. but do you know how to make it into pseudo code form?such as using mathematica or MATLAB?

  8. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    err...nope. It has been way to long. I think I could do it with maple after trail and error. But I don't have maple on this computer.

  9. fahana1710
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Owh, it's okay. One more question, do you know how to do calculate flop-count? My friend get \[\frac{ n(n+1) }{ 2 }\] is it correct?

  10. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    actually that is what I got. You want to know how I figured it out... Ok we want to basically know how many operations we did. And I had to look up the definition of flops. So we want to count the number of operations we did. I counted my diagonal elements which were n. Then for the first row we had (n-1) entries left to calculate second row we had (n-2) entries left to calculate third row we had (n-3) entries left to calculate ....... nth row we had (n-n) entries left to calculate So we had n diagonal entries + (n-1)+(n-2)+...+(n-n) other entries to calculate. So we have n+sum(n-i, i=1..n) Do you understand how I got this so far? We can simplify this to what your friend got.

  11. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    \[n+\sum_{i=1}^{n}(n-i)\] \[n+\sum_{i=1}^{n}n - \sum_{i=1}^{n}i\] \[n+n(n)-\frac{n(n+1)}{2}\] \[n(n+1)-\frac{n(n+1)}{2}=\frac{2n(n+1)-n(n+1)}{2}=\frac{(n+1)(2n-n)}{2}=\frac{1n(n+1)}{2}\]

  12. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    I counted each entry we had to calculate. I know the diagonal entries will be repeated once but all other entries will be counted twice. So you know if we had a 3 by 3 symmetric matrix. You find the sum of the operations we did by counting the diagonal entries and the entries above the diagonal. So for a 3 b3 symmetric matrix, we have 3 diagonal entries then the number of entries above that diagonal is (3-1)+(3-2)+(3-3) (3-1)=2 that is how many are above the diagonal in the first row (3-2)=1 that is how many are above the diagonal in the second row (3-3)=0 that is how many are above the diagonal in the 3rd row Now I ignored everything below the diagonal because we already performed those operations above the diagonal. We were suppose to use the fact that the matrix was symmetric after all.

  13. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    So using this we have 3+(3-1)+(3-2)+(3-3) or you can use the simplified formula 3(3+1)/2

  14. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Makes sense how I found the flops?

  15. fahana1710
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yes. i'm still trying to understand what you explain. =)

  16. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    [ a11 a12 a13] [ a22 a23] [ a33] Or you could have looked at is in much simpler way lol 3+2+1 =3(3+1)/2

  17. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    for a 4by 4, we could have said (4+3+2+1)

  18. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    I made it more complicated than it should have been Do you see what I mean so for an n by n, we do 1+2+...+n

  19. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    But either way the formula can be simplified to that n(n+1)/2 one

  20. fahana1710
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ohhh..now i understand already how to get n(n+1)/2. it's simple but quite tricky. =)

  21. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1381169885319:dw| 1+2+...(n-1)+n \[\sum_{i=1}^{n}i=\frac{n(n+1)}{2}\]

  22. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1381169994491:dw|

  23. fahana1710
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    woww..you tried so hard to make me understand. thank you so much. now, honestly, i understand already. =) are you a lecturer?

  24. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Yes.

  25. fahana1710
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oh, i see. until right now, i'm still dont know how to develop an algorithm to compute c=a+b.

  26. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Is it because you aren't sure what is acceptable to write exactly?

  27. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    And also because you want to input in the matlab and see if it works?

  28. fahana1710
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yes.

  29. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Yeah. I will have to do some review on that part. I'm going to class soon. I can't promise I will look at it tonight but I think @zarkon might know matlab. I could be wrong. No promises. lol.

  30. fahana1710
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    hehe. It's okay. You helped me a lot today. Actually, i'm going to sleep already because in Malaysia, right now is midnight. Thank you so much for your helped. May God bless you. =)

  31. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy