Time complexity of matrix multiplications?

AI Thread Summary
The discussion centers on the time complexity of two matrix multiplication expressions involving n×n matrices A and B and a column vector v. The first expression, (A⋅B)⋅v, requires O(n^3) for the matrix multiplication and O(n^2) for the subsequent multiplication with the vector, totaling O(n^5). The second expression, A⋅(B⋅v), involves O(n^2) for the vector multiplication and O(n^2) for the final matrix-vector multiplication, resulting in O(n^2) overall. Participants debate the accuracy of their calculations and the implications of the number of additions versus multiplications. Ultimately, the second expression is confirmed to be faster due to its lower computational complexity.
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.
 
Back
Top