maspack.solvers
Class KellerLCPSolver

java.lang.Object
  extended by maspack.solvers.KellerLCPSolver

public class KellerLCPSolver
extends java.lang.Object

Solves linear complementarity problems (LCPs) for symmetric positive semi-definite (SPSD) matrices using Kellers's method. An LCP is defined by the linear system

 w = M z + q
 
and solving it entails finding w and z subject to the constraints
                  T
 w >= 0, z >= 0, w z = 0
 
Keller'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.


Nested Class Summary
static class KellerLCPSolver.Status
          Described whether or not a solution was found.
 
Field Summary
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 Summary
KellerLCPSolver()
          Creates a new Keller solver.
 
Method Summary
 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
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

SHOW_NONE

public static final int SHOW_NONE
See Also:
Constant Field Values

SHOW_PIVOTS

public static final int SHOW_PIVOTS
See Also:
Constant Field Values

SHOW_MIN_RATIO

public static final int SHOW_MIN_RATIO
See Also:
Constant Field Values

SHOW_QM

public static final int SHOW_QM
See Also:
Constant Field Values

SHOW_ALL

public static final int SHOW_ALL
See Also:
Constant Field Values

Z_FREE

public static final int Z_FREE
See Also:
Constant Field Values

Z_UPPER_BOUNDED

public static final int Z_UPPER_BOUNDED
See Also:
Constant Field Values

Z_LOWER_BOUNDED

public static final int Z_LOWER_BOUNDED
See Also:
Constant Field Values
Constructor Detail

KellerLCPSolver

public KellerLCPSolver()
Creates a new Keller solver.

Method Detail

getDebug

public int getDebug()

setDebug

public void setDebug(int code)

getTolerance

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

Returns:
numeric tolerance
See Also:
setTolerance(double)

setTolerance

public void setTolerance(double tol)
Sets the numeric tolerance for this solver. This is used to determine when q' >= 0, as described in the class documentation. In particular, a solution will be considered found whenever q' >= -tol.

Parameters:
tol - new numeric tolerance. Negative numbers will be truncated to 0.
See Also:
getTolerance()

getIterationLimit

public int getIterationLimit()
Gets the iteration limit for this solver. This value multiplied by the size of the LCP matrix gives the maximum number of iterations allowed for the solver.

Returns:
iteration limit

setIterationLimit

public void setIterationLimit(int limit)
Sets the iteration limit for this solver. This value multiplied by the size of the LCP matrix gives the maximum number of iterations allowed for the solver. The maximum number of iterations is specified in this way because the expected number of iterations for Keller's algorithm is proportional to the size of the LCP matrix.

Parameters:
limit - new iteration limit

getIterationCount

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

Returns:
iteration count for last solution

solve

public KellerLCPSolver.Status solve(VectorNd z,
                                    MatrixNd M,
                                    VectorNd q,
                                    boolean[] zBasic)
Solves the LCP
 w = M z + q
 
where M is SPSD. It is possible to use this routine to solve a mixed LCP, by pre-pivoting M and q to make the relevant non-LCP z variables basic and presetting the corresponding entries for these variables in zBasic to true.

Parameters:
z - returns the solution for z
M - system matrix
q - system vector
zBasic - 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.
Returns:
Status of the solution.

solve

public 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.

Parameters:
zsol - returns the solution for z
Mbuf - system matrix, stored in row-major order
qbuf - system vector
zBasic - identifies which z variables are basic in the solution (see
n - size of the LCP system
Returns:
Status of the solution.

mulPivotedMatrix

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

Parameters:
res - used to store result
vec - vector to be multiplied

mulPivotedMatrix

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

Parameters:
MR - matrix result
M1 - matrix to be multiplied