The problem can be formally stated as follows:
Given a graph , let each vertex have a load
associated with it. The flow calculation problem is to find the amount of migrating load
along each edge , such that
after the migration, the load on each vertex is the same. That is
The graph here is the so called processor graph of the partitioning. Each vertex of the processor graph corresponds to a subdomain (or a processor) and two vertices are linked by an edge if the two subdomains share a boundary. Figure 14 shows the processor graph corresponding to the partitioning in Figure 13 (b). The load can simply be taken as the number of nodes in the subdomain . Figure 14 shows that subdomain 1 has a load of 25 nodes, whilst others have 15 nodes each. In the following the terms vertex and processor are used interchangeably.
It is noted that the flow calculation problem does not have a unique answer. This is because the solutions are given by a linear system (9), with as the unknown. There are equations (out of these, are independent), and unknowns. As there are usually more edges than vertices in a graph (that is, ), there are usually more unknowns than equations and so the answer to the problem is not unique.
This flow calculation problem has been studied by many authors [4,6,14,28,43,44,41,78,88,89]. Apart from parallel unstructured mesh based applications, it has appeared in areas such as parallel molecular dynamic simulation [7,55]. Some of the algorithms are discussed in the following.