  We introduce an efficient combination of polyhedral analysis and predicate
partitioning. Template polyhedral analysis abstracts numerical variables inside
a program by one polyhedron per control location, with a priori fixed
directions for the faces. The strongest inductive invariant in such an abstract
domain may be computed by upward strategy iteration. If the transition relation
includes disjunctions and existential quantifiers (a succinct representation
for an exponential set of paths), this invariant can be computed by a
combination of strategy iteration and satisfiability modulo theory (SMT)
solving. Unfortunately, the above approaches lead to unacceptable space and
time costs if applied to a program whose control states have been partitioned
according to predicates. We therefore propose a modification of the strategy
iteration algorithm where the strategies are stored succinctly, and the linear
programs to be solved at each iteration step are simplified according to an
equivalence relation. We have implemented the technique in a prototype tool and
we demonstrate on a series of examples that the approach performs significantly
better than previous strategy iteration techniques.
