{'fraction_non_alphanumeric': 0.03499806759135999, 'fraction_numerical': 0.00854554043028299, 'mean_word_length': 4.629199903311578, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Block Spins for Partial Differential Equations

We investigate the use of renormalisation group methods to solve partial differential equations (PDEs) numerically. Our approach focuses on coarse-graining the underlying continuum process as opposed to the conventional numerical analysis method of sampling it. We calculate exactly the coarse-grained or `perfect' Laplacian operator and investigate the numerical effectiveness of the technique on a series of 1+1-dimensional PDEs with varying levels of smoothness in the dynamics: the diffusion equation, the time-dependent Ginzburg-Landau equation, the Swift-Hohenberg equation and the damped Kuramoto-Sivashinsky equation. We find that the renormalisation group is superior to conventional sampling-based discretisations in representing faithfully the dynamics with a large grid spacing, introducing no detectable lattice artifacts as long as there is a natural ultra-violet cut off in the problem. We discuss limitations and open problems of this approach.


I. INTRODUCTION
It is a rare event in science that a single paper contains an idea so powerful that it revolutionises an entire field. Rarer still are those gems which transform two or more apparently separate fields, such as the paper entitled Scaling Laws for Ising Models near T c by Leo P. Kadanoff [1], published in the regrettably shortlived journal Physics. Indeed, this organ, edited and founded by P.W. Anderson and the late B.T. Matthias, announced as its by-line the memorable claim "An international journal for selected articles which deserve the special attention of physicists in all fields"; and perhaps no other journal before or since has lived up to this hubris. Kadanoff's famous article developed the notion of what came to be called "block spins", and was cited in the title of the early seminal paper by K.G. Wilson which introduced the modern form of the renormalisation group (RG) in both condensed matter and high energy physics [2].
Although these theoretical developments have become part of the canon of modern physics, the "spin-off" from Kadanoff's work continues to this day, as mathematicians and physicists, including Kadanoff and colleagues at the University of Chicago, study the singularities and patterns which arise in extended physical systems, governed only by sets of partial differential equations (PDEs) [3]. On the auspicious occasion of this 60th birthday Festschrift to honour Leo P. Kadanoff, it therefore seems appropriate to contribute a brief account of our recent unpublished work [4] which extends the "block spin" insights and renormalisation group theory to the numerical solution of PDEs. Some, but not all of our results have recently been rederived independently by Katz and Wiese [5], and we shall comment on the differences in the sequel. This work is part of our program to utilise RG methods for PDEs [6,7], and is distinct from our earlier work applying RG iterative methods to construct simi-larity solutions and travelling waves [8].

II. THEORY OF PERFECT OPERATORS A. Motivation
Discretisation is an inevitable part of numerical analysis. Let us suppose that we wish to solve a partial differential equation numerically. The standard procedure in real space is to suppose that the solution u(x) is sampled at points x i and an algorithm devised to approximate the values u i ≡ u(x i ). If the points are equidistant with spacing dx, then we naturally require that in the continuum limit dx → 0, the sequence u i converges to u(x).
The disadvantage of the sampling approach is that one is forced to reproduce as faithfully as possible all the detail and fine structure of the solution, even on a scale that may be of no interest or worse, beyond the regime of applicability of the differential equation itself. This has two consequences: • a small grid size dx must be used, which implies many grid points must be calculated and stored; • a small time step δt is implied by the small dx, either for reasons of accuracy or stability of the numerical method.
As a result, the numerical method is subjected to an unnaturally large degree of computational complexity. Finally, for a given sampling procedure there is no unique prescription for obtaining the equation governing the sampled points u i . The only criterion for admissability is that it converges in the continuum limit; in practice of course, one seeks schemes which are numerically stable and attain the continuum limit rapidly.
From the statistical physicist's point of view, Kadanoff's 1966 paper suggests that a more natural approach to discarding information is to coarse-grain rather than to sample. Such a procedure focuses on the scale of interest, whilst allowing the possibility of accessing the continuum function to an arbitrary level of detail if desired. Suppose that we denote the coarse-graining operator at scale Λ by the symbol C Λ , with capital letters denoting coarse-grained quantities. Then conceptually we need to find the operator L Λ which connects U (X, 0) and U (X, t) given the microscopic time evolution operator L connecting u(x, 0) with u(x, t), as shown schematically in the commutativity diagram below: In practice, we coarse-grain onto a lattice X i with a specified C Λ . The freedom of choice in this coarsegraining operator parallels the lack of uniqueness in defining a governing equation for sampled points u i in the sampling approach; but once a coarse-graining operator C Λ has been defined, there should be a unique prescription to obtain L Λ .
Our diagram suggests that coarse-graining and time evolution commute, but it is not clear that this is correct, even in principle. For example, an equation with a positive Liapunov exponent might have the following property: two initial values u 1,2 (x, 0) differing only in field configuration at two nearby points in space, but with the same coarse-grained representation U (X, 0), might differ substantially at very long times t: u 1 (x, t) = u 2 (x, t) even though the coarse-grained initial fields would evolve identically. This example raises the interesting question of whether such equations are well-defined: no numerical procedure would be appropriate, unless the divergence of the trajectories was still bounded (as in a strange attractor).
We also need to consider the appropriate coarsegraining scale. Two situations are possible here. In the first, we suppose that the solution we wish to obtain has a natural scale Λ below which there is no significant structure. In that case, our goal is to avoid having to overdiscretise the problem merely in order to attain the accuracy of the continuum limit. Thus, we would like to be able to use as large a value for the grid spacing dx as possible without sacrificing accuracy. In the second situation, there is no such obvious scale, or at least, it is not known a priori, but the computational demands are so large that it is simply not feasible to work with a grid spacing dx smaller than some size Λ. In this case, we would like to minimise in some sense the artifacts that must inevitably arise.
We will mainly have in mind the first situation, which is more straightforward because the only issue is speed of convergence to the continuum limit: there is no explicit discarding of important dynamical information. Instead the focus is how to remove lattice discretisation artifacts [4,5]. We will refer to an operator or equation as being 'perfect' if it has been constructed by coarse-graining appropriately so that it has no lattice artifacts; our discussion follows the pioneering work of Hasenfratz and Niedermeyer in the context of lattice gauge theory [9].
In the second situation, however, one is making an uncontrolled and potentially severe truncation of the correct dynamics, and issues of modelling must be faced. For example, can one model the neglected unresolved scales as effective renormalisations of the coefficients in the original PDE? Are the neglected degrees of freedom usefully thought of as noise for the retained large-scale degrees of freedom? And how can any available statistical information on the small-scale degrees of freedom be used to improve the numerical solution for the large-scale degrees of freedom? Such questions may perhaps be treated by combining constrained Monte Carlo simulation of the microscopic degrees of freeedom with a maximum entropy criterion for discretisation of the large-scale degrees of freedom. An alternative but related approach has been implemented by Kast and Chorin [10], who minimise the RMS error, estimated from knowledge of the microscopic probability distribution.

B. The Perfect Laplacian
Our goal in this section is to examine the simplest possible problem, namely the diffusion equation in d + 1 dimensions: subject to appropriate initial conditions and boundary conditions. The coarse-graining is defined with respect to a ddimensional hypercubic lattice of spacing a on whose vertices reside the lattice variables U (n, t) defined by The numerical scheme that we will adopt is Euler discretisation in time, but with a perfect discretisation for the Laplacian: where the perfect Laplacian ∆ a at scale a is given by where the delta function enforces the definition of the coarse-grained field This definition of the coarse-grained operator is of course motivated by field theory, but is unsatisfactory for several reasons. First, it is admittedly ad hoc; in some sense, it is imposing a probability distribution on the high wavenumber degrees of freedom which is not necessarily present in the actual solution of the PDE being solved. Second, we are implicitly assuming that the coarse-graining of a differential equation is accomplished by simply coarsegraining the separate terms in the equation according to the prescription given above. We would prefer to able to start with the governing PDE and coarse-grain the entire equation in a systematic procedure. We hope to report on this methodology in a future publication. The deltafunction constraint in Equation (4) can be softened by The calculation of the functional integral in Equation (4) is straightforward [9] and yields a convolution expression where R is a d-dimensional lattice integer, and . (8) Here, the vector p lies in the first Brillouin zone: |p i | < π. Evaluation of the coefficients ρ(R) requires numerical integration in general, but in the case of d = 1 there is a simplification because which can be summed by contour integration to yield In the case κ = 2, which looks just like the conventional lowest order finite difference expression for the second derivative. This is, however, slightly misleading, because this kernel acts on the coarse-grained function U (n), not the sampled value of the continuum function. The general result for arbitrary κ is where A ≡ −6κ/(κ − 2). These formula are problematic to interpret for the cases where κ < ∞, because the functional integral in Equation (4) does not exactly enforce the definition of the coarse-grained field U . Thus, for example, is it consistent to coarse-grain the initial condition using Equation (5), whilst at the same time using the perfect Laplacian operator with κ < ∞? We will return to this issue below.

III. NUMERICAL RESULTS IN ONE DIMENSION
In this section, we present numerical results obtained on differential equations in one space and one time dimension, but with varying character of solutions. All the results were initiated from the random initial conditions shown in Figure (1), defined on a lattice of 1024 points with grid spacing dx = 0.5 with periodic boundary conditions. First we examine the diffusion equation, where high wavenumber behaviour dies away rapidly. As expected, the RG numerical method performs well compared to the standard algorithms. The second example is the coarsening dynamics of the time dependent Ginzburg-Landau equation (sometimes known as model A), where the coalescence of domains is the dominant behaviour; we will see that over-aggressive coarse-graining of the initial conditions can lead to late time configurations which differ from the correct solution. Although it seems plausible that the statistical information is preserved, i.e. the ensemble averaged structure factor, we have not yet explicitly checked this hypothesis. The third example is the Swift-Hohenberg equation, which in the parameter range we studied forms a lamellar phase with a well-defined periodicity. Again, over-aggressive coarse-graining is seen to be counter-productive. Lastly, we studied the damped Kuramoto-Sivashinsky equation, which is a toy model for directional solidification and other systems which form interfacial patterns. The interesting aspect of this benchmark is that a spatio-temporal chaotic phase exists for certain parameter ranges. As one might expect from the heuristic comments earlier, faithful reproduction of the solution is not really possible with any significant degree of coarse-graining.
In order to perform these numerical experiments, we have had to make two uncontrolled approximations. First, we have followed Katz and Wiese and used the exact coarse-graining operation Equation (5) but allowed the Laplacian operator to have any κ, not just the value κ = ∞. In particular, we have used the special value κ = 2, where the Laplacian takes on its conventional and very local form. Our results are essentially unchanged when we use the κ = ∞ form of the Laplacian, but there is a slight loss of stability of the Euler algorithm in this case, which sets a limit on the maximum value of dt/dx 2 . For a general value of κ, the stability limit (calculated for the diffusion equation) is given by implying that dt/dx 2 < 1/6 for κ = ∞. Second, we have not yet calculated the coarse-grained operators corresponding to nonlinear operators such as u 3 and u∂ x u: instead we have simply replaced each nonlinear operator N (u) by writing C Λ N (u) = N (U ). This approximation can be controlled in a more systematic derivation of the theory.

A. Diffusion Equation
We used the random initial condition shown in Figure  (1), defined on a lattice of 1024 points with grid spacing dx = 0.5, and evolved it in three different ways to time t = 100. The first way was a benchmark calculation using a conventional numerical analysis Euler scheme with dt = 0.001.
The second way used the RG methodology we have described above. We coarse-grained the initial condition down to a smaller lattice of 128 grid points and dx = 4, using the coarse-graining of Equation (5), yielding the function exhibited in Figure (2). We evolved this forward in time using the perfect Laplacian of Equation (11) with κ = 2, and dt = 5. Such a large value was stable because of the much larger value of dx than in the benchmark. In the third way, we sampled N = 128 points of the initial condition with a uniform grid spacing of dx = 4, and then evolved this forward in time using the standard Euler method.
The appropriate comparison is between the two calculations using 128 points: how well does each reproduce the benchmark calculation? In Figure (3) is plotted the benchmark configuration at t = 100 along with the results from the coarse graining or sampling methods. The coarse grained result almost exactly falls onto the benchmark calculation, even though it uses an 8-fold coarser lattice and a bigger time step size. Numerical stability dictates that dt < dx 2 /2. This means that the largest time step size one can use for the benchmark lattice is about dt = 0.1. Therefore, by coarse graining by a factor of eight and using a dt 50 times larger than the maximum permitted for the benchmark, the calculation was accelerated by a factor of 400, without introducing any noticeable lattice artifacts. The reduction in CPU time will be more pronounced when we go to higher dimensions. Furthermore, one sees clearly that with the same degree of discretisation, the uniform sampling result is inferior to the coarse-graining result and does not reproduce the benchmark calculation very well.
The reason that coarse-graining works well in this instance is because our procedure preserved all relevant information down to the coarse grained scale Λ. In the uniform sampling method, however, one grid point is used to represent all those within a neighbourhood of size Λ; thus, this point is likely to be in the tail of the spectrum spanned by function values in the neighbourhood.
What is an appropriate scale at which to coarse-grain? Λ should be set such that the time scale of interest is larger than the relaxation time τ relax of details on a scale smaller than Λ. In the case of the diffusion equation, if the initial configuration is very smooth on the scale of Λ, we can safely coarse grain to that level; the inset to Figure (1) shows the power spectrum of the initial data, and reveals that the coarse-graining level used preserves the salient long-wavelength features. When there are significant high wavenumber modes, given that τ relax of a fluctuation on the order of dx is roughly proportional to dx 2 , we can at most coarse grain to a level Λ ∼ √ T with T being the time scale of interest. Because computation is most consuming in simulations with long evolution time and large lattices, we almost always want to coarse grain to some level. But if we are interested in the early time evolution of the configuration with significant high wavenumber modes, we should not coarse grain at all.

(14)
It has a nontrivial fixed point u(n, t) = ± √ ǫ when ǫ is positive. Unlike the diffusion equation, where the configuration continually flattens, one sees regions of u(n, t) = √ ǫ and u(n, t) = − √ ǫ forming, separated by domain walls. As time progress, these regions coalesce and expand as shown in Figure (4).
In our simulation, ǫ = 0.3, and the benchmark lattice was evolved with dx = 0.5, dt = 0.001. Coarse graining and sampling were used to evolve the system with dx = 2, dt = 0.1, and dx = 4, dt = 0.001. As shown in Figure  (4), coarse graining always yields superior results than uniform sampling. Also, one notices that when coarse grained to dx = 4, there are some suprious offshoots in the configuration. This is because we coarse-grained too aggressively. The structure factor S(k) ≡ |u(k)| 2 of the initial configuration is plotted in Figure (1). It has significant spectral weight beyond k = π/8. Each coarsegraining step (defined as double the dx size) discards half of the Brillouin zone with larger wavenumber. So coarsegraining three times loses the modes with k > π/8. This is not serious for diffusion where the dynamics is a trivial decay of large wavenumber modes, but is a poor approximation for model A where domains grow from the initial configuration.

C. Swift-Hohenberg Equation
The discretised form of the Swift-Hohenberg equation [11] u(n, t + dt) = u(n, t)+dt [ǫ u(n, t) − u(n, t) 3 −(1 + ∆ a ) 2 u(n, t)] was studied using the comparison methodology described above, and the results are shown in Figure (6). Because of the (1 + ∆ a ) 2 term, there is an intrinsic length scale of 2π and a periodic ground state. The dynamics is interesting because u not only has an amplitude but also a phase. We choose ǫ = 0.5. The benchmark lattice was evolved with dx = π/16, dt = 0.0001 to time t = 4. The coarse-graining and sampling methods used dx = π/4, dt = 0.001. Again, the coarse-grained result reproduces the benchmark quite well, better than sampling, but not as well as found in experiments on the diffusion and TDGL equations. We attribute this to the existence of the intrinsic length scale. When we coarse-grain to a level close to this period, many relevant modes are ignored. Indeed, when we coarse-grain further to dx = π/2, the dynamics longer follows the benchmark very closely, as shown in Figure (7).

D. Damped Kuramoto-Sivashinsky Equation
We also considered the damped Kuramoto-Sivashinsky equation [12], which can undergo a phase transition from a lamellar phase to spatio-temporal chaos when the control parameter ǫ exceeds a critical value ǫ c ∼ 0.68. The discretised equation of motion studied was where ∇u(n, t) is the usual central difference formula for first derivative. We examined both the lamellar phase (ǫ = 0.4) and the chaotic phase (ǫ = 0.9). The former situation is very similar to that found in the Swift-Hohenberg equation. In the chaotic phase shown in Figure (8), one finds that even coarse-graining once does not give us a result satisfactorily close to the benchmark. This is not surprising given that the chaotic phase has positive Liapunov exponent as discussed before. In Figure (8), the benchmark was obtained using dx = π/16, dt = 0.0001 to time t = 16, whereas the coarse graining and sampling methods used dx = π/8, dt = 0.0002. Of course, the interesting question to address is whether the statistical properties of the dynamics are faithfully reproduced by coarse-graining in a way that is superior to sampling methods.

IV. DISCUSSION
We have presented a feasible alternative to the numerical solution of differential equations, in which the continuum limit is attained from a sequence of coarse-grained function values rather than a sequence of sampled functions. The numerical results that we and others [5,10] have obtained are promising and a fully systematic study is clearly warranted. In particular, useful acceleration of appropriate problems is possible without loss of accuracy or even the need to use adaptive methods.
There are many issues left unresolved by our work (which is why it has remained unpublished until this timely occasion). First and foremost, what is the correct interpretation to place on the RG scheme when κ < ∞? It can be shown that a literal interpretation requires a stochastic coarse-graining transformation; in this case, should one (in principle) average over realisations of the coarse-graining noise in order to obtain the appropriate solution of the PDE? Is it correct to take the mean of this distribution, which seems to offer a justification for using an exact (i.e. κ = ∞) coarse-graining procedure with a κ = 2 formula for the dynamics? How can one properly extend the philosophy espoused here to nonlinear problems in a systematic way?
Katz and Wiese [5] implicitly addressed these issues by deriving the coarse-grained equations of motion from a postulated action functional S, which they varied with respect to all its arguments. In fact their procedure is equivalent to ours, and their action S can be derived from our Equation (4) leading to the result that e − 1 2 n U(n,t)∆aU(n,t) = Du Dλ e −S{U(n,t),u(n,t),λ(n,t)} where S{U (n, t), u(n, t), λ(n, t)} = 1 2 d d x u(x)∂ 2 x u(x) is the action (3.5) from reference [5]. Such a functional integral formulation does not possess a small parameter in which to make a loop expansion based around the classical action δS δu = ∂S ∂λ(n, t) = 0.
Furthermore, only by requiring the additional constraint ∂S ∂U (n) = 0 can one use the coarse-grained equation of motion for any κ consistently with the constraint of Equation (5) (eqn. (3.8) of reference [5]). Despite these questions, we are optimistic that the spirit of the program initiated by Leo P. Kadanoff in critical phenomena will be equally useful in the fields of pattern formation and partial differential equations.