Steward’s algorithm

We now consider how Steward s algorithm can help to ascertain whether or not the system of equations describing the process is determinate. It should be noted that if a system of equations having the same number of variables as equations incorporates a subset of equations that contains fewer variables than equations, a unique solution of the system equations is unlikely to exist. We have used the words is unlikely to rather than does not because there are some special classes of equations that specify more than one variable, and if such an equation is included in the system, the system may have a subset of equations with fewer variables than equations and still be determinate. For example, consider the system of Eq. (5) ... 

Steward s algorithm, thus, can help locate errors in formulating a model of a process by identifying the set of equations that contains improperly specified design variables or parameters. The fortran program listed in Appendix A prints out the equation numbers in the subset that contains fewer variables than equations when an output set cannot be found. 

To illustrate how Steward s algorithm is executed, consider the adjacency matrix of Fig. 8a. The first row contains all zero elements and can be removed from the adjacency matrix the equation represented by row 1 is placed first in the ordering sequence for solving the equtions. The removal of the first row corresponds to a cut shown by the dashed lines in the associated graph in Fig. 8b, and the portion of the graph below the dashed line is the graph of the reduced matrix obtained by removing row 1 and column 1 as in Fig. 9a. 

There are no rows with all zero elements in the reduced matrix of Fig. 9a, hence we proceed to the second phase of Steward s algorithm by starting with the first row of the reduced matrix to trace the path 2 - 3 -> 4 -> 2. The loop of information flow between vertices 2, 3, and 4 is encircled by the dashed line in the graph in Fig. 9b. The rows and columns labeled 2, 5, and 4 are next removed from the reduced matrix and one row, which is the Boolean union of the rows labeled 2, 3, and 4, and one column, which is the Boolean union of the columns labeled 2, 2, and 4, are added to the reduced matrix to obtain the new reduced matrix of Fig. 10a. The added row and column are labeled... 

Steward s algorithm has proved to be quite efficient and easily programmed on a digital computer. The fortran program listed in Appendix A employs Steward s algorithm to accomplish the partitioning. 

Steward s algorithm is simple and very well suited to hand calculations for smaller systems. However, the computer storage and time requirements needed to tear large systems are prohibitive. 

Ledet s algorithm involves two phases. In the first phase an ordering of the rows and columns of the occurrence matrix takes place according to certain optimality criteria. The second phase involves reordering the occurrence matrix to reduce the number of torn variables. The first phase carries out an initial tearing, and the second phase improves the results of the first phase. However, instead of tearing individual variables as in Steward s algorithm, Ledet s method systematically reorders the occurrence matrix as described below. 

Second, the adjacency matrix would require n2 words of storage where n is the number of equations in the system. In finding the loops by either the method described here or by the other method proposed by Steward (S3), all of the loops are found more than once, which tends to reduce the efficiency of the procedure. Finally, since no exact criteria was given by Steward for evaluating the effectiveness of each tear, all possible tears must be performed and the best tear chosen by inspection of all the tears. Steward s algorithm, however, is simpler than Ledet s algorithm, and therefore better suited for decomposition of small systems by hand. 

C SUBROUTINE STEWRD PARTITIONS THE SYSTEM BY STEWARD S ALGORITHM. CALL STEWRD(MIN.MAX)... 

C THIS SUBROUTINE EXECUTES STEWARD S ALGORITHM FOR PARTITIONING FOR C THE SUBMATRIX OF ROWS AND COLUMNS OF K FROM MIN TO MAX. 

Lee (L2) proposed a different algorithm for tearing, which also obtains the tears for the minimum number of variables associated with the torn streams. The procedure is completely different from that of Sargent s in that the loops of material flow are determined first and tears made so that all the loops are broken. The algorithm requires a previous knowledge of the loops of material flow and which units and streams are included in each loop. The loops can be found by forming the adjacency matrix for the process, and determining the loops in the matrix by Steward s method as described in Section IV. 

---