MultiGrid Calculus
Oh, this is only One-dimensional ! So let's skip it altogether . . .
Wrong ! Why ?
- 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 ?
- 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.
- 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 !
- 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 HTML/MathJax Document.
Generalizations of my (mis)conception of MG
were gradually coming up but subsequently have died out:
- 2-D Full MultiGrid implementation
available as a Windows (Delphi)
executable
(source code included, as usual)
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.
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