next up previous
Next: A Procedure for Choosing Up: Statement of the Problem Previous: Tiling with Hyperplanes

Geometric Considerations


First, we note that if tex2html_wrap_inline1926, then so is tex2html_wrap_inline1928 for any positive scalar tex2html_wrap_inline1930. The partition induced by A and b is unchanged if we scale the columns of A by arbitrary positive amount and scale the corresponding components of b by the reciprocal amounts. There is therefore no loss of generality if we replace A with tex2html_wrap_inline1560, the matrix obtained by scaling the columns of A to have unit euclidean length.

We first assume that tex2html_wrap_inline1908. Let tex2html_wrap_inline1910. Then except at the boundaries, all tiles are congruent to
tex2html_wrap_inline1952 is a parallelepiped subtended by the columns of the inverse of tex2html_wrap_inline1954. In other words, if tex2html_wrap_inline1956, then
To see this, note that tex2html_wrap_inline1960, so for any x that satisfies (3), tex2html_wrap_inline1964, and since tex2html_wrap_inline1966, equation (2) is satisfied.

Let tex2html_wrap_inline1968 denote the volume of tex2html_wrap_inline1952. Then
Let us now consider the faces of tex2html_wrap_inline1952. Without loss of generality, consider the face tex2html_wrap_inline1978 subtended by tex2html_wrap_inline1980. The face is itself a (k-1) dimensional parallelepiped. We want to know its surface area, or in general its (k-1) dimensional volume, which we denote tex2html_wrap_inline1986.
We give a proof, unfortunately algebraic rather than geometric in nature, in the Appendix.

What are the consequences of the lemma? we see that all the faces have the same area and that it is equal to the volume of tex2html_wrap_inline1952. Thus, the ratio tex2html_wrap_inline1992 of the volume to the total surface area of tex2html_wrap_inline1952 is just the reciprocal of the number of sides, 2k:

At first this is surprising, since if tex2html_wrap_inline1560 is far from having orthogonal columns we would expect a lower ratio. The explanation is that the constant ratio has been obtained because the size of tex2html_wrap_inline1952 grows as tex2html_wrap_inline1560 loses orthogonality. (Scaling up the size of any k-dimensional object by a factor tex2html_wrap_inline2012 increases the ratio by the factor tex2html_wrap_inline2012 ).

The problem we have is to make the ratio tex2html_wrap_inline1572 as big as possible subject to some limit, tex2html_wrap_inline1580 on the tile cross section. This is because, as we shall show in detail later (and it is clear intuitively), the cross section of a tile is proportional to the amount of local memory needed to execute it. The cross section of tex2html_wrap_inline1952 is also roughly equal to tex2html_wrap_inline2022. To satisfy such a bound, we must change the size of tex2html_wrap_inline1952. To keep the problem simple, we shall for the present consider rescaling b by a constant factor tex2html_wrap_inline1704. Let tex2html_wrap_inline1704 be chosen so that the area of a face, tex2html_wrap_inline2032, is exactly tex2html_wrap_inline1580. We have that the volume and area of the rescaled tile are
Thus, we must choose
We can then achieve the ratio of volume to surface area
On the other hand, if we wish a ratio tex2html_wrap_inline2046 of volume to surface area, we need tiles of dimension tex2html_wrap_inline2048. Therefore, we must be able to hold tiles whose sides have area

We can, because of these observations, now state the optimality problem we would like to solve: Given a cone tex2html_wrap_inline1766, find an integer basis whose elements are in the cone. Choose them so that the matrix having the scaled basis vectors as columns has largest possible determinant. (We call the determinant of this scaled matrix the normalized determinant.

This problem is related to, but is not the same as, choosing tex2html_wrap_inline1560 to minimize its spectral condition number under the constraints tex2html_wrap_inline2058. (See [10] for the definition and properties of matrix condition numbers.) Consider the vector of singular values of tex2html_wrap_inline1560. The normalization condition places it on the unit sphere in tex2html_wrap_inline2062. The condition number is the ratio of the largest to the smallest component; the determinant is the product of the components. In the unconstrained case, both are optimized by the vector of equal singular values. In the constrained case, however, the optimizing matrices can differ.

Of course, for general tex2html_wrap_inline1766, there may be no maximizer among the integer bases in the cone. And we do not know whether there is always a maximizing choice when tex2html_wrap_inline1766 comes from an integer dependence matrix D.

We can view this problem as the maximization of the real valued function tex2html_wrap_inline2070 over the tex2html_wrap_inline2072 dimensional space of integer matrices A, subject to m linear inequality constraints tex2html_wrap_inline2078. It might be fruitful to use a standard method for the continuous problem and then convert the solution to integer by some rounding-off procedure; we have not pursued this approach.

In the next section, we consider a heuristic method for choosing the basis A.

next up previous
Next: A Procedure for Choosing Up: Statement of the Problem Previous: Tiling with Hyperplanes

Jack Dongarra
Tue Feb 18 15:39:11 EST 1997