Sparse Matrix Ordering Methods for Interior Point Linear Programming

References

• Amestoy P. , Davis T. , Duff I. An Approximate Minimum Degree Ordering Algorithm. (1994) . Technical report TR-94-039, University of Florida Google Scholar
• Ashcraft C. , Liu J. A Partition Improvement Algorithm for Generalized Nested Dissection. (1994) . Technical report BCSTECH-94-020, Boeing Computer Services Google Scholar
• Ashcraft C. , Liu J. Robust Ordering of Sparse Matrices using Multisection. (1996) . Technical report ISSTECH-96-002, Boeing Information and Support Services Google Scholar
• Ashcraft C. , Liu J. Using Domain Decomposition to Find Graph Bisectors. (1995) . Technical report ISSTECH-95-024, Boeing Information and Support Services Google Scholar
• Berger A. , Mulvey J. , Rothberg E. , Vanderbei R. Solving Multistage Stochastic Programs using Tree Dissection. (1995) . Technical report SOR-95-07, Dept. of Statistics and Operations Research, Princeton University Google Scholar
• Bisseling R. , Doup T. , Loyens L. A Parallel Interior Point Algorithm for Linear Programming on a Network of Transputers. Annals of Operations Research (1993) 43 51 86 Crossref, Google Scholar
• Bui T. , Jones C. A Heuristic for Reducing Fill in Sparse Matrix Factorization. 6th SIAM Conference on Parallel Processing for Scientific Computing (1993) (SIAM, Philadelphia, PA) Google Scholar
• Fiduccia C. , Mattheyses R. A Linear Time Heuristic for Improving Network Partitions. Proceedings of the 19th IEEE Design Automation Conference (1982) 175 181 Crossref, Google Scholar
• Gay D. Electronic Mail Distribution of Linear Programming Test Problems. Mathematical Programming Society (COAL) Newsletter (1985) 13 10 12 Google Scholar
• George A. , Liu J. An Automated Nested Dissection Algorithm for Irregular Finite Element Problems. SIAM J. Numer. Anal. (1978) 15 1053 1069 Crossref, Google Scholar
• George A. , Liu J. Computer Solution of Large Sparse Positive Definite Systems (1981) (Prentice-Hall, Englewood Cliffs, NJ) Google Scholar
• George A. , Liu J. The Evolution of the Minimum Degree Ordering Algorithm. SIAM Review (1989) 31 1 19 Crossref, Google Scholar
• Gupta A. Graph Partitioning Based Sparse Matrix Ordering Algorithms for Interior-Point Methods. (1996) . Technical report RC 20467, IBM T.J. Watson Research Center, Yorktown Heights, NY Google Scholar
• Hendrickson B. , Leland R. The Chaco User's Guide: Version 2.0. (1994) . Technical report SAND94-2692, Sandia National Laboratories, Albuquerque, NM Google Scholar
• Hendrickson B. , Leland R. A Multilevel Algorithm for Partitioning Graphs. Proceedings in Supercomputing '95 (1995) (IEEE Computer Society Press, Los Alamitos, CA) Crossref, Google Scholar
• Hendrickson B. , Rothberg E. Improving the Runtime and Quality of Nested Dissection Ordering. (1996) . Technical report SAND96-0868J, Sandia National Laboratories, Albuquerque, NM Google Scholar
• Karypis G. , Gupta A. , Kumar V. A Parallel Formulation of Interior Point Algorithms. Proceedings of Supercomputing '94 (1994) (IEEE Computer Society Press, Los Alamitos, CA) 204 213 Crossref, Google Scholar
• Karypis G. , Kumar V. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. (1995) . Technical report 95-035, Department of Computer Science, University of Minnesota Google Scholar
• Kernighan B. , Lin S. An Efficient Heuristic Procedure for Partitioning Graphs. Bell System Techical Journal (1978) 29 291 307 Google Scholar
• Liu J. A Graph Partitioning Algorithm by Node Separators. ACM Transactions on Mathematical Software (1989) 15 198 219 Crossref, Google Scholar
• Liu J. Modification of the Minimum Degree Algorithm by Multiple Elimination. ACM Transactions on Mathematical Software (1985) 11 141 153 Crossref, Google Scholar
• Lustig I. , Marsten R. , Shanno D. Computational Experience with a Primal-dual Interior Point Method for Linear Programming. Linear Algebra and Its Applications (1991) 152 191 222 Crossref, Google Scholar
• Lustig I. , Marsten R. , Shanno D. Interior Point Methods for Linear Programming: Computational State of the Art. ORSA Journal on Computing (1994) 6 1 14 Link, Google Scholar
• Lustig I. , Rothberg E. Gigaflops in Linear Programming. OR Letters (1996) 18 157 165 Crossref, Google Scholar
• Markowitz H. The Elimination Form of the Inverse and Its Application to Linear Programming. Management Science (1957) 3 255 269 Link, Google Scholar
• Pothen A. , Fan C. Computing the Block Triangular Form of a Sparse Matrix. ACM Transactions on Mathematical Software (1990) 16 303 324 Crossref, Google Scholar
• Pothen A. , Rothberg E. , Simon H. , Wang L. Parallel Sparse Cholesky Factorization with Spectral Nested Dissection Ordering. Proceedings of the 5th SIAM Conference Applied Linear Algebra (1994) (SIAM, Philadelphia, PA) 418 422 Google Scholar
• Pothen A. , Simon H. , Liou K. Partitioning Sparse Matrices with Eigenvectors of Graphs. SIAM Journal of Matrix Analysis and Applications (1990) 11 430 452 Crossref, Google Scholar
• Pothen A. , Simon H. , Wang L. , Barnard S. Towards a Fast Implementation of Spectral Nested Dissection. Proceedings of Supercomputing '92 (1992) (IEEE Computer Society Press, Los Alamitos, CA) 42 51 Crossref, Google Scholar
• Rothberg E. (1996) . Ordering Sparse Matrices using Approximate Minimum Local Fill, Silicon Graphics manuscript, submitted for publication Google Scholar
• Tinney W. Comments on using Sparsity Techniques for Power System Problems. Sparse Matrix Proceedings (1969) . IBM Research Report RAI 3-12-69 Google Scholar