next up previous
Next: Statement of the Problem Up: Introduction Previous: Strip Mining and Loop


We use uppercase letters for matrices. The notation tex2html_wrap_inline1542 means that X has columns tex2html_wrap_inline1546. The notation tex2html_wrap_inline1548 means that X has elements tex2html_wrap_inline1552.

In general, we use lowercase Greek letters for scalars. Let
The following symbols have the indicated meaning


tex2html_wrap_inline1556 The index space -- the set of values of the loop index vector

A The matrix that transforms natural to new loop indices

tex2html_wrap_inline1560 The matrix A with its columns scaled

to have euclidean length one

F tex2html_wrap_inline1502

D The matrix of dependences

C The matrix of data fluxes

tex2html_wrap_inline1572 The ratio of the volume of a tile to its surface area

tex2html_wrap_inline1574 The vector of block size parameters

tex2html_wrap_inline1576 A normal vector to a tiling hyperplane; one of the columns of A\

tex2html_wrap_inline1580 A bound on the size of local memory.

tex2html_wrap_inline1582 The time required to perform the computation at a point

in the index space.

tex2html_wrap_inline1584 The time required to move data across one unit of area

in the hyperplane normal to tex2html_wrap_inline1576.

We shall make considerable use of determinants. If tex2html_wrap_inline1588 is a real, square matrix, then the real-valued function tex2html_wrap_inline1590 is the volume of the parallelepiped subtended by the columns of X:
Thus, tex2html_wrap_inline1594. Also tex2html_wrap_inline1596. If Y is also tex2html_wrap_inline1600, then tex2html_wrap_inline1602. If tex2html_wrap_inline1604 is a triangular matrix, then tex2html_wrap_inline1606.

Let tex2html_wrap_inline1608 denote the one-dimensional subspace spanned by the vector z, and let tex2html_wrap_inline1612 denote its orthogonal complement.

Proof: Let tex2html_wrap_inline1622 be a k-1-vector chosen so that for each tex2html_wrap_inline1626, tex2html_wrap_inline1628 is orthogonal to tex2html_wrap_inline1630. Construct the matrix
Then, since C is triangular and has unit diagonal, tex2html_wrap_inline1634. Since tex2html_wrap_inline1630 is a vector of length one, tex2html_wrap_inline1638. Thus,

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