Vector processing in simplex and interior methods for linear programming

1. I. Adler, M.G.C. Resende and G. Veiga, An implementation of Karmarkar's algorithm for linear programming, Report ORC 86-8, Dept. of IE/OR, University of California, Berkeley, CA (1986).

   Google Scholar 

2. I. Adler, N. Karmarkar, M.G.C. Resende and G. Veiga, Data structures and programming techniques for the implementation of Karmarkar's algorithm, Technical Report, Dept. of IE/OR, University of California, Berkeley, CA (1987).

   Google Scholar 

3. C.C. Ashcraft, R.G. Grimes, J.G. Lewis, B.W. Peyton and H.D. Simon, Progress in sparse matrix methods for large linear systems on vector supercomputers, Int. J. Supercomputer Appl. 1(1987)10–30.

   Article  Google Scholar 

4. E.M.L. Beale, Advanced algorithmic features for general mathematical programming systems, in:Integer and Nonlinear Programming, ed. J. Abadie (North-Holland, Amsterdam, 1970) pp. 119–137.

   Google Scholar 

5. M. Benichou, J.M. Gauthier, G. Hentges and G. Ribière, The efficient solution of large-scale linear programming problems — some algorithmic techniques and computational results, Math. Progr. 13(1977)280–322.

   Article  Google Scholar 

6. W. Buchholz, The IBM System/370 vector architecture, IBM Systems J. 25(1986)51–62.

   Google Scholar 

7. D. Carstens, Parallel processing for large scale linear programming and other application programs, Paper presented at the ORSA/TIMS Joint National Meeting, Los Angeles, CA (1978).

8. R.S. Clark and T.L. Wilson, Vector system performance of the IBM 3090, IBM System J. 25(1986)63–82.

   Article  Google Scholar 

9. G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963).

   Google Scholar 

10. J.J. Dongarra, Designing algorithms for dense linear algebra problems on high performance computers, Paper presented at the Workshop on Supercomputers and Large Scale Optimization, University of Minnesota (1988).

11. J.J. Dongarra, F.G. Gustavson and A. Karp, Implementing linear algebra algorithms for dense matrices on a vector pipeline machine, SIAM Rev. 26(1984)91–112.

    Article  Google Scholar 

12. I.S. Duff, Parallel implementation of multifrontal schemes, Parallel Computing 3(1986)193–204.

    Article  MathSciNet  Google Scholar 

13. I.S. Duff, The use of vector and parallel computers in the solution of large sparse linear equations, AERE-R.12393, Harwell Laboratory, Oxfordshire, UK (1986).

    Google Scholar 

14. I.S. Duff, A.M. Erisman and J.K. Reid,Direct Methods for Sparse Matrices (Oxford University Press, London, 1986).

    Google Scholar 

15. I.S. Duff and J.K. Reid, The multifrontal solution of indefinite sparse symmetric linear systems, ACM Trans. Math. Softw. 9(1983)302–325.

    Article  Google Scholar 

16. J.J.H. Forrest, Linear programming using IBM 3090 vector facility, Paper presented at the E.M.L. Beale Memorial Symp., The Royal Society, London (1987).

    Google Scholar 

17. J.J.H. Forrest and J.A. Tomlin, Updating triangular factors of the basis to maintain sparsity in the product form simplex method, Math. Progr. 2(1972)263–278.

    Article  Google Scholar 

18. K. Gallivan, W. Jalby and U. Meier, The use of BLAS3 in linear algebra on a parallel processor with a hierarchical memory, SIAM J. Sci. Stat. Comput. 8(1987)1079–1084.

    Article  Google Scholar 

19. D.M. Gay, Massive memory buys little speed for complete, in-core sparse Cholesky factorization, Numerical Analysis Manuscript 88-04, AT&T Bell Laboratories, Murray Hill, NJ. Presented at the 25th ORSA/TIMS Joint Meeting, Washington, D.C. (1988).

20. J.A. George and J.W. Liu,Computer Solution of Large Sparse Positive Definite Systems (Prentice-Hall, Englewood Cliffs, NJ, 1981).

    Google Scholar 

21. P.E. Gill, W. Murray, M.A. Saunders, J.A. Tomlin and M.H. Wright, On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method, Math. Progr. 36(1986)183–209.

    Google Scholar 

22. D. Goldfarb and S. Mehrotra, Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective function value, Math. Progr. 40(1988)183–195.

    Article  Google Scholar 

23. G.H. Golub and C.F. Van Loan,Matrix Computations (North Oxford Academic, Oxford, and John Hopkins Press, Baltimore, 1983).

    Google Scholar 

24. F.G. Gustavson, W.M. Liniger and R.A. Willoughby, Symbolic generation of an optimal Crout algorithm for sparse systems of linear equations, J. ACM 17(1970)87–109.

    Article  Google Scholar 

25. P.M.J. Harris, Pivot selection methods of the Devex LP code, Math. Progr. 5(1973)1–28.

    Article  Google Scholar 

26. IBM Corporation, IBM system/370 vector operations. Publication no. SA22-7125-2 (1986).

27. IBM Corporation, Engineering and Scientific Subroutine Library, guide and reference. Publication no. SC23-0184-2 (1987).

28. C.H. Johnson and E.P. Willard, TIMPS/ASC — An MPS implementation on a pipeline computer, Paper presented at the 8th Int. Symp. on Mathematical Programming, Stanford, CA (1973).

29. J.E. Kalan, Machine inspired enhancements of the simplex algorithm, Technical Report CS75001-R, Virginia Polytechnic Institute, Blacksburg, VA (1975).

    Google Scholar 

30. N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4(1984)373–395.

    Google Scholar 

31. J.G. Lewis and H.D. Simon, The impact of hardware gather/scatter on sparse Gaussian elimination, Boeing Computer Services, Mathematics and Modeling, Technical Report ETA-TR-33, Seattle, WA (1986).

32. K. McShane, C. Monma and D. Shanno, An implementation of a primal-dual interior point method for linear programming, Technical Report, Rutgers University, New Brunswick, NJ (1988).

    Google Scholar 

33. Wm. Orchard-Hays,Advanced Linear Programming Computing Techniques (McGraw-Hill, New York, 1968).

    Google Scholar 

34. C.C. Paige and M.A. Saunders, LSQR: An algorithm for sparse linear equations and sparse least-squares, ACM Trans. on Math. Softw. 8(1982)43–71.

    Article  Google Scholar 

35. C.E. Pfefferkorn and J.A. Tomlin, Design of a linear programming system for the ILLIAC IV, Technical Report SOL 76-8, Dept. of Operations Research, Stanford University, and Technical Report 5487, NASA-Ames Institute for Advanced Computation, Sunnyvale, CA (1976).

    Google Scholar 

36. J.K. Reid, FORTRAN subroutines for handling sparse linear programming bases, Report AERE-R.8269, Harwell Laboratory, Oxfordshire, UK (1976).

    Google Scholar 

37. J.K. Reid, A sparsity exploiting variant of the Bartels-Golub decomposition for linear programming bases, Math. Progr. 24(1982)55–69.

    Article  Google Scholar 

38. U.H. Suhl and L. Aittoniemi, Computing sparseLU-factorizations for large-scale linear programming bases, Arbeitspapier Nr. 58/87, Fachbereich Wirtschaftswissenschaft, Angewandte Informatik, Freie Universität Berlin (1987).

39. J.A. Tomlin, A note on comparing simplex and interior methods for linear programming, in:Progress in Mathematical Programming, ed. N. Megiddo (Springer-Verlag, New York, 1988) pp. 91–103.

    Google Scholar 

40. J.A. Tomlin and J.S. Welch, Implementing an interior point method in a mathematical programming system, Paper presented at the 22nd TIMS/ORSA Joint Meeting, Miami, FL (1986).

Download references