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

84
0
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:

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top