Time complexity of matrix multiplications?

Click For Summary
SUMMARY

The discussion centers on the time complexity of matrix multiplications involving two n×n matrices, A and B, and a column vector v. It concludes that the expression A⋅(B⋅v) is computationally more efficient, requiring a total of T(n) = n² multiplications and n² additions, while the expression (A⋅B)⋅v results in T(n) = n³ + n² multiplications and additions. The key takeaway is that the order of operations significantly impacts the overall computational complexity, with the latter expression being less efficient due to the additional matrix multiplication step.

PREREQUISITES
  • Understanding of matrix multiplication
  • Familiarity with time complexity analysis
  • Knowledge of Big O notation
  • Basic linear algebra concepts
NEXT STEPS
  • Study the Strassen algorithm for matrix multiplication
  • Learn about the Coppersmith-Winograd algorithm for further optimization
  • Explore the implications of matrix multiplication on algorithm design
  • Investigate the use of parallel computing in matrix operations
USEFUL FOR

Mathematicians, computer scientists, software engineers, and anyone involved in algorithm optimization or linear algebra applications will benefit from this discussion.

de1337ed
Messages
10
Reaction score
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
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.[/color]

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.
 

Similar threads

Replies
8
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 3 ·
Replies
3
Views
3K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 14 ·
Replies
14
Views
4K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 27 ·
Replies
27
Views
3K
Replies
2
Views
2K
  • · Replies 4 ·
Replies
4
Views
3K