Sparsity Preserving Algorithms for Octagons - Archive ouverte HAL Access content directly
Conference Papers Year : 2016

Sparsity Preserving Algorithms for Octagons

(1, 2)
1
2

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.
Fichier principal
Vignette du fichier
jourdan2016sparsity.pdf (442.02 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01406795 , version 1 (01-12-2016)

Identifiers

Cite

Jacques-Henri Jourdan. Sparsity Preserving Algorithms for Octagons. NSAD 2016 - Numerical and symbolic abstract domains workshop , Sep 2016, Edinburgh, United Kingdom. pp.14. ⟨hal-01406795⟩

Collections

INRIA INRIA2 ANR
104 View
59 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More