  We present abstract acceleration techniques for computing loop invariants for
numerical programs with linear assignments and conditionals. Whereas abstract
interpretation techniques typically over-approximate the set of reachable
states iteratively, abstract acceleration captures the effect of the loop with
a single, non-iterative transfer function applied to the initial states at the
loop head. In contrast to previous acceleration techniques, our approach
applies to any linear loop without restrictions. Its novelty lies in the use of
the Jordan normal form decomposition of the loop body to derive symbolic
expressions for the entries of the matrix modeling the effect of n>=0
iterations of the loop. The entries of such a matrix depend on $n$ through
complex polynomial, exponential and trigonometric functions. Therefore, we
introduces an abstract domain for matrices that captures the linear inequality
relations between these complex expressions. This results in an abstract matrix
for describing the fixpoint semantics of the loop.
  Our approach integrates smoothly into standard abstract interpreters and can
handle programs with nested loops and loops containing conditional branches. We
evaluate it over small but complex loops that are commonly found in control
software, comparing it with other tools for computing linear loop invariants.
The loops in our benchmarks typically exhibit polynomial, exponential and
oscillatory behaviors that present challenges to existing approaches. Our
approach finds non-trivial invariants to prove useful bounds on the values of
variables for such loops, clearly outperforming the existing approaches in
terms of precision while exhibiting good performance.
