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:

Notice that

and thus

This exposes a natural tie between sub-vectors of and corresponding blocks of columns of .

Also

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: