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$?

• 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$"?
– gerw
Commented May 9, 2016 at 10:34
• 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. Commented May 9, 2016 at 11:26
• 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. Commented May 9, 2016 at 14:30

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.