Linear Algebra Matrix Addition Algorithm

In summary, an algorithm can be developed to compute the sum of two symmetric nxn matrices, taking advantage of symmetry for each matrix. The complexity is O(n^2) and the algorithm involves looping through the rows and columns of the matrices, inputting the values and adding them to get the corresponding value in the output matrix C. To make the algorithm more efficient, one can take advantage of the symmetric nature of the matrices by reducing the number of reads and writes in the loop, leading to a more efficient computation. It is always important to look for symmetries in algorithms to improve their efficiency.
  • #1
iwan89
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 :(
 
Physics news on Phys.org
  • #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.
 

What is "Linear Algebra Matrix Addition Algorithm"?

The Linear Algebra Matrix Addition Algorithm is a mathematical method used to add two matrices together. It is a fundamental operation in linear algebra and is used in a variety of applications, including computer graphics, machine learning, and engineering.

How does the algorithm work?

The algorithm works by adding each element of one matrix to the corresponding element in the other matrix. For example, to add two 2x2 matrices, you would add the top-left elements together, the top-right elements together, the bottom-left elements together, and the bottom-right elements together. This process is repeated for each element in the matrices, resulting in a new matrix with the same dimensions as the original matrices.

What are the benefits of using this algorithm?

The Linear Algebra Matrix Addition Algorithm allows for efficient and accurate computation of matrix addition, which is essential in many mathematical and scientific fields. It also allows for easy implementation in computer programs, making it a valuable tool for data analysis and other applications.

Are there any limitations to this algorithm?

One limitation of the algorithm is that it can only be used for adding matrices with the same dimensions. Additionally, it is only applicable for matrices with numerical elements, so it cannot be used for matrices with non-numeric elements such as symbols or variables.

How is this algorithm used in real-world applications?

The Linear Algebra Matrix Addition Algorithm is used in a variety of real-world applications, including computer graphics, image processing, data analysis, and machine learning. It is also used in many engineering and scientific fields, such as physics, chemistry, and biology, to solve complex mathematical problems and analyze data.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
372
  • Calculus and Beyond Homework Help
Replies
25
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
14
Views
587
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
18
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
977
Back
Top