Choice of solver for A*x=b when only A*x is available

I need to solve A*x=b. I have a routine that provides matrix
multiplcation A*x, where A is rectangular and x is the supplied
vector. However I don't know of an iterative (linear) technique that
can be used for this; they need A'*b as well. So I've been using a
nonlinear method to minimize ||b - A*x|| which I'm sure is terribly
wasteful!

Is there a linear solver for this situation? Or what nonlinear solver
is best suited for linear problems?
.

Relevant Pages