Sparsity Preserving Algorithms for Octagons

Abstract : Known algorithms for manipulating octagons do not preserve their sparsity, leading typically to quadratic or cubic time and space complexities even if no relation among variables is known when they are all bounded. In this paper, we present new algorithms, which use and return octagons represented as weakly closed difference bound matrices, preserve the sparsity of their input and have better performance in the case their inputs are sparse. We prove that these algorithms are as precise as the known ones.
Type de document :
Communication dans un congrès
Isabella Mastroeni. NSAD 2016 - Numerical and symbolic abstract domains workshop , Sep 2016, Edinburgh, United Kingdom. Elsevier, Numerical and symbolic abstract domains, pp.14, 2016, <http://nsad16.di.univr.it/>
Liste complète des métadonnées

https://hal.inria.fr/hal-01406795
Contributeur : Jacques-Henri Jourdan <>
Soumis le : jeudi 1 décembre 2016 - 15:33:38
Dernière modification le : jeudi 8 décembre 2016 - 17:20:53
Document(s) archivé(s) le : lundi 20 mars 2017 - 20:45:01

Fichiers

jourdan2016sparsity.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01406795, version 1
  • ARXIV : 1612.00277

Collections

Citation

Jacques-Henri Jourdan. Sparsity Preserving Algorithms for Octagons. Isabella Mastroeni. NSAD 2016 - Numerical and symbolic abstract domains workshop , Sep 2016, Edinburgh, United Kingdom. Elsevier, Numerical and symbolic abstract domains, pp.14, 2016, <http://nsad16.di.univr.it/>. <hal-01406795>

Partager

Métriques

Consultations de
la notice

81

Téléchargements du document

14