MultiGrid Calculus

Oh, this is only One-dimensional ! So let's skip it altogether . . . Wrong ! Why ?
  1. Because one-dimensional space is a subspace of all spaces of higher dimension. So how can you ever understand the latter when you don't even understand the former ?
  2. Discarding the details of an 1-D theory is a manifestation of disdainful behaviour, which has become typical for people working on "demanding applications". Those who find being impressive more important than taking all steps which are necessary, in order to arrive at a thourough understanding of the matter.
  3. Simple & Straightforward and yet Satisfactory. This remembers to the good old days of Mathematics. Maybe this report will take you back in time. However, if you are not interested in Mathematics as such, why then are you reading these pages anyway ? Please find your pleasure elsewhere !
  4. Apart from personal emotion, I find this 1-D MultiGrid Calculus among the best I have ever done. So if you would have expected more, then I have to apologize for my shortcomings.
    The judgement of a (supposed) authority in the field: I'm sorry, but I don't see anything in it.

Please scan through my Guide through MGC for obtaining a first impression,
before you are going to read the real thing.

The complete theory is disclosed here by a (HTML) Summary
and as a Document in three formats: Generalizations of my (mis)conception of MG were gradually coming up but subsequently have died out: An implementation of 3-D MultiGrid, with the ZonWind project, has been deferred (forever), a bottleneck being that the (time consuming) Finite Element Assembly procedure would have to be carried out several times then, instead of only once.
Thus MG offers no advantage with such 3-D FEA.

Loosely related stuff:

Summary of 1-D Theory

The well-known Newton-Rhapson
algorithm is used as a starting point for finding still another method for solving tri-diagonal systems of equations. It is shown that this method is equivalent with Gaussian elimination in the first place. It is established, in addition, that the method is closely related to MultiGrid algorithms.
The notion of Persistent Properties is developed. The behaviour of a product of the matrix coefficients can be understood in full detail, with help of a Connection to Trigonometry in a "dangerous" domain and a Connection to Hyperbolic functions in a "safe" domain. It turns out that the safe domain is quite distinct from the dangerous one. It is shown that safe solutions can only be found for a certain subset of all second order ODE's (Ordinary Differential Equations), namely those ODE's where the discriminant of the characteristic polynomial is positive (or zero).
The quotient of the off-diagonal matrix coefficients is an exponential function of the grid spacing. All matrix coefficients can be expressed in the coefficients of the accompanying ODE and the grid spacing.

Corollaries

By diminishing grid spacing, any tri-diagonal linear system of equations will converge to a linear second order (ordinary) differential equation. In addition, we find the restriction that the discriminant of the characteristic polynomial of the ODE must always be non-negative. If such is not the case, then it cannot be "safely" approximated by a tri-diagonal system. Because, while trying to solve such a "dangerous" system, you would find that there is a great chance of running into a division by zero. This especially means that oscillatory behaviour, with tri-diagonal systems, can never be achieved in quite a safe manner: there does not exist a path then which is guaranteed to end up in the analytical solution. Trying to describe time-like problems as if they were like in space is thus likely doomed to failure. In space alone, no oscillations can occur, while in time they can, and often do. This at least partly explains why, in the realm of numerical analysis, space-like and time-like solution patterns are implemented differently, most of the time ;-)
My original intention has been to prove that time indeed has an "arrow". But the above work only explains why time can not be structured like one-dimensional space, with interactions in backward and forward direction. Thus resulting in stable and non-oscillatory matrices, which is contradictory to the nature of time-like events. Multigrid Calculus is incompatible with the time domain.

Additional Notes

In the section Some Stable Solutions, the following formulas have been derived, for the off-diagonal coefficients a and b in the tri-diagonal system, where a + b = 1 :

    a = (1 - ε) / 2     b = (1 + ε) / 2     where   ε = tanh(P.dx/2)

Here P = Péchlet number, dx = spacing of uniform mesh. A little algebra reveals that this is equivalent with:

    a = 1/(eP.dx + 1)     b = 1/(1 + e- P.dx)     or   b = eP.dx / (eP.dx + 1)

On the other hand, the following formulas are found in Patankar's Numerical Heat Transfer and Fluid Flow, section 5.2-4, the so-called Exponential Scheme:

      ae = Fe / [ exp(Pe) - 1 ]         aw = Fw exp(Pw) / [ exp(Pw) - 1 ]         ap = ae + aw + ( Fe - Fw )

It can be demonstrated quite easily that Patankar's exponential scheme is compatible with the one from Multigrid Calculus. For uniform meshes, we can drop the suffixes e and w and normalize the flux F to unity = 1 , resulting in:

      a = 1 / [ exp(P) - 1 ]       b = exp(P) / [ exp(P) - 1 ]       a + b = [ exp(P) + 1 ] / [ exp(P) - 1 ]

Now multiply both a and b with [ exp(P) - 1 ] / [ exp(P) + 1 ] and we are done.

TripleGrid Calculus

This document is meant as an extension to a previously published one, named MultiGrid Calculus. Upon retrospective, DoubleGrid Calculus would have been a better name for the latter. The reason being that Multigrid is much of a reserved word within the world of Numerical Analysis. Therefore its use in a pure mathematics context, most likely, will give rise to confusion. (But maybe that's just intended by this author ?)

Anyway, quite unexpectedly, I have discovered that there exists another kind of Multigrid Calculus, which is distinct from DoubleGrid. It also works with coarsening and refinement of grids, but does not double or halve the intervals. Instead, it makes the intervals larger or smaller, not with a factor two, but with a factor three. Ah, and now you would think that the next step is a MultiGrid Calculus employing a factor 4 or maybe 5 . But this is not so. The factor four being already covered by a double doubling in the first place. Furthermore, it can be proved that factors five or higher are not an option, except as a powers of 2 and 3 . Thus all possibilities for MultiGrid are exhausted with DoubleGrid and TripleGrid.

Interesting References