Linear Algebra Matrix Addition Algorithm

[iwan89]

Homework Statement

let L and M be two symmetric nxn matrices. develop an algorithm to compute C=L+M, taking advantage of symmetry for each matrix. Your algorithm should overite B and C. What is the flop-count?

Homework Equations

How to minimize the number of flop count? I want to make the algorithm as efficient as possible..
I hope you can provide me with Pseudocodes as well

The Attempt at a Solution

The old algorithm produced a lot of flop count.

Input Two matrices a and b
Output Output matrix c containing elements after addition of a and b
complexity O(n^2)

Matrix-Addition(a,b)
for i =1 to rows [a]
for j =1 to columns[a]
Input a[i,j];
Input b[i,j];
C[i, j] = A[i, j] + B[i, j];
Display C[i,j];

Algorithm Description

To add two matrixes sufficient and necessary condition is "dimensions of matrix A = dimensions of matrix B".
Loop for number of rows in matrix A.
Loop for number of columns in matrix A.
Input A[i,j] and Input B[i,j] then add A[i,j] and B[i,j]
store and display this value as C[i,j];

how to take advantage of symmetric matrix in order to come out with more efficient matrix? Please help me :(

 

[brmath]

It has to do with how far you are running your loop for each row. For the first row you do have to look at all n elements and get ##c_{1j} = l_{1j} + m_{1j}.## But you also get ##c_{j1} = l_{1j} + m_{1j}.## So you can fill in that portion of C with 2n reads and 2n-1 writes.

Now for the 2nd row, you already have ##c_{21}## so you can run your loop on j from 2 to n, not 1 to n. And so on.

I think if you rewrite with this thought in mind, you can be considerably more efficient.

There may be a bigger message here: always, always look for symmetries, particularly if you expect a lot of computation.