Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.



4D Part 5: Grids in PDEs
Posted:
Jun 28, 1993 11:26 AM


"Instead of looking at 4D as being very close to 3D, you can often get a better feel for 4D by thinking of it as quite a bit along the way to infiniteD. Understanding what happens in extremely high dimensions can clarify the emerging trends that make 4D a _different_ place to live than 2 and 3D," says Paul Burchard of the Geometry Center. Burchard is developing software to study Partial Differential Equations (PDEs) which are related to differential geometry.
This article consists of observations on the problems encountered in higher dimensions when using one of the standard methods of PDEs, namely grids. Numerical calculations of solutions to differential equations often involve a rectangular or triangular grid, using only values of derivatives on the grid points to get an approximation to the function at those grid points. I will describe some of the problems with rectangular grids in higher dimensions. These same problem occur in all shapes of grid, not just rectangular ones.
In a rectangular grid with k equally spaced grid points per unit length in each spatial direction, an n dimensional cube requires k^n grid points. In other words, the number of grid points grows exponentially with dimension. Thus using schemes with grid points very quickly becomes prohibitively costly in terms of storage and time as the dimension increases.
Aside from the large number of points in a rectangular grid, Burchard observes another problem with this approach of having the grid points be the vertices of a hypercube. Namely, as n gets large, the corners of a n dimensional hypercube stick out more and more, making it a pointy and strangely shaped object.
In terms of distance, the following shows that corners get further away: The length of a diagonal of a unit nD hypercube is the square root of n (sqrt(n)). (This can be deduced from the Pythagorean theorem and the fact that the length of each side is one.) The distance from the center to each corner is sqrt(n)/2. As dimension increases, the unit cube has corners which stick out more in linear distance.
Another measurement of the oddness of the shape of the cube is to look at how much of the volume is in the corners. Compare the volume of the nD hypercube to the inscribed n dimensional ball. In some sense, the inscribed ball cuts out the corners of the cube, leaving only the middle. If the volume of this ball gets smaller, since the hypercube is always unit volume, the volume contained in the corners of the cube must be increasing as dimension increases. Through some calculations which I will describe separately, the inscribed nD ball has volume V(n)=(V(n2)*pi)/(2*n). Note that the recursive formula contains an n in the denominator, so there is some kind of factorial decrease in volume. Thus as n increases, the volume of the inscribed ball quickly decreases. This means that more and more of the volume of the unit cube is contained away from the center, another indication that the corners of the high dimensional cube become more pointy.
To give a more detailed picture, it is not only the corners which stick out in the hypercube; all of the "edges" stick out to progressively larger extent as the dimension increases. For example, in the three dimensional cube, the faces (two dimensional edges) are distance 1/2 from the center, the edges (one dimensional edges) are distance sqrt(2)/2 from the center, and the corners (zero dimensional edges) are furthest away, namely sqrt(3)/2 from the center. In general, the k dimensional edges of the n dimensional cube stick out distance sqrt(nk)/3 from the center.
By the above, perhaps grids are not the best method to solve high dimensional PDEs. In fact, even in relatively low dimensional cases, it is necessary to resort to other techniques. According to Burchard, "From the perspective of trying to write fast accurate code in differential equations, five is in a practical sense most of the way to infinity; in other words, it is practically impossible to write the code I would like and have it run in any reasonable amount of time. I think 4D will still be feasible but slow; 5 or 6D is where it starts to become practically impossible with gridbased techniques."



