a matrix-free method
A matrix-free method solves A x = b without ever forming, or even storing, the matrix A. At first this sounds impossible — how do you solve a system you do not have? The trick is that every Krylov method (CG, GMRES, BiCGStab) interacts with A through exactly one operation: it hands A a vector v and asks for the product A v. It never needs the individual entries a_ij, never inspects A's structure, never factors it. So all you must supply is a function — a black box — that, given any vector v, returns A v. The matrix exists only implicitly, as the action it performs.
This is liberating whenever the product A v is far easier to compute than the matrix itself. A spectacular example arises in solving nonlinear equations by Newton's method, where each Newton step needs to solve a linear system with the Jacobian matrix J. Forming J explicitly can be prohibitively expensive or complicated, but the only thing the Krylov solver needs is J times a vector — and J v is just a directional derivative, which can be approximated by a single finite difference: J v is approximately (F(x + epsilon v) - F(x)) / epsilon, two evaluations of the function F and no Jacobian at all. This is the heart of Jacobian-free Newton-Krylov methods, a backbone of large-scale nonlinear simulation. Matrix-free thinking also wins when A is a huge structured operator (a convolution, an FFT-based solve, a discretized integral operator) whose action is cheap but whose explicit storage would be enormous or dense.
The freedom comes with a real cost. Preconditioning is the lifeblood of Krylov methods, yet many strong preconditioners (like incomplete LU) need the actual matrix entries — which a matrix-free method has deliberately thrown away. So matrix-free solvers must rely on preconditioners that are themselves matrix-free or that use only a cheap approximation of A, and finding a good one is the central challenge. There is also a subtle accuracy issue when the product is approximated by finite differences: too large an epsilon gives a poor Jacobian, too small lets round-off dominate, so the step size must be chosen with care. Still, for the very largest problems — where you could not store A even if you wanted to — matrix-free Krylov methods are not a convenience but a necessity.
In a Jacobian-free Newton-Krylov solver, each linear solve never forms J. GMRES asks only for J v, supplied as J v ~ (F(x + epsilon v) - F(x)) / epsilon — two residual evaluations. The whole nonlinear PDE solve proceeds without ever assembling a Jacobian matrix.
Supply only the action v -> A v; the matrix never exists explicitly.
Going matrix-free saves storage but sacrifices access to the entries, which most strong preconditioners need — so the hardest part is building an effective matrix-free preconditioner. And when the product A v is approximated by finite differences, the perturbation epsilon must balance truncation error against round-off, just as in numerical differentiation.