School of Computing

Exploiting Sparsity in Polyhedral Analysis

Axel Simon and Andy King

In Chris Hankin, editor, Twelfth International Static Analysis Symposium, volume 3672 of Lecture Notes in Computer Science, pages 336-351. Springer Verlag, September 2005 Also see http://www.springer.de/comp/lncs/index.html.

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.

Download publication 410 kbytes (PostScript)

Bibtex Record

@inproceedings{2212,
author = {Axel Simon and Andy King},
title = {{E}xploiting {S}parsity in {P}olyhedral {A}nalysis},
month = {September},
year = {2005},
pages = {336-351},
keywords = {abstract interpretation, polyhedral analysis, argument-size analysis, computational geometry},
note = {Also see http://www.springer.de/comp/lncs/index.html.},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/2005/2212},
    volume = {3672},
    publication_type = {inproceedings},
    submission_id = {15483_1117618756},
    booktitle = {Twelfth International Static Analysis Symposium},
    editor = {Chris Hankin},
    series = {Lecture Notes in Computer Science},
    publisher = {Springer Verlag},
    refereed = {yes},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 12/03/2012 17:22