equations.h File Reference

Definition of the Tequations type and the associated functions. More...

#include "boolean.h"
#include "variables.h"
#include "equation.h"
#include "simplex.h"
#include <stdio.h>

Data Structures
struct	TequationInfo
	Information associated with each equation in the equation set. More...
struct	Tequations
	Set of equations. More...
Defines
#define	INIT_NUM_EQUATIONS 10
	Initial room for equations.
Functions
void	InitEquations (Tequations *eqs)
	Constructor.
void	CopyEquations (Tequations eqs_dst, Tequations eqs_src)
	Copy constructor.
boolean	UsedVarInNonDummyEquations (unsigned int nv, Tequations *eqs)
	Checks if a variable is used in the set of equations.
boolean	UsedVarInEquations (unsigned int nv, Tequations *eqs)
	Checks if a variable is used in the set of equations.
void	RemoveEquationsWithVar (double epsilon, unsigned int nv, Tequations *eqs)
	Removes all equations that include a given variable.
boolean	ReplaceVariableInEquations (double epsilon, unsigned int nv, TLinearConstraint lc, Tequations eqs)
	Replaces a variable with a linear expression.
boolean	GaussianElimination (Tequations *eqs)
	Perform Gaussian elimination on the set of equations.
unsigned int	NEquations (Tequations *eqs)
	Number of equations in the set.
unsigned int	NSystemEquations (Tequations *eqs)
	Number of system equations in the set.
unsigned int	NCoordEquations (Tequations *eqs)
	Number of coordenalization equations in the set.
unsigned int	NDummyEquations (Tequations *eqs)
	Number of dummy equations in the set.
unsigned int	NEqualityEquations (Tequations *eqs)
	Number of equalities in the set.
boolean	IsSystemEquation (unsigned int i, Tequations *eqs)
	Identify system equations.
boolean	IsCoordEquation (unsigned int i, Tequations *eqs)
	Identify coordenalization equations.
boolean	IsDummyEquation (unsigned int i, Tequations *eqs)
	Identify dummy equations.
unsigned int	GetEquationTypeN (unsigned int i, Tequations *eqs)
	Gets the type of a particular equation.
boolean	HasEquation (Tequation equation, Tequations eqs)
	Checks if a given equation is already in the set.
void	AddEquation (Tequation equation, Tequations eqs)
	Adds an equation to the set.
Tequation *	GetEquation (unsigned int n, Tequations *eqs)
	Gets an equation from the set.
TequationInfo *	GetEquationInfo (unsigned int n, Tequations *eqs)
	Gets the info associated with an equation in the set.
unsigned int	CropEquation (unsigned int ne, double epsilon, double rho, Tbox b, Tequations eqs)
	Equation-wise crop.
boolean	AddEquation2Simplex (unsigned int ne, double lr2tm_q, double lr2tm_s, double epsilon, double rho, Tbox b, Tvariables vs, TSimplex lp, Tequations eqs)
	Adds an equation to the simplex.
void	UpdateSplitWeight (unsigned int ne, double splitDim, Tbox b, Tequations *eqs)
	Computes the linearization error induced by the variables of a given equation.
void	PrintEquations (FILE f, char varNames, Tequations eqs)
	Prints a set of equations.
void	DeleteEquations (Tequations *eqs)
	Destructor.

Detailed Description

Definition of the Tequations type and the associated functions.

See also:: Tequations, equations.c.

Definition in file equations.h.

Define Documentation

#define INIT_NUM_EQUATIONS 10

Initial room for equations in an equation set. It will be enlarged if necessary.

See also:: Tequations

Definition at line 25 of file equations.h.

Referenced by InitEquations().

Function Documentation

void InitEquations ( Tequations * eqs )

Initializes a set of equations.

Parameters:

eqs

The equation set to be initialized.

Definition at line 595 of file equations.c.

References Tequations::c, Tequations::d, Tequations::e, Tequations::equation, INIT_NUM_EQUATIONS, Tequations::max, Tequations::n, NEW, and Tequations::s.

Referenced by DummifyCuikSystem(), GaussianElimination(), InitCuikSystem(), RemoveEquationsWithVar(), and ReplaceVariableInEquations().

Here is the caller graph for this function:

void CopyEquations	(	Tequations *	eqs_dst,
		Tequations *	eqs_src
	)

Initializes a set of equations from another set.

Parameters:

	eqs_dst	The equation set to be initialized.
	eqs_src	The equation set from where to get the information.

Definition at line 611 of file equations.c.

References Tequations::c, CopyEquationInfo(), Tequations::d, Tequations::e, Tequations::equation, Tequations::max, Tequations::n, NEW, and Tequations::s.

Referenced by CopyCuikSystem(), CuikSystemMerge(), DummifyCuikSystem(), GaussianElimination(), GetCSEquations(), RemoveEquationsWithVar(), ReplaceVariableInEquations(), and SimplifyCuikSystem().

Here is the call graph for this function:

Here is the caller graph for this function:

boolean UsedVarInNonDummyEquations	(	unsigned int	nv,
		Tequations *	eqs
	)

Checks if a variable is used in non-dummy equations of the set of equations.

Parameters:

	nv	The identifier of the variable to look for.
	eqs	The equation set from where to get the information.

Returns:: TRUE if the variable nv appears in any of the non-dummy equations of the set eqs.

Definition at line 637 of file equations.c.

References DUMMY_EQ, FALSE, GetEquation(), GetEquationType(), GetEquationVariables(), and VarIncluded().

Referenced by CSRemoveUnusedVars().

Here is the call graph for this function:

Here is the caller graph for this function:

boolean UsedVarInEquations	(	unsigned int	nv,
		Tequations *	eqs
	)

Checks if a variable is used in the set of equations.

Parameters:

	nv	The identifier of the variable to look for.
	eqs	The equation set from where to get the information.

Returns:: TRUE if the variable nv appears in the set eqs.

Definition at line 657 of file equations.c.

References FALSE, GetEquation(), GetEquationVariables(), and VarIncluded().

Referenced by CSRemoveUnusedVars(), and SampleCuikSystemInBox().

Here is the call graph for this function:

Here is the caller graph for this function:

void RemoveEquationsWithVar	(	double	epsilon,
		unsigned int	nv,
		Tequations *	eqs
	)

Removes all equations that include a given variable. This is one of the steps to remove a variable from a problem. Therefore, equations that do not include the given variable are also affected by this function: we have to shift all the variable indexes higher than the given one.

The use of this function without using function RemoveVariable right immediately after it leaves the cuiksystem in a incoherent state.

Parameters:

	epsilon	Monomials with a constant below epsilon are eliminated.
	nv	The identifier of the variable to remove.
	eqs	The set of equations to update.

Definition at line 673 of file equations.c.

References AddEquation(), CopyEquations(), DeleteEquations(), FixVariableInEquation(), GetEquation(), GetEquationVariables(), InitEquations(), Tequations::n, and VarIncluded().

Referenced by CSRemoveUnusedVars().

Here is the call graph for this function:

Here is the caller graph for this function:

boolean ReplaceVariableInEquations	(	double	epsilon,
		unsigned int	nv,
		TLinearConstraint *	lc,
		Tequations *	eqs
	)

Replaces a variable by linear combination of variables (including an offset).

The use of this function without using function RemoveVariable right immediately after it leaves the cuiksystem in a incoherent state.

Parameters:

	epsilon	Monomials with a constant below epsilon are eliminated.
	nv	The variable to replace.
	lc	The linear constraint to use in the replacement.
	eqs	The equation set from where to get the information.

Returns:: TRUE the equation set still holds after replacing the equation.

See also:: SimplifyCuikSystem

Definition at line 702 of file equations.c.

References AddEquation(), CopyEquations(), DeleteEquations(), FALSE, GetEquation(), InitEquations(), ReplaceVariableInEquation(), and TRUE.

Referenced by CSRemoveLCVars(), and CSRemoveVarsWithCtRange().

Here is the call graph for this function:

Here is the caller graph for this function:

boolean GaussianElimination ( Tequations * eqs )

Operates linearly pairs of equations (scale one of the and then sum them) with the objective of getting a simpler equation (i.e., one with less monomials). The rationale is that equations with less monomials produce simpler problems and, in some cases, they can trigger simplifications that are not evident at first sight.

The use of this function without using function RemoveVariable right immediately after it leaves the cuiksystem in a incoherent state.

Parameters:

eqs

The equation set to be simplified.

Returns:: TRUE the equation set still holds after replacing the equation.

See also:: AccumulateEquations, SimplifyCuikSystem

Definition at line 737 of file equations.c.

References AccumulateEquations(), AddEquation(), CopyEquation(), CopyEquations(), DeleteEquation(), DeleteEquations(), DUMMY_EQ, EQU, FALSE, FindMonomial(), GetEquation(), GetEquationCmp(), GetEquationNumVariables(), GetEquationType(), GetMonomial(), GetMonomialCt(), GetNumMonomials(), InitEquations(), NEquations(), NO_UINT, and TRUE.

Referenced by SimplifyCuikSystem().

Here is the call graph for this function:

Here is the caller graph for this function:

unsigned int NEquations ( Tequations * eqs )

Number of equations in the set.

Parameters:

eqs

The equation set.

Returns:: The number of equations in the set.

Definition at line 829 of file equations.c.

References Tequations::n.

Referenced by CoordInequalitiesHold(), CSRemoveLCVars(), CuikSystemMerge(), DeleteCuikSystemJacobian(), DummifyCuikSystem(), ErrorInInequalities(), ErrorInSolution(), GaussianElimination(), GetCSNumEquations(), GetCuikSystemJacobian(), and UpdateCuikSystem().

Here is the caller graph for this function:

unsigned int NSystemEquations ( Tequations * eqs )

Number of system equations in the set.

Parameters:

eqs

The equation set.

Returns:: The number of system equations in the set.

Definition at line 834 of file equations.c.

References Tequations::s.

unsigned int NCoordEquations ( Tequations * eqs )

Number of coordenalization equations in the set.

Parameters:

eqs

The equation set.

Returns:: The number of coordenalization equations in the set.

Definition at line 839 of file equations.c.

References Tequations::c.

unsigned int NDummyEquations ( Tequations * eqs )

Number of dummy equations in the set.

Parameters:

eqs

The equation set.

Returns:: The number of dummy equations in the set.

Definition at line 844 of file equations.c.

References Tequations::d.

unsigned int NEqualityEquations ( Tequations * eqs )

Number of equality equations in the set.

Parameters:

eqs

The equation set.

Returns:: The number of equality equations in the set.

Definition at line 849 of file equations.c.

References Tequations::e.

Referenced by UpdateCuikSystem().

Here is the caller graph for this function:

boolean IsSystemEquation	(	unsigned int	i,
		Tequations *	eqs
	)

Identify system equations.

Parameters:

	i	The identifier of the equation to check.
	eqs	The equation set.

Returns:: TRUE if the selecte equation is a system equation.

Definition at line 854 of file equations.c.

References Tequations::equation, GetEquationType(), GetOriginalEquation(), and SYSTEM_EQ.

Referenced by PrintEquations().

Here is the call graph for this function:

Here is the caller graph for this function:

boolean IsCoordEquation	(	unsigned int	i,
		Tequations *	eqs
	)

Identify coordenalization equations.

Parameters:

	i	The identifier of the equation to check.
	eqs	The equation set.

Returns:: TRUE if the selected equation is a coordenalization equation.

Definition at line 860 of file equations.c.

References COORD_EQ, Tequations::equation, GetEquationType(), and GetOriginalEquation().

Referenced by PrintEquations().

Here is the call graph for this function:

Here is the caller graph for this function:

boolean IsDummyEquation	(	unsigned int	i,
		Tequations *	eqs
	)

Identify dummy equations.

Parameters:

	i	The identifier of the equation to check.
	eqs	The equation set.

Returns:: TRUE if the selected equation is a dummy equation.

Definition at line 866 of file equations.c.

References DUMMY_EQ, Tequations::equation, GetEquationType(), and GetOriginalEquation().

Referenced by PrintEquations().

Here is the call graph for this function:

Here is the caller graph for this function:

unsigned int GetEquationTypeN	(	unsigned int	i,
		Tequations *	eqs
	)

Gets the type of a particular equation.

Parameters:

	i	The identifier of the equation to check.
	eqs	The equation set.

Returns:: The type of the selected eqution of NOTYPE_EQ if there is no equation with the given identifier in the set.

Definition at line 872 of file equations.c.

References Tequations::equation, GetEquationType(), GetOriginalEquation(), and NOTYPE_EQ.

Here is the call graph for this function:

boolean HasEquation	(	Tequation *	equation,
		Tequations *	eqs
	)

Checks if a given equation is already in the set.

Parameters:

	equation	The equation.
	eqs	The equation set.

Returns:: TRUE if the given equation is already in the set.

Definition at line 880 of file equations.c.

References CmpEquations(), Tequations::equation, FALSE, and GetOriginalEquation().

Referenced by AddEquation().

Here is the call graph for this function:

Here is the caller graph for this function:

void AddEquation	(	Tequation *	equation,
		Tequations *	eqs
	)

Adds an equation to the set and computes its associated information.

Parameters:

	equation	The equation to be added.
	eqs	The equation set.

See also:: TequationInfo.

Definition at line 1157 of file equations.c.

References Tequations::c, CmpEquations(), COORD_EQ, Tequations::d, DUMMY_EQ, Tequations::e, EQU, Tequations::equation, Error(), GetEquationCmp(), GetEquationType(), GetNumMonomials(), GetOriginalEquation(), HasEquation(), Tequations::max, MEM_DUP, Tequations::n, NEW, NOCMP, NormalizeEquation(), NOTYPE_EQ, Tequations::s, SetEquationInfo(), and SYSTEM_EQ.

Referenced by AddEquation2CS(), DummifyAndAddEquation(), GaussianElimination(), RemoveEquationsWithVar(), and ReplaceVariableInEquations().

Here is the call graph for this function:

Here is the caller graph for this function:

Tequation* GetEquation	(	unsigned int	n,
		Tequations *	eqs
	)

Returns a pointer to the n-th equation stored in the set.

Parameters:

	n	The number of equation to get.
	eqs	The equation set.

Definition at line 1204 of file equations.c.

References Tequations::equation, and GetOriginalEquation().

Referenced by ComputeSimpCuikSystemJacobian(), CoordInequalitiesHold(), CSRemoveLCVars(), CuikSystemMerge(), DummifyCuikSystem(), ErrorInInequalities(), ErrorInSolution(), GaussianElimination(), GetCSEquation(), GetCuikSystemJacobian(), RemoveEquationsWithVar(), ReplaceVariableInEquations(), UsedVarInEquations(), and UsedVarInNonDummyEquations().

Here is the call graph for this function:

Here is the caller graph for this function:

TequationInfo* GetEquationInfo	(	unsigned int	n,
		Tequations *	eqs
	)

Returns a pointer to the information of the n-th equation stored in the set.

Parameters:

	n	The number of equation to query.
	eqs	The equation set.

See also:: TequationInfo.

unsigned int CropEquation	(	unsigned int	ne,
		double	epsilon,
		double	rho,
		Tbox *	b,
		Tequations *	eqs
	)

Gets a box (as an array of parameters is of size m) and uses the equation number ne to reduce the ranges of the variables involved in the equation as much as possible.
Only equalities are used for crop (LEQ and GEQ equations are not taken into account).
We use different crop procedures according to the type of equation: LINEAR_EQ, PARABOLA_EQ, SADDLE_EQ, CIRCLE_EQ, SPHERE_EQ or GENERAL_EQ. In the GENERAL_EQ case, equations a the linear approximation is used for the crop. This does not produce the stronger possible crop. For this reason, we implemented non-linear crop for the non-linear equations that appear often in the systems of equations (due to dummification, for instance).

Parameters:

	ne	The equation to use in the crop.
	epsilon	Only ranges with a size larger than epsilon are reduced.
	rho	The crop is repeated as far as the ranges for the variables in the equation reduce a ratio larger than rho.
	b	The box with the ranges to crop.
	eqs	The equation set.

See also:: ReduceBoxEquationWise

Definition at line 895 of file equations.c.

References BoxSaddleClipping(), BoxSphereClipping(), CIRCLE_EQUATION, CopyInterval(), CropLinearConstraint(), DeleteLinearConstraint(), EMPTY_BOX, TequationInfo::EqType, EQU, Tequations::equation, Error(), GENERAL_EQUATION, GetBoxIntervals(), GetBoxNIntervals(), GetEquationCmp(), GetEquationValue(), GetEquationVariables(), GetFirstOrderApproximationToEquation(), GetLinearConstraintError(), GetMonomial(), GetMonomialCt(), GetMonomialVariables(), GetNumMonomials(), GetOriginalEquation(), GetVariableN(), INF, IntervalCenter(), IntervalSize(), TequationInfo::lc, LINEAR_EQUATION, TequationInfo::n, NEW, NewInterval(), NOT_REDUCED_BOX, PARABOLA_EQUATION, PrintEquation(), PrintInterval(), RectangleCircleClipping(), RectangleParabolaClipping(), REDUCED_BOX, SADDLE_EQUATION, SetLinearConstraintError(), SimplexExpandBounds(), SPHERE_EQUATION, VariableSetSize(), and ZERO.

Referenced by AddEquation2Simplex(), and ReduceBoxEquationWise().

Here is the call graph for this function:

Here is the caller graph for this function:

boolean AddEquation2Simplex	(	unsigned int	ne,
		double	lr2tm_q,
		double	lr2tm_s,
		double	epsilon,
		double	rho,
		Tbox *	b,
		Tvariables *	vs,
		TSimplex *	lp,
		Tequations *	eqs
	)

Adds linear constraints representing the selected equation (i.e., a linear relaxation of the equation) to a simplex tableau. Linear constraints are directly added to the simplex using the information cached in the TequationInfo structure. Non linear equations are linearized using the information stored in the Jacobian and Hessian fields in the corresponding TequationInfo too. Different equations are linearized in a different way

For Parabola equations y=x^2: Two planes defined at the center of the x range and, if the variables in the equation are larger than lr2tm_q, we add one plane at each one of the extremes of the x range.
For Circle equations x^2+y^2=r^2: Two planes defined at the center of the x-y range and, if the variables in the equation are larger than lr2tm_q, we add one plane tangent to the circle for the corners of the x-y box that are out of the circle.
- For Sphere equations x^2+y^2+z^2=r^2: Two planes defined at the center of the x-y-z range and, if the variables in the equation are larger than lr2tm_q, we add one plane tangent to the sphere for the corners of the x-y-z box that are out of the sphere.
For Saddle equations z=x*y: if the variables in the equation are larger than lr2tm_s, we add one plane for each corner of the x-y square. Otherwise we linearize the equation as a general equation (two planes defined at the center of the x,y,z box).
For the rest of equations, a couple of planes defined from the linearization of the equation at the center of the sub-box defined by the variables involved in the equation plus-less an error defined from the remainder of the linearization. For equalities we add the two planes defined in such a way but for inequalities only one plane is necessary.

By using small lr2tm_q and lr2tm_s we generate linear relaxations that tightly bound the functions and this reduces the number of iterations to found the solution. The drawnback is that we we add more constraints to the simplex and this slows downs each iteration.

Equations that define particular variables (cartesian or dummy ones) are only added to the simplex if the variable is used in any of the other constraints already in the simplex. Otherwise we will add useless constraints. This filter is implemented with the array of booleans usedVar. This array is updated as we add equations to the simplex and is checked to see if defined variables are used before adding the corresponding equation to the simplex. For this to be operative, equations are ordered so that system equations are added first to the simplex, then cartesian equations and, finally, dummyfications equations.

There is no need to equations that involves almost constant variables to the simplex. Thus, before adding an EQU equation to the simplex, we evaluate the equations using interval arithmetics and if the result is almost constant(this occurs if the variables involved in the equation are have tiny ranges) we just check if the equation holds or not. If not, the system has no solution.

The same applies to inequalities that already hold. An inequality (LEQ, GEQ equations) that trivially holds do not add any constrain to the simplex and, consequently we do not add it to the Tableau.

Parameters:

	ne	The number of the equation to add.
	lr2tm_q	Size of the variables in the equation to switch between a specific linearization and a general one for spheres, circles, and parabolas.
	lr2tm_s	Size of the variables in the equation to switch between a specific linearization and a general one for saddle equations.
	epsilon	When generating a linear constraints, coefficients below epsilon are discarted, since the simplex process has troubles with too small values.
	rho	Before adding the equation to the simplex it is croped and the crop process is repeated as far as the variables reduce more than rho. Ranges smaller than epsilon are not reduced any further.
	b	The box with the variable ranges. It defines the area where to linearize the equations and where to compute the linearization error, if necessary.
	vs	The set of variables. Used to get the type of variables in GetDefinedVar
	lp	The simplex structure where to add the constraints.
	eqs	The equation set.

See also:: CropEquation, GetDefinedVar

Returns:: TRUE if the simplex is still feasible after adding the linear constraints.

Definition at line 1584 of file equations.c.

References CIRCLE_EQUATION, CropEquation(), EMPTY_BOX, TequationInfo::EqType, EQU, Tequations::equation, Error(), EvaluateEquationInt(), FALSE, GENERAL_EQUATION, GEQ, GetBoxIntervals(), GetBoxMinSizeVarSet(), GetEquationCmp(), GetEquationValue(), GetEquationVariables(), GetOriginalEquation(), INF, IntervalOffset(), IntervalSize(), IsInside(), TequationInfo::lc, LEQ, LINEAR_EQUATION, LinearizeCircleEquation(), LinearizeGeneralEquation(), LinearizeParabolaEquation(), LinearizeSaddleEquation(), LinearizeSphereEquation(), LowerLimit(), PARABOLA_EQUATION, PrintEquation(), PrintInterval(), SADDLE_EQUATION, SimplexAddNewConstraint(), SPHERE_EQUATION, TRUE, and UpperLimit().

Referenced by ReduceBox().

Here is the call graph for this function:

Here is the caller graph for this function:

void UpdateSplitWeight	(	unsigned int	ne,
		double *	splitDim,
		Tbox *	b,
		Tequations *	eqs
	)

When the SPLIT_ERROR parameter is set to TRUE, we select the split variable for a box from the linearization error induced by the variables. This function updates the error induced by the variables in a given equation.

Parameters:

	ne	The equation to use in the update.
	splitDim	The array with the linearization errors induced by the variables to be updated.
	b	The box with the ranges for the variables.
	eqs	The equation set.

Definition at line 1775 of file equations.c.

References TequationInfo::EqType, TequationInfo::equation, Tequations::equation, ErrorDueToVariable(), GetBoxIntervals(), GetBoxNIntervals(), GetEquationVariables(), GetVariableN(), IntervalCenter(), LINEAR_EQUATION, TequationInfo::n, and NEW.

Referenced by ComputeSplitDimInt().

Here is the call graph for this function:

Here is the caller graph for this function:

void PrintEquations	(	FILE *	f,
		char **	varNames,
		Tequations *	eqs
	)

Writes a set of equations into a stream.

Parameters:

	f	The stream where to write the equations.
	varNames	The name of the variables. If this parameter is NULL the printed names for the variables are v_X with X the index of the variable.
	eqs	The equation set to print.