There are formulae such as the Woodbury identity that allow for rank k updates to a previously solved problem, which I think fits your problem nicely. In addition, using a reasonably smart iterative algorithm such as conjugate gradients will also be helpful since you can feed it the solution from your previous problem, and for small perturbations the new solution can be computed very quickly.

a) There are formulae such as the Woodbury identity that allow for rank k updates to a previously solved problem, which I think fits your problem nicely.

b) In addition, using a reasonably smart iterative algorithm such as conjugate gradients (or whatever is appropriate for your problem) will also be helpful since you can feed it the solution from your previous problem, and for small perturbations the new solution can be computed very quickly.

In practice I have found it sufficient to use just (b), but it might be worth trying both separately or together.