1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Time complexity of matrix multiplications?
Loading...