{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T10:03:45Z","timestamp":1777889025685,"version":"3.51.4"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T00:00:00Z","timestamp":1605225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Schweizerischer Nationalfonds zur Foerderung der Wissenschaftlichen Forschung","award":["PZ00P2168016"],"award-info":[{"award-number":["PZ00P2168016"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2020,11,13]]},"abstract":"<jats:p>A plethora of program analysis and optimization techniques rely on linear programming at their heart. However, such techniques are often considered too slow for production use. While today\u2019s best solvers are optimized for complex problems with thousands of dimensions, linear programming, as used in compilers, is typically applied to small and seemingly trivial problems, but to many instances in a single compilation run. As a result, compilers do not benefit from decades of research on optimizing large-scale linear programming. We design a simplex solver targeted at compilers. A novel theory of transprecision computation applied from individual elements to full data-structures provides the computational foundation. By carefully combining it with optimized representations for small and sparse matrices and specialized small-coefficient algorithms, we (1) reduce memory traffic, (2) exploit wide vectors, and (3) use low-precision arithmetic units effectively. We evaluate our work by embedding our solver into a state-of-the-art integer set library and implement one essential operation, coalescing, on top of our transprecision solver. Our evaluation shows more than an order-of-magnitude speedup on the core simplex pivot operation and a mean speedup of 3.2x (vs. GMP) and 4.6x (vs. IMath) for the optimized coalescing operation. Our results demonstrate that our optimizations exploit the wide SIMD instructions of modern microarchitectures effectively. We expect our work to provide foundations for a future integer set library that uses transprecision arithmetic to accelerate compiler analyses.<\/jats:p>","DOI":"10.1145\/3428263","type":"journal-article","created":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T23:36:06Z","timestamp":1606260966000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Fast linear programming through transprecision computing on small and sparse data"],"prefix":"10.1145","volume":"4","author":[{"given":"Tobias","family":"Grosser","sequence":"first","affiliation":[{"name":"University of Edinburgh, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Theodoros","family":"Theodoridis","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maximilian","family":"Falkenstein","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arjun","family":"Pitchanathan","sequence":"additional","affiliation":[{"name":"IIIT Hyderabad, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Kruse","sequence":"additional","affiliation":[{"name":"Argonne National Laboratory, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuel","family":"Rigger","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhendong","family":"Su","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Torsten","family":"Hoefler","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,11,13]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/pact.2015.17"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2007.08.001"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158120"},{"key":"e_1_2_2_4_1","volume-title":"Introduction to linear optimization","author":"Bertsimas Dimitris","unstructured":"Dimitris Bertsimas and John N Tsitsiklis . 1997. Introduction to linear optimization . Vol. 6 . Athena Scientific Belmont , MA. Dimitris Bertsimas and John N Tsitsiklis. 1997. Introduction to linear optimization. Vol. 6. Athena Scientific Belmont, MA."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/17m1140819"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/73141.74831"},{"key":"e_1_2_2_7_1","unstructured":"Sharan Chetlur Clif Woolley Philippe Vandermersch Jonathan Cohen John Tran Bryan Catanzaro and Evan Shelhamer. 2014. cudnn: Eficient primitives for deep learning. arXiv preprint arXiv:1410.0759 ( 2014 ).  Sharan Chetlur Clif Woolley Philippe Vandermersch Jonathan Cohen John Tran Bryan Catanzaro and Evan Shelhamer. 2014. cudnn: Eficient primitives for deep learning. arXiv preprint arXiv:1410.0759 ( 2014 )."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.2307\/3621190"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066100.1066102"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/icse.2012.6227142"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1051\/ro\/1988220302431"},{"key":"e_1_2_2_12_1","unstructured":"M. J. Fromberger. 2019. imath. https:\/\/github.com\/creachadair\/imath. Accessed: 2019-04-25.  M. J. Fromberger. 2019. imath. https:\/\/github.com\/creachadair\/imath. Accessed: 2019-04-25."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.21236\/ada124397"},{"key":"e_1_2_2_14_1","unstructured":"Torbjrn Granlund et al. 2015. GNU MP 6.0 Multiple precision arithmetic library. Samurai Media Limited.  Torbjrn Granlund et al. 2015. GNU MP 6.0 Multiple precision arithmetic library. Samurai Media Limited."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2544137.2544160"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2925426.2926286"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2743016"},{"key":"e_1_2_2_18_1","volume-title":"International Conference on Machine Learning. 1737-1746","author":"Gupta Suyog","year":"2015","unstructured":"Suyog Gupta , Ankur Agrawal , Kailash Gopalakrishnan , and Pritish Narayanan . 2015 . Deep learning with limited numerical precision . In International Conference on Machine Learning. 1737-1746 . Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan. 2015. Deep learning with limited numerical precision. In International Conference on Machine Learning. 1737-1746."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314606"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3242953.3242964"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-93698-7_45"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/sc.2018.00050"},{"key":"e_1_2_2_23_1","unstructured":"Jared Hoberock. 2019. C+ + Extensions for Parallelism Version 2 ( Working Draft N4808 ). Accessed: 2019-07-22.  Jared Hoberock. 2019. C+ + Extensions for Parallelism Version 2 ( Working Draft N4808 ). Accessed: 2019-07-22."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/143095.143114"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/178243.178478"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/77726.255144"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1369396.1370017"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/130930352"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/cgo.2004.1281665"},{"key":"e_1_2_2_30_1","unstructured":"Vincent Loechner. 1999. PolyLib: A library for manipulating parameterized polyhedra.  Vincent Loechner. 1999. PolyLib: A library for manipulating parameterized polyhedra."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.17.3.751"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ipdpsw.2018.00091"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11515-8_10"},{"key":"e_1_2_2_34_1","volume-title":"Techniques for program verification. Xerox","author":"Nelson Charles Gregory","unstructured":"Charles Gregory Nelson . 1981. Techniques for program verification. Xerox . Palo Alto Research Center . Charles Gregory Nelson. 1981. Techniques for program verification. Xerox. Palo Alto Research Center."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3330345.3330377"},{"key":"e_1_2_2_36_1","volume-title":"Polybench: The polyhedral benchmark suite. ( 2012 ).","author":"Pouchet Louis-No\u00ebl","year":"2012","unstructured":"Louis-No\u00ebl Pouchet . 2012 . Polybench: The polyhedral benchmark suite. ( 2012 ). Louis-No\u00ebl Pouchet. 2012. Polybench: The polyhedral benchmark suite. ( 2012 )."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375594"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/cgo.2007.21"},{"key":"e_1_2_2_39_1","first-page":"92","volume-title":"Warsaw ( 1929 )","author":"Presburger Mojzesz","unstructured":"Mojzesz Presburger . 1929. \u00dcber die Vollst\u00e4ndigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt in Comptes Rendus du I congres de Math\u00e9maticiens des Pays Slaves. Slaves , Warsaw ( 1929 ) , 92 - 101 . Mojzesz Presburger. 1929. \u00dcber die Vollst\u00e4ndigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt in Comptes Rendus du I congres de Math\u00e9maticiens des Pays Slaves. Slaves, Warsaw ( 1929 ), 92-101."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3338906.3338907"},{"key":"e_1_2_2_41_1","unstructured":"A Schriver. 1986. Theory of integer and linear programming.  A Schriver. 1986. Theory of integer and linear programming."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429069.2429127"},{"key":"e_1_2_2_43_1","volume-title":"Tensor comprehensions: Framework-agnostic high-performance machine learning abstractions. arXiv preprint arXiv","author":"Vasilache Nicolas","year":"1802","unstructured":"Nicolas Vasilache , Oleksandr Zinenko , Theodoros Theodoridis , Priya Goyal , Zachary DeVito , William S Moses , Sven Verdoolaege , Andrew Adams , and Albert Cohen . 2018. Tensor comprehensions: Framework-agnostic high-performance machine learning abstractions. arXiv preprint arXiv : 1802 . 04730 ( 2018 ). Nicolas Vasilache, Oleksandr Zinenko, Theodoros Theodoridis, Priya Goyal, Zachary DeVito, William S Moses, Sven Verdoolaege, Andrew Adams, and Albert Cohen. 2018. Tensor comprehensions: Framework-agnostic high-performance machine learning abstractions. arXiv preprint arXiv: 1802. 04730 ( 2018 )."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15582-6_49"},{"key":"e_1_2_2_45_1","volume-title":"International Workshop on Polyhedral Compilation Techniques, Date: 2015 \/01\/19-2015\/01\/19","author":"Verdoolaege Sven","year":"2015","unstructured":"Sven Verdoolaege . 2015 . Integer set coalescing . In International Workshop on Polyhedral Compilation Techniques, Date: 2015 \/01\/19-2015\/01\/19 , Location : Amsterdam, The Netherlands. Sven Verdoolaege. 2015. Integer set coalescing. In International Workshop on Polyhedral Compilation Techniques, Date: 2015 \/01\/19-2015\/01\/19, Location: Amsterdam, The Netherlands."},{"key":"e_1_2_2_46_1","first-page":"22","article-title":"Integer Set Library: Manual","volume":"0","author":"Verdoolaege Sven","year":"2020","unstructured":"Sven Verdoolaege . 2020 . Integer Set Library: Manual , Version 0 . 22 .1. Retrieved from http:\/\/isl.gforge. inria.fr\/manual.pdf on 31.08. 2020. Sven Verdoolaege. 2020. Integer Set Library: Manual, Version 0.22.1. Retrieved from http:\/\/isl.gforge. inria.fr\/manual.pdf on 31.08. 2020.","journal-title":"Version"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2400682.2400713"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68564-7_7"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2509578.2509581"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-017-1116-6_8"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428263","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3428263","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:57Z","timestamp":1750197777000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428263"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,13]]},"references-count":50,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2020,11,13]]}},"alternative-id":["10.1145\/3428263"],"URL":"https:\/\/doi.org\/10.1145\/3428263","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,13]]},"assertion":[{"value":"2020-11-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}