F500 Linear Homogeneous Inequalities

Subroutine subprograms RLHOIN and DLHOIN find the basis $v$_j,(j=1,2,...,J) , of the convex polyhedral cone defining the solution of a system of homogeneous linear inequalities $Ax\ge 0$ . $A=a$_mn is a given $M\; xN$ matrix, $M\ge N$ , and rank$(A)=N$ . $x=(x$₁,x₂,...,x_n) is a column vector. Any solution x of $Ax\ge 0$ can be expressed as

$x=\sum$_j=1^Jλ_jv_j.

where all $\lambda$_j≥0 . The number J of vectors $v$_j

depends on the matrix A in an unknown way, except when M=N, where J=N.

On CDC and Cray computers, the double-precision version DLHOIN is not available.

Structure:

SUBROUTINE subprogram
User Entry Names: RLHOIN, DLHOIN
Obsolete User Entry Names: LIHOIN $\equiv$ RLHOIN
Files Referenced: Unit 6
External References: RVCPY, RVMPY, RVSCL, DVCPY, DVMPY, DVSCL (F002),
RMCPY, RMSET, DMCPY, DMSET (F003), RINV, DINV (F010),
MTLMTR (N002), ABEND (Z035)

Usage:

For $t=R$ (type REAL), $t=D$ (type DOUBLE PRECISION),

    CALL tLHOIN(A,MA,M,N,MAXV,V,NV,JVEC,EPS,IOUT,W,IW)

A

(type according to t) Two-dimensional array, dimensioned $(MA,\ge N)$ , whose rows contain the coefficients of the inequalities, arranged in such a way that the upper left $N\; xN$ corner has a non-vanishing determinant. Usually it is advisable to normalise the rows of A to unity before calling this subprogram.

MA

( INTEGER) First dimension parameter of A.

M

( INTEGER) Number M of inequalities.

N

( INTEGER) Number N of variables.

MAXV

( INTEGER) Maximum number of basis vectors which may occur at any intermediate step, to be chosen sufficiently large and in any case $\ge N$ .

V

(type according to t) Two-dimensional array, dimensioned $(NV,\ge MAXV)$ , whose columns contain, on return, the basis vectors $v$_j of the solution cone.

NV

( INTEGER) First dimension parameter of $V\; (\ge N)$ .

JVEC

( INTEGER) Number J of basis vectors of the final cone.

EPS

(type according to t) A small parameter which discriminates small quantities against zero, chosen to take into account the accuracy of the machine used.

IOUT

( INTEGER)
$=\; 0:$ Gives no intermediate printout,
$=\; 1:$ Gives, for each iteration, the basis vectors of the respective cone, the matrix of scalar products and the index of the inequality taken into account in the next step.

W

(type according to t) Two-dimensional array, dimensioned $(MAXV,\ge M+1)$ , used as working space.

IW

( INTEGER) Two-dimensional array, dimensioned $(MA,5)$ whose columns serve as book-keepers for certain properties of the system during the iteration procedure.

Method:

The Motzkin-Burger procedure is used to obtain the solution iteratively. Ref. 1 should be consulted before using this subprogram.

Restrictions:

The routine may fail if the matrix A is "ill-conditioned" in a certain sense.

Notes:

A given system of linear homogenous inequalities may have no solution.

Error handling:

Error F500.1: $MAXV$ too small.
Error F500.2: Upper left $N\; xN$ corner of A is singular.
Error F500.3: Inequality k is inconsistent.
In all cases, a message is written on Unit 6, unless subroutine MTLSET (N002) has been called.

References:

1. K.S. Kölbig and F. Schwarz, A program for solving systems of homogeneous linear inequalities. Computer Phys. Comm. 17 (1979) 375--382.

Statistical Analysis and Probability

G100