TY - GEN

T1 - A dynamic algorithm for approximate flow computations

AU - Prabhakar, Pavithra

AU - Viswanathan, Mahesh

PY - 2011

Y1 - 2011

N2 - In this paper we consider the problem of approximating the set of states reachable within a time bound T in a linear dynamical system, to within a given error bound ε. Fixing a degree d, our algorithm divides the interval [0,T] into sub-intervals of not necessarily equal size, such that a polynomial of degree d approximates the actual flow to within an error bound of ε, and approximates the reach set within each sub-interval by the polynomial tube. Our experimental evaluation of the algorithm when the degree d is fixed to be either 1 or 2, shows that the approach is promising, as it scales to large dimensional dynamical systems, and performs better than previous approaches that divided the interval [0,T] evenly into sub-intervals.

AB - In this paper we consider the problem of approximating the set of states reachable within a time bound T in a linear dynamical system, to within a given error bound ε. Fixing a degree d, our algorithm divides the interval [0,T] into sub-intervals of not necessarily equal size, such that a polynomial of degree d approximates the actual flow to within an error bound of ε, and approximates the reach set within each sub-interval by the polynomial tube. Our experimental evaluation of the algorithm when the degree d is fixed to be either 1 or 2, shows that the approach is promising, as it scales to large dimensional dynamical systems, and performs better than previous approaches that divided the interval [0,T] evenly into sub-intervals.

KW - Approximation

KW - Linear dynamical systems

KW - Post computation

UR - http://www.scopus.com/inward/record.url?scp=79956009868&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79956009868&partnerID=8YFLogxK

U2 - 10.1145/1967701.1967722

DO - 10.1145/1967701.1967722

M3 - Conference contribution

AN - SCOPUS:79956009868

SN - 9781450306294

T3 - HSCC'11 - Proceedings of the 2011 ACM/SIGBED Hybrid Systems: Computation and Control

SP - 133

EP - 142

BT - HSCC'11 - Proceedings of the 2011 ACM/SIGBED Hybrid Systems

T2 - 14th ACM International Conference on Hybrid Systems: Computation and Control, HSCC 2011

Y2 - 12 April 2011 through 14 April 2011

ER -