We postulate that one should never start by considering how to decompose the matrix. Rather, one should start by considering how to decompose the physical problem to be solved. Notice that it is the elements of vectors that are typically associated with data of physical significance and it is therefore their distribution to nodes that is directly related to the distribution of the problem to be solved. A matrix (discretized operator) merely represents the relation between two vectors (discretized spaces):
Since it is more natural to start with distributing the problem to nodes, we partition x and y , and assign portions of these vectors to nodes. The matrix A should then be distributed to nodes in a fashion consistent with the distribution of the vectors, as we shall show next. We will call a matrix distribution physically based if the layout of the vectors which induce the distribution of A to nodes is consistent with where an application would naturally want them. We will use the abbreviation PBMD for Physically Based Matrix Distribution.
As discussed, we must start by describing the distribution of the vectors, x and y , to nodes, after which we will show how the matrix distribution is induced (derived) by the vector distribution. Let and be permutations so that
Here and are the permutations that order the elements of x and y , respectively, that are to be assigned to the first node first, then the ones assigned to the second node, and so forth. Thus if the nodes are labeled , and are assigned to . Notice that the above discussion links the linear algebra object ``vector'' to a mapping to the nodes. In most other approaches to matrix distribution, vectors appear as special cases of matrices, or as somehow linked to the rows and columns of matrices, after the distribution of matrices is already specified. We will also link rows and columns of matrices to vectors, but only after the distribution of the vectors has been determined, as prescribed by the application. We again emphasize that this means we inherently start with the (discretized) physical problem, rather than the (discretized) operator.
Next, we partition matrix A conformally:
This exposes a natural tie between sub-vectors of and corresponding blocks of columns of .
so there is a natural tie between sub-vectors of and corresponding blocks of rows of .
It has been well documented [, ] that for scalability reasons, it is often important to assign matrices to nodes of a distributed memory architecture using a so-called two-dimensional matrix distribution. To do so, the p = rc nodes are viewed as a logical mesh, , with and . This requires us to decide how to distribute the sub-vectors to the two-dimensional mesh. We will assume this is done in column-major order. (Notice that by appropriate choice of and , this can always be enforced.) The distribution of A is now induced by requiring block of columns to be assigned to the same column of nodes as sub-vector , and block of rows to the same row of nodes as sub-vector (and thus ). This is illustrated in Figure 1.1.
Often, for load balancing reasons, it becomes important to over-decompose the vectors and matrices, and wrap the sub-blocks onto the node mesh. This can be described by now partitioning x and y so that
where N >> p . Partitioning A conformally yields the blocked matrix
An explicitly two-dimensional wrapped distribution for the matrix can now be obtained by wrapping the blocks of x and y , which induces a wrapping in the distribution of A , as illustrated in Figure 1.2. Again, the sub-vectors are assigned to the node mesh in column-major order, wrapping as necessary. As before, the distribution of A is now induced by requiring block of columns to be assigned to the same column of nodes as sub-vector , and block or rows to the same row of nodes as sub-vector (and thus ). This is also illustrated in Figure 1.2. Notice that the wrapping of the vectors induces a tight wrapping of blocks of rows of , and a looser wrapping (by a factor of r ) of the blocks of columns of .
We emphasize that the distributions described in Figures 1.1 and 1.2 may appear to be special cases of Physically Based Matrix Distribution, since corresponding sub-blocks of x and y are assigned to the same node. Notice that by choosing in Equation 1.2, a general distribution can be attained .
Having just stated that we can achieve total generality, we need to also clearly state that in the initial implementation of PLAPACK, we actually only implement a special case: