Implementation and computational results for the hierarchical algorithm for making sparse matrices sparser

ABSTRACT

If A is the (sparse) coefficient matrix of linear-equality constraints, for what nonsingular T is A = TA as sparse as possible, and how can it be efficiently computed? An efficient algorithm for this Sparsity Problem (SP) would be a valuable preprocessor for linearly constrained optimization problems. In a companion paper we developed a two-pass approach to solve SP called the Hierarchical Algorithm. In this paper we report on how we implemented the Hierarchical Algorithm into a code called HASP, and our computational experience in testing HASP on the NETLIB linear-programming problems. We found that HASP substantially outperformed a previous code for SP and that it produced a net savings in optimization time on the NETLIB problems. The results allow us to give guidelines for its use in practice.

REFERENCES

• 1: ADLER, I., KARMARKAR, N., RESENDE, M., AND VEIGA, O. Data structures and programming techniques for the implementation of Karmarkar's algorithm, Tech Rep. Dept of Industrial Engineering and Operations Research, Univ of Calif., Berkeley, 1987 A shorter version appeared in ORSA J. Comput. 1, 2 (1989), 84-106.
• 2: Shin-Jyh Frank Chang, Increasing sparsity in matrices for large-scale optimization--theoretical properties and implementational aspects, 1989
• 3: CHANG, S. F., AND McCoRMICK, S. T. A faster implementation of a bipartite cardmahty matching algorithm. Univ. of British Columbia Tech Rep UBC 90-MSC-005, 1990.
• 4: S. Frank Chang , S. Thomas McCormick, A hierarchical algorithm for making sparse matrices sparser, Mathematical Programming: Series A and B, v.56 n.1-3, p.1-30, Aug. 1992 [doi>10.1007/BF01580890]
• 5: DUFF, I S. MA28--a set of FORTRAN subroutines for sparse unsymmetric linear equations. A.E.R.E. Harwell Rep. 8730, 1977.
• 6: FOURER, R. Solving staircase linear programs by the simplex method, 2: Pricing. Math. Program. 25, (1983), 251 292.
• 7: GAY, D.M. Electronic mail dmtnbution of linear programming test problems Math. Program Soc. Comm. Algorithms Newsl. 13 (1985), 10 12.
• 8: HO, J. K., AND LOUTE, E. A set of staircase hnear programming test problems Math. Program. 20 (1981), 245-250.
• 9: HOFFMAN, A. J., AND McCoRMiCK, S. T, A Fast Algorithm That Makes Matrices Optimally Sparse. In Progress zn Combinatorial Optlmtzahon, W. R. Pulleyblank, Ed Academic Press, 1984, 185-196.
• 10: Irvin J. Lustig, An analysis of an available set of linear programming test problems, Computers and Operations Research, v.16 n.2, p.173-184, Mar. 1989 [doi>10.1016/0305-0548(89)90018-X]
• 11: MCCORMICK, S.T. A combinatorial approach to some sparse matrix problems. Ph.D. Thesis, Stanford Univ., Stanford, Calif., 1983.
• 12: S. T. McCormick, Making sparse matrices sparser: computational results, Mathematical Programming: Series A and B, v.49 n.1, p.91-111, Nov. 1990 [doi>10.1007/BF01588780]
• 13: MCCORMICK, S. T., AND CHU% S. F. Weighted sparsity problem: Complexity and algorithms. UBC Faculty of Commerce Working Paper 90-MSC-007, Vancouver, BC, 1990.
• 14: MCCORMICK, S. T., ~D CHUG, S. F. Making AAT Sparser for interior-point algorithms: Complexity and heuristics. In preparation, 1990.
• 15: MURT^GH, B. A., AND S^UNDERS, M. A. MINOS 5.0 User's Guide. Tech. Rep. SOL 83-20, Systems Optimization Laboratory, Dept. of Operations Research, Stanford Univ., Stanford, Calif., 1983.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency; Verification**

General Terms:
Algorithms, Measurement, Performance