  We show that a wide variety of non-linear cellular automata (CAs) can be
decomposed into a quasidirect product of linear ones. These CAs can be
predicted by parallel circuits of depth O(log^2 t) using gates with binary
inputs, or O(log t) depth if ``sum mod p'' gates with an unbounded number of
inputs are allowed. Thus these CAs can be predicted by (idealized) parallel
computers much faster than by explicit simulation, even though they are
non-linear.
  This class includes any CA whose rule, when written as an algebra, is a
solvable group. We also show that CAs based on nilpotent groups can be
predicted in depth O(log t) or O(1) by circuits with binary or ``sum mod p''
gates respectively.
  We use these techniques to give an efficient algorithm for a CA rule which,
like elementary CA rule 18, has diffusing defects that annihilate in pairs.
This can be used to predict the motion of defects in rule 18 in O(log^2 t)
parallel time.
