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!

Homework Help: Number of Arithmetic Operations to solve (x^T)(A^-1)x

  1. Feb 21, 2009 #1
    1. The problem statement, all variables and given/known data
    Let A be a nxn real symmetric positive definite matrix and x not equal to 0 a real nx1 vector. Show how to computre xTA-1x in n3/3 + O(n2) arithmetic operations.

    2. Relevant equations

    3. The attempt at a solution
    Some things I think I do know:
    If A is real spd, so is A-1.
    Therefore, A-1=LLT where L is a lower triangular matrix with positive diagonal elements.
    I also know in class it was stated that solving Ax = b by Cholesky Factorization requires n3/3 + O(n2) arithmetic operations.
    Also, I might be wrong, but I think we are looking for there to be (n-1)2 + O(n) operations, then you would say that is equivalent to [tex]\sum[/tex]j=1n-1j2 and then [tex]\sum[/tex]j=1kj2=k(k+1)(2k+1)/6 = 2k3/6 + O(n2) = k3/3 + O(k2).
    I'm not sure how to piece these all together or if I even need this information, and I'm missing something else.

    Does anyone have any ideas? Thank you so much.
    Last edited: Feb 21, 2009
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted