public class KellerLCPSolver
extends java.lang.Object
w = M z + qand solving it entails finding w and z subject to the constraints
T w >= 0, z >= 0, w z = 0Keller's method does this by a series of pivoting operations. Each pivot corresponds to one solver iteration and entails the exchange of a single variable w_i with its complementary counterpart z_i. A sequence of pivots results in the pivoted system
w' = M' z' + q'where w' and z' contain complementary combinations of the w and z variables. Any variable (w or z) contained in w' is called a basic variable. When a pivoted system is found for which q'
>=
0, this provides a solution to
the LCP in which the z and w variables comprising z' are 0 and the z and w
variables comprising w' are equal to the corresponding entries in q'. As
mentioned above, Dantzig's method only works when M is SPSD.
Full details on the solution of LCPs can be found in The Linear Complementarity Problem, by Cottle, Pang, and Stone. Details on Keller's method can be found in Claude Lacoursiere's Ph.D. thesis. Ghosts and Machines: Regularized Variational Methods for Interactive Simulations of Multibodies with Dry Frictional Contact.
Modifier and Type  Class and Description 

static class 
KellerLCPSolver.Status
Described whether or not a solution was found.

Modifier and Type  Field and Description 

static int 
SHOW_ALL 
static int 
SHOW_MIN_RATIO 
static int 
SHOW_NONE 
static int 
SHOW_PIVOTS 
static int 
SHOW_QM 
static int 
Z_FREE 
static int 
Z_LOWER_BOUNDED 
static int 
Z_UPPER_BOUNDED 
Constructor and Description 

KellerLCPSolver()
Creates a new Keller solver.

Modifier and Type  Method and Description 

int 
getDebug() 
int 
getIterationCount()
Returns the number of iterations, or pivots, that were used in the most
recent solution operation.

int 
getIterationLimit()
Gets the iteration limit for this solver.

double 
getTolerance()
Returns the numeric tolerence for this solver.

void 
mulPivotedMatrix(double[] res,
double[] vec)
Multiplies the pivoted system matrix, produced by the last solve, by a
vector.

void 
mulPivotedMatrix(MatrixNd MR,
MatrixNd M1)
Multiplies the pivoted system matrix, produced by the last solve, by
another matrix.

void 
setDebug(int code) 
void 
setIterationLimit(int limit)
Sets the iteration limit for this solver.

void 
setTolerance(double tol)
Sets the numeric tolerance for this solver.

KellerLCPSolver.Status 
solve(double[] zsol,
double[] Mbuf,
double[] qbuf,
boolean[] zBasic,
int n)
Identical in function to
solve , but uses arrays
instead of VectorNd and MatrixNd objects to pass arguments. 
KellerLCPSolver.Status 
solve(VectorNd z,
MatrixNd M,
VectorNd q,
boolean[] zBasic)
Solves the LCP

public static final int SHOW_NONE
public static final int SHOW_PIVOTS
public static final int SHOW_MIN_RATIO
public static final int SHOW_QM
public static final int SHOW_ALL
public static final int Z_FREE
public static final int Z_UPPER_BOUNDED
public static final int Z_LOWER_BOUNDED
public int getDebug()
public void setDebug(int code)
public double getTolerance()
setTolerance(double)
public void setTolerance(double tol)
>=
0, as described in the class documentation. In particular, a
solution will be considered found whenever q' >=
tol.tol
 new numeric tolerance. Negative numbers will be truncated to 0.getTolerance()
public int getIterationLimit()
public void setIterationLimit(int limit)
limit
 new iteration limitpublic int getIterationCount()
public KellerLCPSolver.Status solve(VectorNd z, MatrixNd M, VectorNd q, boolean[] zBasic)
w = M z + qwhere M is SPSD. It is possible to use this routine to solve a mixed LCP, by prepivoting M and q to make the relevant nonLCP z variables basic and presetting the corresponding entries for these variables in zBasic to true.
z
 returns the solution for zM
 system matrixq
 system vectorzBasic
 On output, identifies which z variables are basic in the solution. On
input, identifies z variables which have been made basic as part of
solving a mixed LCP. If the LCP is not mixed, then all entries in this
array should be set to false.public KellerLCPSolver.Status solve(double[] zsol, double[] Mbuf, double[] qbuf, boolean[] zBasic, int n)
solve
, but uses arrays
instead of VectorNd and MatrixNd objects to pass arguments.zsol
 returns the solution for zMbuf
 system matrix, stored in rowmajor orderqbuf
 system vectorzBasic
 identifies which z variables are basic in the solution (see
solve
).n
 size of the LCP systempublic void mulPivotedMatrix(double[] res, double[] vec)
res
 used to store resultvec
 vector to be multiplied