Two-level Algorithm for Linear Complementarity Problem
In many applications, the variational inequality from the previous section
reduces to a linear complementarity problem with a large and sparse matrix.
Since one has to solve this problem in each iteration step of the
BT
code, it is very important to have an efficient method for solving it.
In Kocvara-Zowe (1994)
we proposed and implemented an iterative algorithm for solving the above
linear complementarity problems; each step of the algorithm combines an application
of the successive overrelaxation method with projection (to determine an approximation
of the optimal active set) with the preconditioned conjugate gradient method
(to solve the reduced residual systems of linear equations). Convergence
of the iterates to the solution was proved. In the experimental part we compared
the efficiency of the algorithm with several other methods. As test example
we considered the obstacle problem with different obstacles. For problems
of dimension up to 24000 variables, the algorithm finds the solution in less
then 7 iterations, where each iteration requires about 10 matrix-vector multiplications;
this is considerably better than other results reported in literature.
Michal Kocvara
March 1, 2001