Time complexity of matrix multiplications?

In summary: I don't think you can do the same thing for additions. I am not sure why.)In summary, for (1), the number of multiplications required is n3 + n2 and the number of additions required is n3. For (2), the number of multiplications required is n2 + n2 and the number of additions required is n2. Therefore, as a function of n, (2) is faster to compute.
  • #1
de1337ed
11
0
Let A and B be n×n matrices, and let v be a column vector of length n. Which of
the following two expressions is faster to compute?
1. ( A⋅ B )⋅ v or 2. A⋅ (B⋅ v)
As a function of n, give the number of multiplications and additions required for each part.

My attempt:

So, I said that (2) is faster to compute because B x v will have n additions and n multiplications, so that would be f(n) = n2. And B x v would be another column vector.
And A x (B x v) would also be g(n) = n2 for the same reason (because B x v is a column vector). So I thought the total complexity for be T(n) = n4

For (1), I thought that (A x B) would be f(n) = n3 because there are n additions, n multiplications, and this occurs n times. Multiplying the new n x n matrix with the column vector, we would get g(n) = n2 because of n multiplications and n additions. So in total, it would be T(n) = n5.

I feel like this isn't correct, but maybe I'm on the right track?
A little help please?
Thank you.
 
Physics news on Phys.org
  • #2
de1337ed said:
Let A and B be n×n matrices, and let v be a column vector of length n. Which of
the following two expressions is faster to compute?
1. ( A⋅ B )⋅ v or 2. A⋅ (B⋅ v)
As a function of n, give the number of multiplications and additions required for each part.
It is not clear what the question is asking. Maybe it is this:

As a function of n, give (i) the number of multiplications, and
(ii) the number of additions, required for each part.


When you compute a new element by multiplying a row of n elements by a column of n elements, the number of multiplications involved is n, but the number of additions involved is n-1. (I'm not sure whether n-1 is close enough to call it n, or not.)
For (1), I thought that (A x B) would be f(n) = n3 because there are n additions, n multiplications, and this occurs n times. Multiplying the new n x n matrix with the column vector, we would get g(n) = n2 because of n multiplications and n additions. So in total, it would be T(n) = n5.
Why multiply the two? If you had to combine them, I think you'd add them, and this can't be simplified further: number of multiplications = n3 + n2.
 

What is time complexity in the context of matrix multiplications?

Time complexity refers to the amount of time it takes for a computer algorithm to solve a problem. In the context of matrix multiplications, it refers to the number of operations required to multiply two matrices of a given size.

How is time complexity calculated for matrix multiplications?

Time complexity for matrix multiplications is typically calculated using the Big O notation. This notation represents the worst-case scenario for the number of operations needed to solve a problem, based on the size of the input.

What is the time complexity of the standard matrix multiplication algorithm?

The standard matrix multiplication algorithm has a time complexity of O(n^3), where n represents the size of the matrices being multiplied. This means that for larger matrices, the number of operations required will increase significantly.

How does the time complexity change for different types of matrix multiplications?

The time complexity for different types of matrix multiplications can vary. For example, the Strassen algorithm has a time complexity of O(n^2.81), which is slightly more efficient than the standard algorithm. Other specialized algorithms may have different time complexities depending on the specific properties of the matrices being multiplied.

What factors can affect the time complexity of matrix multiplications?

The time complexity of matrix multiplications can be affected by various factors, including the size of the matrices, the type of algorithm used, and the hardware and software being used to perform the calculations. Additionally, the sparsity (number of zeroes) in the matrices can also impact the time complexity.

Similar threads

  • Math POTW for University Students
Replies
4
Views
630
  • Calculus and Beyond Homework Help
Replies
3
Views
521
Replies
27
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
460
  • Engineering and Comp Sci Homework Help
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
514
  • Calculus and Beyond Homework Help
Replies
3
Views
689
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Math Proof Training and Practice
Replies
25
Views
2K
Back
Top