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

Functions

char *basis_to_name(unsigned nb, unsigned n)
unsigned basis_to_number(unsigned nb, unsigned n)
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_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_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 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)
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

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)
void lcp_pivot_diagnose_info(int info)

print a diagnostic of the info value

Parameters
  • info: the value given by the algorithm

int pivot_init_lemke(double *mat, unsigned int dim)

find the first leaving variable for Lemke’s algorithm

Return
the index of the blocking variable
Parameters
  • mat: the matrix
  • dim: the dimension of the problem

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

find the first leaving variable for the pathsearch algorithm

Return
the index of the blocking (leaving) variable
Parameters
  • dim: the dimension of the problem
  • mat: the matrix
  • t_indx: the index of t in the basis (needed since block < 0 is possible and meaningful)

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

find the leaving variable for Lemke’s algorithm

Return
the leaving (or blocking) variable
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

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

Return
the leaving (or blocking) variable
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

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

Return
the leaving (or blocking) variable
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

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.

Return
the leaving (or blocking) variable
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