Linear Complementarity Problems Solvable by an Efficient Polynomially Bounded Pivoting Algorithm.
Technical summary rept.,
WISCONSIN UNIV-MADISON MATHEMATICS RESEARCH CENTER
Pagination or Media Count:
Applied to two important classes of linear complementarity problems defined by an n x n matrix, the parametric principal pivoting algorithm, using a suitably chosen and easily computable parametric vector, terminates with a desired solution after at most n pivot operations. Since each pivot can be performed using at most 0sq n arithmetic operations, the total computational complexity of the algorithm for solving these linear complementarity problems is no more than 0cu m. In one of the two classes of problems being studied, the complexity is 0sq n because the matrix involved is 5-diagonal which allows each pivot to be performed in linear time. Some discussion in connection with Lemkes well-known almost complementary pivoting algorithm is also addressed.
- Statistics and Probability