Accession Number:

ADA136405

Title:

Linear Complementarity Problems Solvable by an Efficient Polynomially Bounded Pivoting Algorithm.

Descriptive Note:

Technical summary rept.,

Corporate Author:

WISCONSIN UNIV-MADISON MATHEMATICS RESEARCH CENTER

Personal Author(s):

Report Date:

1983-11-01

Pagination or Media Count:

32.0

Abstract:

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.

Subject Categories:

  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE