zbMATH — the first resource for mathematics

Computing projections for the Karmarkar algorithm. (English) Zbl 0729.65043
For computing the projection of a vector onto the nullspace of a matrix some alternatives are considered. Especially the sparsity of the computed matrices is investigated. The author works with an extended but indefinite matrix which is usually sparser than the originally used normal matrix. For the solution process a subroutine from Harwell is modified. Computational results are given for twelve test problems in the Netlib test set. These results indicate a computational advantage for factoring the extended matrix.
Reviewer: J.Terno (Dresden)

65K05 Numerical mathematical programming methods
90C05 Linear programming
Full Text: DOI
[1] Dennis, J.E.; Morshedi, A.M.; Turner, Kathryn, A variable-metric variant of the karmarkar algorithm for linear programming, Math. programming, 1, 1-20, (1987) · Zbl 0635.90058
[2] Dennis, J.E.; Schnabel, Robert B., Numerical methods for unconstrained optimization and nonlinear equations, (1983), Prentice-Hall Englewood Cliffs, N.J · Zbl 0579.65058
[3] Duff, I.S.; Reid, J.K., MA27—A set of Fortran subroutines for solving sparse symmetric sets of linear equations, () · Zbl 0515.65022
[4] Duff, I.S.; Reid, J.K., The multifrontal solution of indefinite sparse symmetric linear equations, AMS trans. math. software, 9, 3, 302-325, (1983), (Sept.) · Zbl 0515.65022
[5] Duff, I.S.; Gould, N.I.M.; Reid, J.K.; Scott, J.A.; Turner, K., The factorization of sparse symmetric indefinite matrices, (), IMA. J. Numer. Anal., to appear · Zbl 0739.65018
[6] Gay, David M., Electronic mail distribution of linear programming test problems, Committee on algorithms newsletter, math. programming soc., 13, (1985), Dec.
[7] Karmarkar, Narendra, A new polynomial-time algorithm for linear programming, Combinatorica, 4, 373-395, (1984) · Zbl 0557.90065
[8] Todd, Michael J.; Burrell, Bruce P., An extension of Karmarkar’s algorithm for linear programming using dual variables, Algorithmica, 1, 409-424, (1986) · Zbl 0621.90048
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.