Skip to main content
Kent Academic Repository

Exploiting Sparsity in Polyhedral Analysis: 12th International Symposium, SAS 2005, London, UK, September 7-9, 2005. Proceedings

Simon, Axel and King, Andy (2005) Exploiting Sparsity in Polyhedral Analysis: 12th International Symposium, SAS 2005, London, UK, September 7-9, 2005. Proceedings. In: Hankin, Chris and Siveroni, Igor, eds. Static Analysis Symposium. Lecture Notes in Computer Science, 3672 . Springer, pp. 336-351. ISBN 978-3-540-28584-7. (doi:10.1007/11547662_23) (KAR id:37606)

Abstract

The intrinsic cost of polyhedra has lead to research on more tractable sub-classes of linear inequalities. Rather than committing to the precision of such a sub-class, this paper presents a projection algorithm that works directly on any sparse system of inequalities and which sacrifices precision only when necessary. The algorithm is based on a novel combination of the Fourier-Motzkin algorithm (for exact projection) and Simplex (for approximate projection). By reformulating the convex hull operation in terms of projection, conversion to the frame representation is avoided altogether. Experimental results conducted on logic programs demonstrate that the resulting analysis is efficient and precise.

Item Type: Book section
DOI/Identification number: 10.1007/11547662_23
Subjects: A General Works
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Andy King
Date Deposited: 13 Dec 2013 08:16 UTC
Last Modified: 05 Nov 2024 10:21 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/37606 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.