Chapter Contents |
Previous |
Next |
The NETFLOW Procedure |
It is more convenient to factor T by block triangular matrices P and M , such that P = T M . The matrices P and M are used instead of T because they are less burdensome to work with. You can perform block substitution when solving the Simplex iteration linear systems of equations.
where D_{w} = D - CA^{-1}B and is called the working basis matrix.
To perform block substitution, you need the tree data structure of the A matrix, also the C , B , and D_{w} matrices. Because the C matrix consists of columns of the constraint coefficient matrix, the maintenance of C from iteration to iteration simply entails changing information specifying which columns of the constraint coefficient matrix compose C .
The A^{-1}B matrix is usually very sparse. Fortunately, the information in A^{-1}B can be initialized easily using the tree structures. In most iterations, only one column is replaced by a new one. The values of the elements of the new column may already be known from preceding steps of the Simplex iteration.
The working basis matrix is the submatrix that presents the most computational complexity. However, PROC NETFLOW usually can use classical Simplex pivot techniques. In many iterations, only one column of D_{w} changes. Sometimes it is not necessary to update D_{w} or its inverse at all.
If INVD_2D is specified in the PROC NETFLOW statement, only one row and one column may need to be changed in the D_{w}^{-1} before the next Simplex iteration can begin. The new contents of the changed column are already known. The new elements of the row that changes are influenced by the contents of a row of A^{-1}B that is very sparse.
If INVD_2D is not specified in the PROC NETFLOW statement, the Bartels-Golub update can be used to update the LU factors of D_{w} . The choice must be made whether to perform a series of updates (how many depends on the number of nonzeros in a row of A^{-1}B), or refactorization.
Chapter Contents |
Previous |
Next |
Top |
Copyright © 1999 by SAS Institute Inc., Cary, NC, USA. All rights reserved.