1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Linear Algebra Matrix Addition Algorithm

  1. Oct 4, 2013 #1
    1. The problem statement, all variables and given/known data
    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?

    2. Relevant 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

    3. 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)

    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 :(
  2. jcsd
  3. Oct 4, 2013 #2
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted