0
$\begingroup$

In the conjugate gradient method for solving $Ax = b$, to update the search direction $p$ you would need to evaluate the matrix-vector product $Ap$, i.e. making sure that each search direction are A-conjugate to each other.

Is there a way to make the approximation of $Ap$? I have noticed that the residual vector is update via (reference here):

$$ r_{i+1} = r_i - \alpha A p_{i} $$

So can we somehow use the difference between each successive vector to approximate $Ap_i$?

$\endgroup$
3
  • $\begingroup$ I do not understand your question. In the algorithm en.wikipedia.org/wiki/…, you only need $A \, x_0$ and $A \, p_k$ and both can be obtained by matrix-vector products. What do you mean by "approximate $A\,p$"? $\endgroup$
    – gerw
    Commented May 9, 2016 at 10:34
  • $\begingroup$ I am trying to 100% avoid the matrix-vector product, and only want to use each successive set of vectors to generate the next one without the need of the matrix $A$ or the matrix vector multiplication $Ax$ at all. $\endgroup$ Commented May 9, 2016 at 11:26
  • 1
    $\begingroup$ You're not going to get very far without computing $Ap_k$. There are many ways to speed up certain matrix-vector products in certain contexts, using parallel code or an approximation method such as fast multipole. The beauty of a CG type method is you don't need to store the matrix, you just need a function $A(x)$ that computes $Ax$ by some means. $\endgroup$
    – icurays1
    Commented May 9, 2016 at 14:30

1 Answer 1

2
$\begingroup$

If you could eliminate the action of $A$ from the CG algorithm, then your new algorithm would find that $Ax=b$ has the same solution as $(2A)x = b$. This is clearly not possible.

For a parallel implementation, the real problem is not only the matrix vector multiplications but the inner products as these operations require communication at every step. Current research by Jim Demmel's group at Berkeley and Laura Gregori's group at INRIA concentrates on developing communication avoiding (CA) Krylov subspace methods. Here $s$ matrix vector multiplications are done in one step in an attempt to reduce the need for communication. The price is some numerical stability.

If you want to avoid inner products entirely, then consider Chebyshev acceleration. See Yousef Saad's book: Iterative methods for linear systems for the details.

$\endgroup$
1
  • $\begingroup$ Edits were suggested as there were a couple of misspellings. I have fixed the misspellings and added a couple of extra words to make the response more precise. Since I did not have the 2k points necessary to do more than view the suggested edit I opted for this approach. $\endgroup$ Commented May 9, 2016 at 13:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .