maspack.solvers

Class MurtyLCPSolver

java.lang.Object

maspack.solvers.MurtyLCPSolver

All Implemented Interfaces:

LCPSolver

public class MurtyLCPSolver
extends java.lang.Object
implements LCPSolver

Solves linear complementarity problems (LCPs) and bounded linear complementarity problems (BLCPs) for symmetric positive definite (SPD) matrices using Murty's method. Details on Murty'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, as well as in ``Algorithms for Linear Complementarity Problems'', by Joaquim Judice (1994).

Nested Class Summary

Nested classes/interfaces inherited from interface maspack.solvers.LCPSolver

LCPSolver.Status

Field Summary

Fields

Modifier and Type	Field and Description
static int	SHOW_ALL
static int	SHOW_BLOCK_PIVOT_CHANGE
static int	SHOW_NONE
static int	SHOW_PIVOTS
static int	SHOW_RETURNS
static int	SHOW_TOL_UPDATE
static int	SHOW_VARIABLES

Fields inherited from interface maspack.solvers.LCPSolver

INF, W_VAR_LOWER, W_VAR_UPPER, Z_VAR

Constructor Summary

Constructors

Constructor and Description
MurtyLCPSolver()

Method Summary

Modifier and Type	Method and Description
boolean	getBlockPivoting()
boolean	getComputeResidual()
int	getDebug()
int	getIterationCount() Returns the number of iterations that were used in the most recent solution operation.
int	getIterationLimit() Gets the iteration limit for this solver.
boolean	getLastBlockPivoting()
double	getLastSolveTol() Returns the numeric tolerance used to determine complementarity for the most recent solution.
int	getPivotCount() Returns the number of pivots that were used in the most recent solution operation.
double	getResidual()
boolean	getSilent()
double	getTolerance() Returns the numeric tolerence for this solver.
boolean	isBLCPSupported() Queries whether this solver supported the solution of bounded linear complementarity problems (BLCPs).
boolean	isWarmStartSupported() Queries whether this solver supports warm starts.
int	numFailedPivots() Returns the number of pivots that were attempted and rejected because they would have resulted in a basis matrix that was not SPD.
void	setBlockPivoting(boolean enable)
void	setComputeResidual(boolean enable)
void	setDebug(int code)
void	setIterationLimit(int limit) Sets the iteration limit for this solver.
void	setSilent(boolean code)
void	setTolerance(double tol) Sets the numeric tolerance for this solver.
LCPSolver.Status	solve(VectorNd z, VectorNd w, VectorNi state, MatrixNd M, VectorNd q, VectorNd lo, VectorNd hi, int nub) If LCPSolver.isBLCPSupported() returns true, solves the BLCP
LCPSolver.Status	solve(VectorNd z, VectorNi state, MatrixNd M, VectorNd q) Solves the LCP

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface maspack.solvers.LCPSolver

clearState, stateToChar, stateToString, stateToString, stateToString, stringToState

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_TOL_UPDATE

public static final int SHOW_TOL_UPDATE

See Also:

Constant Field Values

SHOW_BLOCK_PIVOT_CHANGE

public static final int SHOW_BLOCK_PIVOT_CHANGE

See Also:

Constant Field Values

SHOW_VARIABLES

public static final int SHOW_VARIABLES

See Also:

Constant Field Values

SHOW_RETURNS

public static final int SHOW_RETURNS

See Also:

Constant Field Values

SHOW_ALL

public static final int SHOW_ALL

See Also:

Constant Field Values

Constructor Detail

MurtyLCPSolver

public MurtyLCPSolver()

Method Detail

getDebug

public int getDebug()

setDebug

public void setDebug(int code)

getSilent

public boolean getSilent()

setSilent

public void setSilent(boolean code)

getComputeResidual

public boolean getComputeResidual()

setComputeResidual

public void setComputeResidual(boolean enable)

getResidual

public double getResidual()

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.

Setting a negative value will cause the solver to choose its own tolerance based on the input data. This can then be retrieved, after the solve, using getLastSolveTol().

Parameters:

tol - new numeric tolerance. Negative numbers will be truncated to 0.

See Also:

getTolerance()

getBlockPivoting

public boolean getBlockPivoting()

setBlockPivoting

public void setBlockPivoting(boolean enable)

getLastBlockPivoting

public boolean getLastBlockPivoting()

getLastSolveTol

public double getLastSolveTol()

Returns the numeric tolerance used to determine complementarity for the most recent solution. These tolerances may be updated dynamically during the solution.

Specified by:

getLastSolveTol in interface LCPSolver

numFailedPivots

public int numFailedPivots()

Returns the number of pivots that were attempted and rejected because they would have resulted in a basis matrix that was not SPD.

Specified by:

numFailedPivots in interface LCPSolver

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 Dantzig'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 that were used in the most recent solution operation.

Specified by:

getIterationCount in interface LCPSolver

Returns:

iteration count for last solution

getPivotCount

public int getPivotCount()

Returns the number of pivots that were used in the most recent solution operation. For solvers that support block pivoting and have block pivoting enabled, this will usually exceed the number of iterations. Otherwise, this number should be roughly equal to the number of iterations.

Specified by:

getPivotCount in interface LCPSolver

Returns:

pivot count for last solution

solve

public LCPSolver.Status solve(VectorNd z,
                              VectorNi state,
                              MatrixNd M,
                              VectorNd q)

Solves the LCP

 w = M z + q
 

where M is a matrix whose characteristics should match the capabilities of the solver.

Specified by:

solve in interface LCPSolver

Parameters:

z - returns the solution for z

state - optional argument, which if non-null, returns the state vector resulting from the LCP solve. For solvers capable of warm starts (i.e., if LCPSolver.isWarmStartSupported() returns true), the value of this vector on input will also specify the initial starting state.

M - system matrix

q - system vector

Returns:

Status of the solution.

solve

public LCPSolver.Status solve(VectorNd z,
                              VectorNd w,
                              VectorNi state,
                              MatrixNd M,
                              VectorNd q,
                              VectorNd lo,
                              VectorNd hi,
                              int nub)

If LCPSolver.isBLCPSupported() returns true, solves the BLCP

 w = M z + q = wpos - wneg,
 0 ≤ hi - z perp wneg ≥ 0,
 0 ≤ z - lo perp wpos ≥ 0,
 

where M is a matrix whose characteristics should match the capabilities of the solver. If BLCPs are not supported, then this method returns LCPSolver.Status.UNIMPLEMENTED.

Specified by:

solve in interface LCPSolver

Parameters:

z - returns the solution for z

w - returns the solution for w

state - optional argument, which if non-null, returns the state vector resulting from the LCP solve. For solvers capable of warm starts (i.e., if LCPSolver.isWarmStartSupported() returns true), the value of this vector on input will also specify the initial starting state.

M - system matrix

q - system vector

lo - lower bounds for the z variables

hi - upper bounds for the z variables

nub - number of unbounded variables (corresponding to bilateral constraints). If nub > 0, then the first nub entries of lo and hi must be negative and positive infinity, respectively.

Returns:

Status of the solution.

isBLCPSupported

public boolean isBLCPSupported()

Queries whether this solver supported the solution of bounded linear complementarity problems (BLCPs).

Specified by:

isBLCPSupported in interface LCPSolver

Returns:

true if BLCPs are supported.

isWarmStartSupported

public boolean isWarmStartSupported()

Queries whether this solver supports warm starts.

Specified by:

isWarmStartSupported in interface LCPSolver

Returns:

true if warm starts are supported.