sci.op-research

On 2008-02-22 10:37:33 -0400,
spellucci@fb04373.mathematik.tu-darmstadt.de (Peter Spellucci) said:

>
> In article <1cdd67b4-9168-415c-b75b-e65709365f0b@h25g2000hsf.googlegroups.com>,
> GG writes:
> >Hello,
> >
> >I am looking for a program or library for convex analysis.
> >
> >For an m x n matrix M, I looking for v which satisfies Mv = 0. There
> >exists a convex set of vectors all non-negative linear combinations of
> >which satisfy the equation above, so-called extreme rays. I am looking
> >for a program to get extreme rays out of a given matrix M.
> >
> >I look forward to hearing from you. Any comment will be welcomed.
> >Thank you very much.
>
> something must be wrong here:
> the solution set of Mv=0 is a subspace, which best is computed using
> the svd of M. Maybe you meant Mv >=0, v>=0 ?
> Computing all extremal directions of an unbounded polyhedral set is as
> complex as
> finding all vertices from which an LP step detects unboundedness
> (the current correction direction computed in this step is just such an
> extremal direction) I don't know whether this is feasible
>
> hth
> peter

For extreme point enumeration of small polyhedra try either
Fukuda's double desription method (CDD) which is a nonpivoting
(Fourier elimination) method or Avis's lexagraphic reverse search
(lrs) which is a lexographically ordered pivoting method. Avis and
Fukuda sometime collaborate. Avis is a McGill and Fukuda at ETH
(? or close by but I should ask google for certain!). There is a
(small) body of literature on extreme point enumeration that will
be cited by these two. There are a couple of other geometry libraries
that address similar issues. Bremner is an Avis student now at U New
Brunswick who has worked on this as well.

I think there is a rational arithmetic variant of CDD but you need
to check his web site.