- #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.
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.