Performance Characteristics of the Jacobi and the Gauss-Seidel Versions of the Auction Algorithm on the Alliant FX/8

Recently, D. Bertsekas proposed a new method to solve the linear assignment problem that appears to be well suited for concurrent computation. The method, called the auction algorithm is a primal-dual iterative scheme that updates the dual solution by performing coordinate steps similar to those of the Jacobi and Gauss-Seidel (GS) methods for unconstrained optimization. Bertsekas noted that the GS version tends to converge a little faster on uniprocessor computers but is generally much less parallelizable. Consequently, several questions arise regarding the relative performance of these two versions: How will their performances be affected by changes in problem size, cost range, and problem data? How should one design an efficient implementation for each version that takes full advantage of novel computer hardware capabilities such as concurrency and vectorization? How does the concurrency of computations affect the sensitivity of the solution times to changes in the cost range for each version? Will Jacobi outperform Gauss-Seidel in a vector-concurrent computational environment? In this paper we address these questions and present insightful algorithmic and empirical comparisons between the two versions. Both versions have been tested on 224 randomly generated dense assignment problems with the number of variables ranging from 10,000 to 16 million and with cost ranges of [0, 10], [0, 100], [0, 1,000], and [0, 10,000]. The vector-concurrent computational environment used in this study is the one available on the Alliant FX/8 at Argonne National Laboratory. In our computational experiments the Jacobi version has exhibited higher speedups, less sensitivity to changes in cost ranges, and better solution times in vector-concurrent mode for cost ranges [0, 1,000] and [0,10,000]. However, for cost range [0, 100] the GS version can be up to five times faster and solved the one million variable problem in less than one second and the 16 million variable problem, in less than 7 seconds. In addition, the results of our experiments support the conjecture that the performance of both versions of the auction algorithm improves dramatically when the ratio of the problem size to the cost range is greater than a certain constant that is shown to be 6 for cost range [0, 100] and 8 for cost range [0, 50]. We also show that the variability in solution times due to changes in the cost range is moderated when the vector-concurrent capabilities of the Alliant FX/8 are invoked.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.