Eliminate redundant rows from H-representation (intersection of half spaces) or V-representation (convex hull of points and directions) of convex polytope.
redundant(input, representation = c("H", "V"))
a list containing some of the following components:
The input matrix with redundant rows removed.
For an H-representation, row numbers of inequality constraint rows that together imply equality constraints. For a V-representation, row numbers of rays that together imply lines.
Row numbers of redundant rows. Note: this is set
redset
output by the dd_MatrixCanonicalize
function
in cddlib
. It apparently does not consider all rows it deletes
“redundant”. Redundancy can also be determined from the
following component.
Integer vector of length nrow(input)
. Says
for each input row which output row it becomes or zero to indicate
redundant.
either H-representation or V-representation of convex polyhedron (see details).
if "H"
, then input
is
an H-representation, otherwise a V-representation. May also be
obtained from a "representation"
attribute of input
,
if present.
The input representation may
have type "character"
in which case its elements are interpreted
as unlimited precision rational numbers. They consist of an optional
minus sign, a string of digits of any length (the numerator),
a slash, and another string of digits of any length (the denominator).
The denominator must be positive. If the denominator is one, the
slash and the denominator may be omitted. This package
provides several functions (see ConvertGMP and ArithmeticGMP)
for conversion back and forth between R floating point numbers and rationals
and for arithmetic on GMP rationals.
If you want correct answers, use rational arithmetic. If you do not, this function may (1) produce approximately correct answers, (2) fail with an error, (3) give answers that are nowhere near correct with no error or warning, or (4) crash R losing all work done to that point. In large simulations (1) is most frequent, (2) occurs roughly one time in a thousand, (3) occurs roughly one time in ten thousand, and (4) has only occurred once. So the R floating point arithmetic version does mostly work, but you cannot trust its results unless you can check them independently.
See cddlibman.pdf
in the doc
directory of this package,
especially Sections 1 and 2.
Both representations are (in R) matrices, the first two columns are
special. Let foo
be either an H-representation or
a V-representation and
l <- foo[ , 1]
b <- foo[ , 2]
v <- foo[ , - c(1, 2)]
a <- (- v)
In the H-representation the convex polyhedron in question is the set of
points x
satisfying
axb <- a %*% x - b
all(axb <= 0)
all(l * axb == 0)
In the V-representation the convex polyhedron in question is the set of
points x
for which there exists a lambda
such that
x <- t(lambda) %*% v
where lambda
satisfies the constraints
all(lambda * (1 - l) >= 0)
sum(b * lambda) == max(b)
An H-representation or V-representation object can be checked for validity
using the function validcdd
.
ArithmeticGMP
, ConvertGMP
,
validcdd
, makeH
hrep <- rbind(c(0, 0, 1, 1, 0),
c(0, 0, -1, 0, 0),
c(0, 0, 0, -1, 0),
c(0, 0, 0, 0, -1),
c(0, 0, -1, -1, -1))
redundant(d2q(hrep), representation = "H")
foo <- c(1, 0, -1)
hrep <- cbind(0, 1, rep(foo, each = 9), rep(foo, each = 3), foo)
print(hrep)
redundant(d2q(hrep), representation = "V")
Run the code above in your browser using DataLab