maspack.solvers

Class KellerLCPSolver

java.lang.Object

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

Nested Classes

Modifier and Type	Class and Description
static class	KellerLCPSolver.Status Described whether or not a solution was found.

Field Summary

Fields

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 Summary

Constructors

Constructor and Description
KellerLCPSolver() Creates a new Keller solver.

Method Summary

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

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 solve).

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