Chapter 5

Results

The results of the MATLAB were as expected for comparisons of execution time and performance between the variations of the Bartels-Golub Method. However, the Revised Simplex Method outperformed all expectations to provide an insight into the inner workings of MATLAB and perhaps even a suggestion for direction of future research.

Revised Simplex Method

The number of flops that the Revised Simplex Method required in each problem was consistently better than any of the other methods, varying from a factor of two times better to more than 10 times better. This unexpected result suggested that the inverse of the basis was not nearly as dense as originally thought. Upon reviewing the inverse-basis densities, this supposition holds. Although the Revised Simplex Method provided the worst inverse-basis densities of all the methods, these densities were still sparse enough to take advantage of sparse matrix structure to reduce time-complexity.

The worst inverse-density that the Revised Simplex Method only occasionally surpassed 40%, and it never reached even 55%. These sparse inverse-bases allow MATLAB to take advantage of their structure to reduce the time required by matrix multiplication. Since the matrix-inversion routine involves a significant amount of matrix multiplication, it will also reduce in the time-complexity due to the sparse nature of the inverse-bases. This result accounts for the significant time-complexity advantage the Revised Simplex Method had over the other methods.

Despite the sparse nature of the inverse-bases, the Revised Simplex Method still produced much higher densities than its counterpart methods. Unlike the other methods, the Revised Simplex Method maintains the basis-inverse as a matrix. As a result, any multiplication requires that the entire matrix be available in memory, so any implementation will be limited in use by the physically available memory. Alternatively, secondary storage and virtual memory could be used, however, both methods increase execution time significantly indicating that other methods may be more amenable. For smaller problems the Revised Simplex Method would be the quickest method.

The significant use of native MATLAB functions resulted in the Revised Simplex Method taking by far the least amount of execution time of all the methods. Unfortunately, MATLAB has some limitations in solving very large sparse-matrix problems because of its interpretive nature. At present, compilation utilities for MATLAB still lack sparse matrix support, so this analysis could not be applied to them.

Bartels-Golub Method

The Bartels-Golub Method generally provided the worst flop count of all the methods. The sparse nature of the bases unfortunately did not translate into as signficant a savings during the LU-factorization as they did in the basis-inversion of the Revised Simplex Method. With the extra overhead of the repeated backsolves, the Bartels-Golub Method proved to be extremely costly in terms of floating-point operations.

The size of the upper and lower triangular factors proved to be much sparser than the inverse-bases of the Revised Simplex Method by a factor of two to five. This indicates that the Bartels-Golub Method could handle larger problems in the same amount of memory. Similar to the Revised Simplex Method, though, the backsolves performed by the Bartels-Golub Method still require large amounts of data to be present in memory, so computer memory may still be a severely limiting factor.

The actual running time of the Bartels-Golub Method was the second-fastest of all the methods; in fact, it slightly superceded the Revised Simplex Method in one particular small problem. Although the Bartels-Golub Method used native MATLAB calls like the Revised Simplex Method, the extra time involved in performing the repeated backsolves increased the running time significantly. As MATLAB continues to evolve, the Bartels-Golub Method may eventually surpass the Revised Simplex Method in execution time.

Sparse Bartels-Golub Method

Finding an appropriate threshhold number of eta factors before requiring refactorization of the basis proved to be difficult as no one value was good for every problem. The most effective range of threshhold values varied from to . Using this value, the Sparse Bartels-Golub Method consistently outpaced the original Bartels-Golub Method in all but a few ill-conditioned problems.

The Sparse Bartels-Golub Method performed only slightly fewer flops than the Bartels-Golub Method in most cases. In a couple situations, the Sparse Bartels-Golub Method performed slightly more flops. In the remaining instances, however, the Sparse Bartels-Golub Method managed to perform three to four times fewer floating point operations, showing the advantage of deferring refactorization. Because the sparse algorithm was more detailed and required more interpretation by MATLAB, the running time was increased often 10 to 20 times from the Bartels-Golub Method.

Most significantly, the maximum number of nonzero entries that had to be stored by the Sparse Bartels-Golub Method was fewer than the number of nonzero entries that the Bartels-Method had to contend with in each and every problem. In addition, the Sparse Bartels-Golub Method does not require that the entire set of data be in memory at any one time. Since the eta matrices consisting the lower-triangular factor are applied in sequence, these same entries can be easily stored in secondary storage and read when needed. As a result, much larger problems are more easily handled by the Sparse Bartels-Golub Method than either the Revised Simplex Method or the Bartels-Golub Method.

Forrest-Tomlin Method

No refactorization threshhold value proved to be satisfactory over any wide range for the Forrest-Tomlin Method. However, setting a threshhold for nonzero entries in the list of row-eta factors proved to be most effective, with the threshhold values ranging from to . Although the Forrest-Tomlin Method showed promise, it usually proved to require more flops than the Sparse Bartels-Golub and Bartels-Golub Methods.

Despite the increase in floating-point operations, the Forrest-Tomlin Method usually succeeded in producing fewer nonzero factors than any of the other methods. It also surpassed the other sparse methods significantly in running time. The use of MATLAB’s intrinsic functions calculate and apply the row-eta factors caused this speed up, often by factors of 2 to 10 times.

Reid’s Method

Because of their similarity, Reid’s Method used the same threshhold values as the Sparse Bartels-Golub Method. Surprisingly, the use of rotations did not decrease the number of non-zero factors or floating point operations. In actuality, Reid’s Method proved to be slightly worse in most cases. In fact, the same ill-conditioned matrices that caused the Sparse Bartels-Golub Method to perform poorly also caused Reid’s Method to fail and find a solution at a nearby corner instead.

Reid’s Method often produced the same number of nonzero entries as the Sparse Bartels-Golub Method most likely because it followed the same set of decisions as the latter algorithm. However, on those occasions where they differed, Reid’s Method proved to be more often than not the worse of the two resulting in extra nonzero entries, longer running times, and more floating-point operations.

The Results

The problems solved were a variety of small- and medium-sized problems available from the Netlib ftp site. These problems included a variety of industrial problems in a variety of situations, but most importantly they were real problems instead of academic problems. Table 1 describes the problems according to their matrix dimensions, , and total number of nonzero coefficients.

The most scrutinized data were the number of flop counts each problem required for each algorithm. In Table 2, these flop counts are summarized in terms of millions of flops. Although the values range from problem to problem, the Revised Simplex Method consistently outperformed the other methods.

The agg2 and agg3 problems were unable to find the correct solution when Reid’s method was applied to them. Closer analysis showed that as these problems approached the solution, the basis became unstable and took a slightly different path. Reid’s Method obtained a result that was within the same order of magnitude as the solution but was too disparate to be considered correct.

The amount of CPU time that each algorithm takes, as shown in Table 3, tells us little about the efficiency of the algorithm under MATLAB, but it does give us some insightful information about how the algorithms work with MATLAB. The Revised Simplex Method made extremely good use of MATLAB’s internal coding to run often two to three times faster than each of the other algorithms. The Bartels-Golub Method also used MATLAB’s internal LU-factorization code to often run faster than the sparse-matrix algorithms.

The stability of each method is easiest to compare by looking at the number of times the basis required refactorization. In the case of the Revised Simplex Method and the Bartels-Golub Method, refactorization occurs each iteration so their numbers are far higher than the others. The full results are available in Table 4. The Forrest-Tomlin Method outperformed the other sparse algorithms, however the Sparse Bartels-Golub and Reid’s Methods still significantly improved on the dense algorithms.

Finally, some measure has to be taken about the amount of data storage that is required. Even with the price of computer memory dropping, the size of industrial problems are increasing and the actual amount of data that must be held in memory must remain a consideration in evaluating any algorithm. Table 5 presents the maximum number of nonzero data entries that each algorithm had to handle for each problem. The direct matrix inversion employed by the Revised Simplex Method resulted in the large numbers of nonzeros that can be seen here. The Bartels-Golub Method proved to do much better, however the Forrest-Tomlin Method proved to be the best method for keeping the amount of data to a minimum.

The data collected provided many insights into the Simplex Method algorithms being tested and the nature of MATLAB. In general, the Revised Simplex Method performed fastest and with the fewest calculations, but it required a large amount of memory and basis refactorizations. The Sparse Bartels-Golub Method proved to be simple and effective, however the Forrest-Tomlin and Reid’s variations often performed slightly better.