Remarks on implementation of O(n1/2τ) assignment algorithms

ABSTRACT

We examine an implementation and a number of modifications of a 1973 algorithm of Hopcroft and Karp for permuting a sparse matrix so that there are no zeros on the diagonal. We describe our implementation of the original Hopcroft and Karp algorithm and compare this with modifications which we prove to have the same O(n1/2&tgr;) behavior, where the matrix is of order n with &tgr; entries. We compare the best of these with an efficient implementation of an algorithm whose worst-case behavior is O(n&tgr;).

REFERENCES

• 1: DUFF, I.S. A survey of sparse matrix research. In Proc. IEEE 65 (1977), 500-535.
• 2: I. S. Duff, On Algorithms for Obtaining a Maximum Transversal, ACM Transactions on Mathematical Software (TOMS), v.7 n.3, p.315-330, Sept. 1981 [doi>10.1145/355958.355963]
• 3: I. S. Duff, Algorithm 575: Permutations for a Zero-Free Diagonal [F1], ACM Transactions on Mathematical Software (TOMS), v.7 n.3, p.387-390, Sept. 1981 [doi>10.1145/355958.355968]
• 4: DUFF, I. S., GRIMES, R. G., AND LEWIS, J.G. Sparse matrix test problems. Report CSS 191, Computer Science and Systems Division, Harwell Laboratory, UK, 1987.
• 5: DUFF, I. S., AND REID, J.K. Performance evaluation of codes for sparse matrix problems. In Performance Evaluation of Numerical Software. L. D. Fosdick (Ed.), North-Holland, New York, 1979, 121-135.
• 6: EVERSTINE, G.C. A comparison of three resequencing algorithms for the reduction of matrix profile and wavefront. Int. J. Numer. Meth. Eng. 14 (1979), 837-853.
• 7: GEORGE, A., AND LIU, J. W.H. An automatic nested dissection algorithm for irregular finiteelement problems. SIAM d. Numer. Anal. 15 (1978), 1053-1069.
• 8: GUSTAVSON, F.G. Finding the block lower-triangular form of a sparse matrix. In Sparse Matrix Computations. J. R. Bunch and D. J. Rose (Eds.). Academic Press, New York, 1976, 275-289.
• 9: HALL, M. An algorithm for distinct representatives. Amer. Math. Monthly 63 (1956), 716-717.
• 10: HOPCROFT, J. E., AND KARP, R.M. An n'~/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2 (1973), 225-231.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Theory