• Support PF! Buy your school textbooks, materials and every day products Here!

Linear Algebra Matrix Addition Algorithm

  • Thread starter iwan89
  • Start date
  • #1
27
0

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 :(
 

Answers and Replies

  • #2
329
34
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.
 

Related Threads for: Linear Algebra Matrix Addition Algorithm

  • Last Post
Replies
2
Views
5K
  • Last Post
Replies
0
Views
1K
Replies
10
Views
2K
Replies
4
Views
3K
Replies
4
Views
2K
  • Last Post
Replies
1
Views
7K
  • Last Post
Replies
13
Views
967
Top