
Accession Number : ADA136405
Title : Linear Complementarity Problems Solvable by an Efficient Polynomially Bounded Pivoting Algorithm.
Descriptive Note : Technical summary rept.,
Corporate Author : WISCONSIN UNIVMADISON 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 5diagonal which allows each pivot to be performed in linear time. Some discussion in connection with Lemke's wellknown 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