zbMATH — the first resource for mathematics

A hierarchical algorithm for making sparse matrices sparser. (English) Zbl 0770.90039
Summary: If \(A\) is the (sparse) coefficient matrix of linear equality constraints, for what nonsingular \(T\) is \(\widehat A\equiv TA\) as sparse as possible, and how can it be efficiently computed? An efficient algorithm for this Sparsity Problem (SP) would be a valuable pre-processor for linearly constrained optimization problems. In this paper we develop a two-pass approach to solve SP. Pass 1 builds a combinatorial structure on the rows of \(A\) which hierarchically decomposes them into blocks. This determines the structure of the optimal transformation matrix \(T\). In Pass 2, we use the information about \(T\) as a road map to do block-wise partial Gauss- Jordan elimination on \(A\). Two block-aggregation strategies are also suggested that could further reduce the time spent in Pass 2. Computational results indicate that this approach to increasing sparsity produces significant net reductions in simplex solution time.

90C05 Linear programming
90C06 Large-scale problems in mathematical programming
Full Text: DOI
[1] I. Adler, N. Karmarkar, M.G.C. Resende and G. Veiga, ”Data structures and programming techniques for the implementation of Karmarkar’s Algorithm,”ORSA Journal on Computing 1 (1987) 84–106. · Zbl 0752.90043
[2] A.V. Aho, J.E. Hopcroft and J.D. Ullman,The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, MA, 1979). · Zbl 0326.68005
[3] A.L. Brearley, G. Mitra and H.P. Williams, ”Analysis of mathematical programming problems prior to applying the Simplex Algorithm,”Mathematical Programming 8 (1975) 54–83. · Zbl 0317.90037 · doi:10.1007/BF01580428
[4] S.F. Chang, ”Increasing sparsity in matrices for large scale optimization – theoretical properties and implementational aspects,” Ph.D. Thesis, Columbia University (New York, 1989).
[5] S.F. Chang and S.T. McCormick, ”A faster implementation of a bipartite cardinality matching algorithms,” Working Paper 90-MSC-005, Faculty of Commerce, University of British Columbia (Vancouver, BC, 1990a).
[6] S.F. Chang and S.T. McCormick, ”Implementation and computational results for the Hierarchical Algorithm for making sparse matrices sparser,” Working Paper 90-MSC-013, Faculty of Commerce, University of British Columbia (Vancouver, BC, 1990b).
[7] T.F. Coleman,Large Sparse Numerical Optimization, Lecture Notes in Computer Science No. 165 (Springer, Berlin 1984). · Zbl 0536.65047
[8] R.W. Cottle, ”Manifestations of the Schur complement,”Linear Algebra and its Applications 8 (1974) 182–211. · Zbl 0284.15005 · doi:10.1016/0024-3795(74)90066-4
[9] I.S. Duff, ”Ma28 – a set ofFortran subroutines for sparse unsymmetric linear equations,” A.E.R.E. Harwell Report 8730 (Harwell, UK, 1977).
[10] I.S. Duff, ”On algorithms for obtaining a maximum transversal,”ACM Transactions on Mathematical Software 7 (1981) 315–330. · doi:10.1145/355958.355963
[11] I.S. Duff, A.M. Erisman and J.K. Reid,Direct Methods for Sparse Matrices (Clarendon Press, Oxford, UK, 1986). · Zbl 0604.65011
[12] I.S. Duff and T. Wiberg, ”Remarks on implementations of O(n 1/2 \(\tau\)) assignment algorithms,”ACM Transactions on Mathematical Software 14 (1988) 267–287. · Zbl 0648.65041 · doi:10.1145/44128.44131
[13] D.M. Gay, ”Electronic mail distribution of linear programming test problems,”Mathematical Programming Society Committee on Algorithms Newsletter 13 (1985) 10–12.
[14] M. Grötschel, L. Lovász and A. Schrijver, ”The Ellipsoid Method and its consequences in combinatorial optimization,”Combinatorica 1 (1981) 169–197. · Zbl 0492.90056 · doi:10.1007/BF02579273
[15] A.J. Hoffman and S.T. McCormick, ”A fast algorithm that makes matrices optimally sparse,” in: W.R. Pulleyblank, ed.,Progress in Combinatorial Optimization (Academic Press, London and New York, 1984) pp. 185–196. · Zbl 0567.65018
[16] E.L. Lawler,Combinatorial Optimization:Networks and Matroids (Holt, Rinehart and Winston, New York, 1976). · Zbl 0413.90040
[17] C.L. Liu,Introduction to Combinatorial Mathematics (McCraw-Hill, New York, 1972).
[18] S.T. McCormick ”A combinatorial approach to some sparse matrix problems,” Ph.D. Thesis, Stanford University (Stanford, CA, 1983). · Zbl 0507.65027
[19] S.T. McCormick, ”Making sparse matrices sparser: Computational results,”Mathematical Programming 49 (1990) 91–111. · Zbl 0714.90067 · doi:10.1007/BF01588780
[20] S.T. McCormick and S.F. Chang, ”The weighted sparsity problem: Complexity and algorithms,” Working Paper 90-MCS-007, Faculty of Commerce, University of British Columbia (Vancouver, BC, 1990).
[21] K. Murota, ”Sparsity and block-triangularization,” Research Memorandum RMI 87-07, Department of Mathematical Engineering and Information Physics, University of Tokyo (Tokyo, Japan, 1987).
[22] B.A. Murtagh and M.A. Saunders, ”MINOS 5.0 user’s guide,” Technical Report SOL 83-20, Systems Optimization Laboratory, Department of Operations Research, Stanford University (Stanford, CA, 1983).
[23] C.H. Papadimitriou and K. Steiglitz,Combinatorial Optimization:Algorithms and Complexity (Prentice Hall, Englewood Cliffs, NJ, 1982). · Zbl 0503.90060
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.