A parallel formulation of interior point algorithms

ABSTRACT

In this paper we describe a scalable parallel formulation of interior point algorithms. Through our implementation on a 256-processor nCUBE 2 parallel computer, we show that our parallel formulation utilizes hundreds of processors efficiently and delivers much higher performance and speedups than reported earlier. These speedups are a result of our highly efficient parallel algorithm for solving a linear symmetric positive definite system using Cholesky factorization. We also evaluate a number of ordering algorithms for sparse matrix factorization in terms of their suitability for parallel Cholesky factorization.

REFERENCES

• 1: Ilan Adler, Mauricio G.C. Resende, Geraldo Veiga, and Narendra Karmarkar. An Implementation of Karmarkar's Algorithm for Linear Programming. Mathematical Programming, (44):297-335, 1989.
• 2: Mokhtar S. Bazaraa , John J. Jarvis , Hanif D. Sherali, Linear programming and network flows (2nd ed.), John Wiley & Sons, Inc., New York, NY, 1990
• 3: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and distributed computation: numerical methods, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 4: R. H. Bisseling, T. M. Doup, and L.D.J.C. Loyens. A parallel Interior Point algorithm for linear programming on a network of transputers. Annals of Operations Research, 43:51-86, 1993.
• 5: In Chan Choi, Clyde L. Monma, and David F. Shanno. Further Development of a Primal-Dual Interior Point Method. ORSA Journal on Computing, 2(4):304-311, Fall 1990.
• 6: G. B. Dantzig. Linear Programming and Extensions. Princeton University Press, Princeton, NJ, 1963.
• 7: I. S. Duff , J. K. Reid, The Multifrontal Solution of Indefinite Sparse Symmetric Linear, ACM Transactions on Mathematical Software (TOMS), v.9 n.3, p.302-325, Sept. 1983 [doi>10.1145/356044.356047]
• 8: Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986
• 9: J. Eckstein, L. C. Polymenakos, R. Qi, V. I. Ragulin, and S. A. Zenios. Data-Parallel Implementations of Dense Linear Programming Algorithms. Technical Report TMC-230, Thinking Machines Corporations, Cambridge, MA, 1992.
• 10: Jonathan Eckstein. Large-Scale Parallel Computing, Optimization, and Operations Research: A survey. ORSA CSTS Newsletter, 14(2), Fall 1993.
• 11: Shu-Cherng Fang , Sarat Puthenpura, Linear optimization and extensions: theory and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 12: K. A. Gallivan, R. J. Plemons, and A. H. Sameh. Parallel Algorithms for Dense Linear Algebra Computations. In Parallel Algorithms for Matrix Computations, pages 1-82. SIAM, 1990.
• 13: D. M. Gay. Electronic Mail Distribution of Linear Programming Test Problems. <mathematical Programming Society COAL Newsletter, December 1985.
• 14: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 15: A. George , W. H. Liu, The evolution of the minimum degree ordering algorithm, SIAM Review, v.31 n.1, p.1-19, Mar. 1989 [doi>10.1137/1031001]
• 16: A. George, J. W.-H. Liu, and E. G.-Y. Ng. Communication Results for Parallel Sparse Cholesky Factorization on a Hypercube. Parallel Computing, 10(3):287-298, May 1989.
• 17: Anshul Gupta and Vipin Kumar. A scalable parallel algorithm for sparse matrix factorization. Technical Report 94-19, Department of Computer Science, University of Minnesota, Minneapolis, MN, 1994. A shorter version appears in Supercomputing '94. TR available in users/kumar/sparse-cholesky.ps at anonymous FTP site ftp.cs.umn.edu.
• 18: Michael T. Heath , Esmond Ng , Barry W. Peyton, Parallel algorithms for sparse linear systems, SIAM Review, v.33 n.3, p.420-460, Sept. 1991 [doi>10.1137/1033099]
• 19: H. F. Ho, G. H. Chen, S. H. Lin, and J. P. Sheu. Solving Linear Programming on Fixed-Size Hypercubes. In International Conference on Parallel Processesing, pages 112-116, 1988.
• 20: E. C. Housos, C. C. Huang, and J-M. Liu. Parallel Algorithms for the AT&T KORBX System. AT&T Technical Journal, 68(3):37-47, 1989.
• 21: J. Jess and H. Kees. A data structure for parallel L/U decomposition. IEEE Transactions on Computers, C-31:231-239, 1982.
• 22: Ho-Won Jung, Roy E. Marsten, and Matthew J. Saltzman. Numerical Factorization Methods for Interior Point Algorithms. ORSA Journal on Computing, 6(1):94-105, Winter 1994.
• 23: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• 24: George Karypis, Anshul Gupta, and Vipin Kumar. A Parallel Formulation of Interior Point Algorithms. Technical Report (TR 94-20), Department of Computer Science, University of Minnesota, Minneapolis, MN, 1994. Available via anonymous ftp from ftp.cs.umn.edu at users/kumar/interior-point.ps.
• 25: George Karypis and Vipin Kumar. A High Performance Sparse Cholesky Factorization Algorithm For Scalabale Parallel Computers. Technical Report 94-41, Department of Computer Science, University of Minnesota, Minneapolis, MN, 1994. Available via anonymous ftp from ftp.cs.umn.edu at users/kumar/cholesky-forest.ps.
• 26: George Karypis and Vipin Kumar. Performance and Scalability of Parallel Formulations of the Simplex Method for Dense Linear Programming Problems. Technical report, Computer Science Department, University of Minnesota, Minneapolis, MN, April 1994.
• 27: B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 1970.
• 28: Vipin Kumar , Ananth Grama , Anshul Gupta , George Karypis, Introduction to parallel computing: design and analysis of algorithms, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1994
• 29: J W H Liu, Computational models and task scheduling for parallel sparse Cholesky factorization, Parallel Computing, v.3 n.4, p.327-342, Oct. 1986 [doi>10.1016/0167-8191(86)90014-1]
• 30: J. W.-H. Liu. Reordering sparse matrices for parallel elimination. Parallel Computing, 11:73-91, 1989.
• 31: Joseph W. H. Liu, Equivalent sparse matrix reordering by elimination tree rotations, SIAM Journal on Scientific and Statistical Computing, v.9 n.3, p.424-444, May 1988 [doi>10.1137/0909029]
• 32: Joseph W. H. Liu, A graph partitioning algorithm by node separators, ACM Transactions on Mathematical Software (TOMS), v.15 n.3, p.198-219, Sept. 1989 [doi>10.1145/66888.66890]
• 33: J. W. Liu, The minimum degree ordering with constraints, SIAM Journal on Scientific and Statistical Computing, v.10 n.6, p.1136-1145, Nov. 1989 [doi>10.1137/0910069]
• 34: Joseph W. H. Liu, The role of elimination trees in sparse factorization, SIAM Journal on Matrix Analysis and Applications, v.11 n.1, p.134-172, January 1990 [doi>10.1137/0611010]
• 35: Joseph W. H. Liu, The multifrontal method for sparse matrix solution: theory and practice, SIAM Review, v.34 n.1, p.82-109, March 1992 [doi>10.1137/1034004]
• 36: Irvin J. Lustig, Roy E. Marssten, and David F. Shanno. Interior Point Methods for Linear Programming: Computational State of the Art. ORSA Journal on Computing, 6(1):1-14, Winter 1994.
• 37: Irvin J. Lustig, Roy E. Marsten, and David F. Shanno. Computational experience with a primal-dual interior-point method for linear programming. Journal of Linear Algebra and Its Applications, 152:191-222, 1991.
• 38: Irvin J. Lustig, Roy E. Marsten, and David F. Shanno. On Implementing Mehrotra's Predictor-Corrector Interior-Point Method for Linear Programming. SIAM J. Optimization, 2(3):435-449, August 1992.
• 39: Roy E. Marsten, Matthew J. Saltzman, David F. Shanno, George S. Pierce, and J. F. Ballintizn. Implementation of a Dual Affine Interior Point Algorithm for Linear Programming. ORSA Journal on Computing, 1(4):287-297, 1989.
• 40: Kevin A. McShane, Clyde L. Monma, and David Shanno. An Implementation of a Primal-Dual Interior Point Method for Linear Programming. ORSA Journal on Computing, 1(2):70-83, Spring 1989.
• 41: Sanjay Mehrotra. On the Implementation of a Primal-Dual Interior Point Method. SIAM J. Optimization, 2(4):575-601, November 1992.
• 42: K. Onaga and H. Nagayasu. A Wavefront-Driven Algorithm for Linear Programming on Dataflow Processor-Arrays. In Proceedings of International Computer Symposium, pages 739-746, 1984.
• 43: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 44: F. Peters. Parallel pivoting algorithms for sparse symmetric matrices. Parallel Computing, 1:99-110, 1984.
• 45: Alex Pothen , Horst D. Simon , Kan-Pu Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal on Matrix Analysis and Applications, v.11 n.3, p.430-452, Jul. 1990 [doi>10.1137/0611030]
• 46: M. J. Saltzman. Implementation of an Interior Point LP Algorithm on a Shared-Memory Vector Multiprocessor. In R. Sharda, O. Balci, and S. A. Zenios, editors, Computer Science and Operations Research: New Developments in their Interface. Pergamon Press, 1992.
• 47: Wei Shu and Min-You Wu. Sparse Implementation of Revised Simplex Algorithm on Parallel Computers. In SIAM Conference on Parallel Processing for Scientific Computing, March 1993.
• 48: C. B. Stunkel , D. A. Reed, Hypercube implementation of the simplex algorithm, Proceedings of the third conference on Hypercube concurrent computers and applications, p.1473-1482, January 1989, Pasadena, California, United States [doi>10.1145/63047.63104]
• 49: Robert J. Vanderbei. LOQO User's Manual. Princeton University, Princeton, NJ, November 1992.
• 50: Robert J. Vanderbei. ALPO: Another Linear Program Optimizer. ORSA Journal on Computing, 5(2):134-146, Spring 1993.
• 51: M. Yannakakis. Computing the minimum fill-in is NP-complete. SIAM J. Algebraic Discrete Methods, 2:77-79, 1981.