Abstract

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

Mathematical Subject Classification

Primary: 65C20, 65Z05, 82B80, 76F30

Authors