# File numerics/src/LCP/pivot-utils.h¶

Go to the source code of this file

some functions used in one or more solver, mainly related to Lemke’s algorithm

Defines

PIVOT_PATHSEARCH_SUCCESS

Functions

int pivot_init_lemke(double *mat, unsigned int dim)

find the first leaving variable for Lemke’s algorithm

Parameters
• mat – the matrix

• dim – the dimension of the problem

Returns

the index of the blocking variable

int pivot_init_pathsearch(unsigned dim, double *mat, unsigned *t_indx)

find the first leaving variable for the pathsearch algorithm

Parameters
• dim – the dimension of the problem

• mat – the matrix

• t_indx[out] the index of t in the basis (needed since block < 0 is possible and meaningful)

Returns

the index of the blocking (leaving) variable

int pivot_selection_lemke(double *mat, unsigned dim, unsigned drive, unsigned aux_index)

find the leaving variable for Lemke’s algorithm

Parameters
• mat – the matrix; we only use the columns of basic variable and the covering vector of the entering variable

• dim – dimension of the problem

• drive – the driving variable

• aux_index – index of auxillary variable in the current basis

Returns

the leaving (or blocking) variable

int pivot_selection_lemke2(unsigned n, double *col_drive, double *q_tilde, double *lexico_mat, unsigned aux_indx, double lexico_tol)

find the leaving variable for Lemke’s algorithm

Parameters
• n – dimension of the problem pivots)

• col_drive – column of the driving variable (contains all the possible pivots)

• q_tilde – solution of the linear system

• lexico_mat – matrix for the lexico ordering

• aux_indx – index of auxillary variable in the current basis

• lexico_tol – the tolerance on the lexicographic comparison

Returns

the leaving (or blocking) variable

int pivot_selection_lemke3(unsigned n, double *col_drive, double *q_tilde, double *lexico_col, unsigned *basis, unsigned *candidate_indx, SN_lumod_dense_data *lumod_data, unsigned aux_indx, double lexico_tol)

find the leaving variable for Lemke’s algorithm

Parameters
• n – dimension of the problem

• col_drive – column of the driving variable (contains all the possible pivots)

• q_tilde – solution of the linear system

• lexico_col – column for the lexico ordering

• basis – current basis

• candidate_indx – array for storing the possible candidate indexes

• lumod_data – data for the BLU update

• aux_indx – index of auxillary variable in the current basis

• lexico_tol – the tolerance on the lexicographic comparison

Returns

the leaving (or blocking) variable

int pivot_selection_pathsearch(double *mat, unsigned dim, unsigned drive, unsigned t_indx)

find the leaving variable in a path search procedure.

The code is almost the same as in pivot_selection_lemke, except that we also check if it is possible to set t = 1.

Parameters
• mat – the matrix (we only use the columns of basic variable and the covering vector of the entering variable

• dim – dimension of the problem

• drive – the driving or entering variable

• t_indx – the index of the t variable in the basis

Returns

the leaving (or blocking) variable

void init_M_lemke(double *mat, double *M, unsigned int dim, unsigned int size_x, double *q, double *d)

Initialize the matrix for Lemke’s algorithm as [ q | Id | -d | -M ] with d_i = 1 if i < size_x if the argument d is NULL.

Otherwise take d from the arguments

Parameters
• mat – column-major matrix to fill

• M – M matrix from the LCP formulation

• dim – dimension of the problem

• size_x – for the classical Lemke’s algorithm, this is set to dim. Its value is different when we solve an AVI using Cao and Ferris method

• q – vector from the LCP formulation

• d – covering vector for the auxiliary variable, possibly NULL

void do_pivot_driftless(double *mat, unsigned int dim, unsigned int dim2, unsigned int block, unsigned int drive)

Do the pivot <block, drive>, driftless version.

Parameters
• mat – the matrix to update

• dim – the number of rows

• dim2 – the number of columns

• block – the blocking or leaving variable

• drive – the driving or entering variable

void do_pivot_driftless2(double *mat, unsigned int dim, unsigned int dim2, unsigned int block, unsigned int drive)

Do the pivot <block, drive>, driftless version.

Parameters
• mat – the matrix to update

• dim – the number of rows

• dim2 – the number of columns

• block – the blocking or leaving variable

• drive – the driving or entering variable

void do_pivot(double *mat, unsigned int dim, unsigned int dim2, unsigned int block, unsigned int drive)

Do the pivot <block, drive>, standart version.

Parameters
• mat – the matrix to update

• dim – the number of rows

• dim2 – the number of columns

• block – the blocking or leaving variable

• drive – the driving or entering variable

void do_pivot_lumod(SN_lumod_dense_data *lumod_data, NumericsMatrix *M, double *q_tilde, double *lexico_mat, double *col_drive, double *col_tilde, unsigned *basis, unsigned block, unsigned drive)

Do the pivot <block, drive> with block-LU updates.

Parameters
• lumod_data – lumod data

• M – the LCP matrix

• q_tilde – the modified q vector: it is the current of the variables currently in the basis

• lexico_mat – matrix for the lexicographic ordering

• col_drive – column of the driving variable

• col_tilde – Solution to H x = col

• basis – current basis

• block – the blocking or leaving variable

• drive – the driving or entering variable

void lcp_pivot_diagnose_info(int info)

print a diagnostic of the info value

Parameters

info – the value given by the algorithm

int pivot_selection_bard(double *mat, unsigned int dim)
int pivot_selection_least_index(double *mat, unsigned int dim)
void init_M_bard (double *restrict mat, double *restrict M, unsigned int dim, double *restrict q)
void init_M_least_index (double *restrict mat, double *restrict M, unsigned int dim, double *restrict q)
int init_M_lemke_warm_start (int n, double *restrict u, double *restrict mat, double *restrict M, double *restrict q, int *restrict basis, double *restrict cov_vec)
const char *basis_to_name(unsigned nb, unsigned n)
unsigned basis_to_number(unsigned nb, unsigned n)