We present methods for the reduction of the complexity of computational problems,
both time-dependent and stationary, together with connections to renormalization,
scaling, and irreversible statistical mechanics. Most of the methods have been
presented before; what is new here is the common framework which relates the
several constructions to each other and to methods of theoretical physics,
as well as the analysis of the approximate reductions for time-dependent
problems. The key conclusions are: (i) in time dependent problems, it is
not in general legitimate to average equations without taking into account
memory effects and noise; (ii) mathematical tools developed in physics for
carrying out renormalization group transformations yield effective block
Monte Carlo methods; (iii) the Mori–Zwanzig formalism, which in principle
yields exact reduction methods but is often hard to use, can be tamed by
approximation; and (iv) more generally, problem reduction is a search for hidden
similarities.
Keywords
problem reduction, renormalization, irreversible
statistical mechanics, memory, Monte Carlo
