Sparsity Preserving Algorithms for Octagons

Jourdan, Jacques-Henri

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

成果報告書

Sparsity Preserving Algorithms for Octagons

MPS-Authors

/persons/resource/persons204899

Jourdan, Jacques-Henri
Group D. Dreyer, Max Planck Institute for Software Systems, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

arXiv:1612.00277.pdf
(プレプリント), 206KB

付随資料 (公開)

There is no public supplementary material available

引用

Jourdan, J.-H. (2016). Sparsity Preserving Algorithms for Octagons. Retrieved from http://arxiv.org/abs/1612.00277.

引用: https://hdl.handle.net/11858/00-001M-0000-002D-21D6-C

要旨

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.