Least distance methods for the frame of homogeneous equation systems (Q1098570)

To represent the cone \(C\) of all nonnegative solutions of the system of linear equations \(Ax=0\) internally, i.e. as the convex hull of extreme rays of \(C\), it is necessary to find the collection of all these rays, called the frame of \(C\). There are several areas of science (the authors give as example a problem related to the dynamic of chemical reaction system) where such a conversion from external representation (i.e. as the intersection of halfspaces or hyperplanes) of a cone to its internal representation is needed and related utility programs are demanded. The authors present and prove two algorithms based on a subroutine that can decide whether a given subset \(K\) of columns of \(A\) contains a ``corral'' of the origin (an affinely independent vertex set of a simplex containing the origin in its relative interior). This subroutine performs one of simplicial decomposition algorithms with the Euclidean metric as objective function, called ``least distance methods''; such a method computes a sequence of points approaching the point from the convex hull of \(K\), nearest to the origin. First of the algorithms (``the corral method'') assembles all possible corrals of origin from the columns of \(A\) and gives in this way the complete frame of \(C\). The second one (``the edge method'') is in some respects dual to the corral method: instead of operating in the \(d\)-dimensional column space of \(A\), it operates in \(n\)-dimensional row space, intersecting the hyperplane defined by the \(d\)-rows with the resident unit simplex. It generates a sequence of polytopes the last of which yields the frame of \(C\). The source texts of APL procedures for the two algorithms are also presented.