Question

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?

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

Answer 2

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

Answer 3

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

Answer 4

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}\]

Answer 5

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

Answer 6

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.

Answer 7

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

Answer 8

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.

Answer 9

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?

Answer 10

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.

Answer 11

\[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}\]

Answer 12

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.

Answer 13

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

Answer 14

Makes sense how I found the flops?

Answer 15

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

Answer 16

[ 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

Answer 17

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

Answer 18

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

Answer 19

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

Answer 20

ohhh..now i understand already how to get n(n+1)/2.

it's simple but quite tricky. =)

Answer 21

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