
An analysis of ill-conditioned linear systems with large, sparse and symmetric matrix that arise in primal-dual interior-point methods for linear programming is carried out. The linear systems based on augmented system formulation are examined and it is observed how various standard factorization algorithms (the Bunch-Parlett, Bunch-Kaufman, and sparse Bunch-Parlett algorithms) for the system behave as its ill-conditioning grows without bound. Numerical experiments indicate that for degenerate linear programming problems the computed search direction is so inaccurate that the interior-point method can move only a tiny distance along it but if the underlying linear program has a unique primal-dual solution then steps produced by standard factorization are often accurate enough to converge to high accuracy. The effects of roundoff errors are tracked by using standard techniques from backward error analysis.
primal-dual interior-point methods, linear programming, stability, factorization algorithms, Direct numerical methods for linear systems and matrix inversion, augmented system factorizations, large, sparse and symmetric matrix, Numerical mathematical programming methods, Linear programming, ill-conditioned linear systems, backward error analysis, numerical experiments
primal-dual interior-point methods, linear programming, stability, factorization algorithms, Direct numerical methods for linear systems and matrix inversion, augmented system factorizations, large, sparse and symmetric matrix, Numerical mathematical programming methods, Linear programming, ill-conditioned linear systems, backward error analysis, numerical experiments
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 75 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
