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) : Pang,J

PDF Url : ADA136405

Report Date : Nov 1983

Pagination or Media Count : 32

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 0(sq n) arithmetic operations, the total computational complexity of the algorithm for solving these linear complementarity problems is no more than 0(cu m). In one of the two classes of problems being studied, the complexity is 0(sq n ) because the matrix involved is 5-diagonal which allows each pivot to be performed in linear time. Some discussion in connection with Lemke's well-known almost complementary pivoting algorithm is also addressed.

Descriptors :   *Algorithms, *Problem solving, *Linear systems, Equations, Polynomials, Matrices(Mathematics), Computations, Parametric analysis, Linear regression analysis

Subject Categories : Statistics and Probability

Distribution Statement : APPROVED FOR PUBLIC RELEASE