The price of an American-style contract on assets driven by a class of Markov processes containing, in particular, Lvy processes of pure jump type with infinite jump activity is expressed as the solution of a parabolic variational integro-differential inequality (PIDI). A Galerkin discretization in logarithmic price using a wavelet basis is presented. Log-linear complexity in each time-step is achieved by wavelet compression of the moment matrix of the price process' jump measure and by wavelet preconditioning of the large matrix LCPs at each time-step. Efficiency is demonstrated by numerical experiments for pricing American put contracts on various jump-diffusion and pure jump models. Failure of the smooth pasting principle is observed for American put contracts for certain finite variation pure jump price processes.