1
$\begingroup$

Make an analysis of the computational complexity of the algorithm below, where it is given by the number of elementary operations that the algorithm performs (assignment is not considered). Where $A\in\mathbb{M}_n(\mathbb{R})$, $\lambda\in\mathbb{R}$, $B\in\mathbb{R}^n$ and $x\in\mathbb{R}^n$, $r\in\mathbb{R}^n$

(1) $x^{(0)}\in\mathbb{R}^n$ initial approach

(2) $r^{(0)}=b-Ax^{(0)};p^{(0)}=r^{(0)}$

(3) for $k=0,1,2...$

(4) $\lambda_k=\frac{<p^{(k)},r^{(k)}>}{<Ap^{(k)},p^{(k)}>}$

(5) $x^{(k+1)}=x^{(k)}+\lambda_k p^{(k)}$

(6) $r^{(k+1)}=r^{(k)}-\lambda_k Ap^{(k)}$

(7) $B_k=-\frac{<Ap^{(k)},r^{(k+1)}>}{<Ap^{(k)},p^{(k)}>}$

(8) $p^{(k+1)}=r^{(k+1)}+B_kp^k$

(9) end

According to the book this is an economic version of the traditional method of conjugate gradient. I have listed the algorithm to facilitate

$Ax^{(0)}$ it has a coast of $2n^2-n$ elementary operations

$b-Ax^{(0)}$ it has a coast of $n$ elementary operations

$<p^{(k)},r^{(k)}>$ it has a coast of $2n-1$ elementary operations

$<Ap^{(k)},p^{(k)}>$ it has a coast of $2n^2$ elementary operations

$x^{(k)}+\lambda_k p^{(k)}$ it has a coast of $2n$ elementary operations

$r^{(k)}-\lambda_k Ap^{(k)}$ it has a coast of $4n^2-n$ elementary operations

I will not go, because according to the book, the traditional conjugate gradient method has cost in the order of $n^2$, and this will clearly have higher order than that, maybe I was wrong in my calculations as well.

Can anyone help?

$\endgroup$
1
$\begingroup$

You've not considered the cost for assignments and divisions. Anyway, let's ignore this part since it doesn't dominate the final complexity.

Roughly, there are two mistakes in your calculation:

  • $\langle Ap^{(k)}, p^{(k)} \rangle$: you first need to compute $Ap^{(k)}$, which requires $2n^2 - n$ operations, and then you need to compute the inner product of $Ap^{(k)}$ and $p^{(k)}$, which requires $2n - 1$ operations. So the total # of operations if $2n^2 + n - 1$.

  • $r^{(k)} - \lambda_k Ap^{(k)}$: note that you've computed $Ap^{(k)}$ before so you don't need to compute it any more. So the # of operations here is $2n$.


I think your textbook in fact means the complexity is $\mathcal{O}(n^2)$, rather than meaning total $n^2$ operations are required. Moreover, you should notice that there is NO terminating condition in your algorithm, which means the algorithm will run forever.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.