×

zbMATH — the first resource for mathematics

Splitting dense columns in sparse linear systems. (English) Zbl 0727.65034
Let \(A=[S,D]\) where S and D denote respectively the sparse and dense columns of a matrix A. The author gives an efficient and robust method for solving \(AA^ Tx=b.\) The proposed method avoids the rank-deficiency problem that is common to the present algorithms and also makes an effective use of sparse matrix techniques. Applications to interior-point methods for linear programming and non-symmetric matrices are pointed out.

MSC:
65F30 Other matrix algorithms (MSC2010)
65F50 Computational methods for sparse matrices
65K05 Numerical mathematical programming methods
Software:
ALPO
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Gill, P.E.; Murray, W.; Saunders, M.A.; Tomlin, J.A.; Wright, M.H., On projected Newton methods for linear programming and an equivalence to Karmarkar’s projective method, Math. programming, 36, 183-209, (1986) · Zbl 0624.90062
[2] Adler, I.; Karmarkar, N.K.; Resende, M.G.C.; Veiga, G., An implementation of Karmarkar’s algorithm for linear programming, Math. programming, 44, 297-335, (1989) · Zbl 0682.90061
[3] Adler, I.; Karmarkar, N.K.; Resende, M.G.C.; Veiga, G., Data structures and programming techniques for the implementation of Karmarkar’s algorithm, ORSA J. comput., 1, 84-106, (1989) · Zbl 0752.90043
[4] Mehrotra, S., Implementations of affine scaling methods: approximate solutions of systems of linear equations using preconditioned conjugate gradient methods, () · Zbl 0782.90067
[5] Choi, I.C.; Monma, C.L.; Shanno, D.F., Further development of a primal-dual interior point method, () · Zbl 0757.90051
[6] Gill, P.E.; Murray, W.; Saunders, M.A., A single-phase dual barrier method for linear programming, () · Zbl 0815.65080
[7] Lustig, I.J.; Marsten, R.E.; Shanno, D.F., Computational experience with a primal-dual interior point method for linear programming, () · Zbl 0731.65049
[8] Marsten, R.E.; Saltzman, M.J.; Shanno, D.F.; Pierce, G.S.; Ballintijn, J.F., Implementation of a dual interior point algorithm for linear programming, () · Zbl 0752.90046
[9] McShane, K.A.; Monma, C.L.; Shanno, D.F., An implementation of a primal-dual interior point method for linear programming, ORSA J. comput., 1, 70-83, (1989) · Zbl 0752.90047
[10] Lustig, I.J.; Marsten, R.E.; Shanno, D.F., On implementing Mehrotra’s predictor-corrector interior point method for linear programming, () · Zbl 0771.90066
[11] Vanderbei, R.J., {\scalpo}: another linear program optimizer, () · Zbl 0777.90031
[12] Lustig, I.J.; Mulvey, J.M.; Carpenter, T.J., Formulating stochastic programs for interior point methods, () · Zbl 0739.90048
[13] Vanderbei, R.J., A brief description of {\scalpo}, () · Zbl 0446.90045
[14] Gay, D.M., Electronic mail distribution of linear programming test problems, Math. programming soc. COAL newslett., (1985)
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.