Přejít k obsahu


On Root Classification in Kinetic Data Structures

Citace: [] VOMÁČKA, T., KOLINGEROVÁ, I. On Root Classification in Kinetic Data Structures. In ADVCOMP 2011. Lisabon: IARIA, 2011. s. 32-35. ISBN: 978-1-61208-172-4
Druh: STAŤ VE SBORNÍKU
Jazyk publikace: eng
Anglický název: On Root Classification in Kinetic Data Structures
Rok vydání: 2011
Místo konání: Lisabon
Název zdroje: IARIA
Autoři: Ing. Tomáš Vomáčka , Prof. Dr. Ing. Ivana Kolingerová
Abstrakt CZ: Ve článku se zabýváme matematickými vlastnostmi a výpočtem kinetických událostí v kinetických datových strukturách s polynomiálními certifikátovými funkcemi. Ukazujeme, že ignorování násobnosti kořenů těchto rovnic je nejen teoreticky neopodstatněné, ale zároveň i nebezpečné po numerické stránce. Násobnosti těchto kořenů jsou v některých aplikacích ignorovány za účelem zvýšení rychlosti výpočtu jejich polohy, ale je nezbytně nutné uvažovat je při správě kinetických datových struktur. Některé z těchto kořenů nemusí nést požadovanou informaci (tj. informaci o čase výskytu budoucí kinetické události) a měly být tím pádem z výpočtu zcela vyňaty. V textu ukazujeme způsob, jak tyto kořeny rozpoznat ještě před tím, než se přistoupí k výpočtu jejich umístění a tak se tomuto výpočtu zcela vyhnout.
Abstrakt EN: In this paper we discuss the mathematical properties of kinetic events computation for kinetic data structures with polynomial-type certi?cate functions. We show that it is neither theoretically possible nor numerically safe to ignore the multiplicities of roots of these equations. The multiplicities of the roots are sometimes ignored in order to speed up the process of estimating their location, however, they must be taken into account during the management of the kinetic data structures. Some of the roots obtained by the computations of these equations do not necessarily carry the expected information (i.e., the times of future kinetic events) and they may be therefore avoided entirely during the computation. This text shows how to distinguish these roots before their exact location is computed and thus to avoid their computation.
Klíčová slova

Zpět

Patička