Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Jacques-Henri Jourdan Connect in order to contact the contributor
Submitted on : Thursday, December 1, 2016 - 3:33:38 PM
Last modification on : Friday, January 21, 2022 - 3:19:22 AM
Long-term archiving on: : Monday, March 20, 2017 - 8:45:01 PM


Files produced by the author(s)


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



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⟩



Les métriques sont temporairement indisponibles