Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Time complexity of matrix multiplications?

  1. Mar 19, 2012 #1
    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.
     
  2. jcsd
  3. Mar 20, 2012 #2

    NascentOxygen

    User Avatar

    Staff: Mentor

    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.)
    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook