{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,15]],"date-time":"2023-11-15T09:45:37Z","timestamp":1700041537854},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"Interpolation is a foundational concept in scientific computing and is at the heart of many scientific visualization techniques. There is usually a tradeoff between the approximation capabilities of an interpolation scheme and its evaluation efficiency. For many applications, it is important for a user to navigate their data in real time. In practice, evaluation efficiency outweighs any incremental improvements in reconstruction fidelity. We first analyze, from a general standpoint, the use of compact piece-wise polynomial basis functions to efficiently interpolate data that is sampled on a lattice. We then detail our automatic code-generation framework on both CPU and GPU architectures. Specifically, we propose a general framework that can produce a fast evaluation scheme by analyzing the algebro-geometric structure of the convolution sum for a given lattice and basis function combination. We demonstrate the utility and generality of our framework by providing fast implementations of various box splines on the Body Centered and Face Centered Cubic lattices, as well as some non-separable box splines on the Cartesian lattice. We also provide fast implementations for certain Voronoi-splines that have not yet appeared in the literature. Finally, we demonstrate that this framework may also be used for non-Cartesian lattices in 4D.<\/jats:p>","DOI":"10.1145\/3577194","type":"journal-article","created":{"date-parts":[[2022,12,20]],"date-time":"2022-12-20T12:52:51Z","timestamp":1671540771000},"page":"1-35","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["FastSpline: Automatic Generation of Interpolants for Lattice Samplings"],"prefix":"10.1145","volume":"49","author":[{"ORCID":"http:\/\/orcid.org\/0000-0001-5327-4847","authenticated-orcid":false,"given":"Joshua","family":"Horacsek","sequence":"first","affiliation":[{"name":"University of Calgary"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-4834-2475","authenticated-orcid":false,"given":"Usman","family":"Alim","sequence":"additional","affiliation":[{"name":"University of Calgary"}]}],"member":"320","published-online":{"date-parts":[[2023,6,15]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"crossref","first-page":"819","DOI":"10.1007\/978-3-319-27857-5_73","volume-title":"Advances in Visual Computing","author":"Akram Bita","year":"2015","unstructured":"Bita Akram, Usman R. Alim, and Faramarz F. Samavati. 2015. CINAPACT-Splines: A family of infinitely smooth, accurate and compactly supported splines. In Advances in Visual Computing. Springer International Publishing, Cham, 819\u2013829."},{"key":"e_1_3_2_3_1","volume-title":"Data Processing on the Body-centered Cubic Lattice","author":"Alim Usman R.","year":"2012","unstructured":"Usman R. Alim. 2012. Data Processing on the Body-centered Cubic Lattice. Ph.D. Dissertation. Simon Fraser University, Burnaby BC, Canada."},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/141000671"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/83.931101"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/78.790659"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/980175.980179"},{"key":"e_1_3_2_8_1","volume-title":"Sphere Packings, Lattices and Groups","author":"Conway John Horton","year":"2013","unstructured":"John Horton Conway and Neil James Alexander Sloane. 2013. Sphere Packings, Lattices and Groups. Vol. 290. Springer Science & Business Media."},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2013.7"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12917"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02109280"},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2244-4"},{"key":"e_1_3_2_13_1","first-page":"275","volume-title":"Proceedings of the 15th Vision, Modeling, and Visualization Workshop (VMV\u201910)","author":"Domonkos Bal\u00e1zs","year":"2010","unstructured":"Bal\u00e1zs Domonkos and Bal\u00e1zs Cs\u00e9bfalvi. 2010. DC-Splines: Revisiting the trilinear interpolation on the body-centered cubic lattice. In Proceedings of the 15th Vision, Modeling, and Visualization Workshop (VMV\u201910). 275\u2013282."},{"key":"e_1_3_2_14_1","article-title":"Towards computing on non-Cartesian lattices","author":"Entezari Alireza","year":"2006","unstructured":"Alireza Entezari. 2006. Towards computing on non-Cartesian lattices. IEEE Trans. Visualiz. Comput. Graph. (2006).","journal-title":"IEEE Trans. Visualiz. Comput. Graph."},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/VISUAL.2004.65"},{"key":"e_1_3_2_16_1","first-page":"1015","volume-title":"Computer Graphics Forum","author":"Entezari Alireza","year":"2009","unstructured":"Alireza Entezari, Mahsa Mirzargar, and Leila Kalantari. 2009. Quasi-interpolation on the body centered cubic lattice. In Computer Graphics Forum, Vol. 28. Wiley Online Library, 1015\u20131022."},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2006.141"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2007.70429"},{"key":"e_1_3_2_19_1","first-page":"346","volume-title":"Proceedings of the International Conference on High Performance Computing for Computational Science","author":"Fabregat-Traver Diego","year":"2012","unstructured":"Diego Fabregat-Traver and Paolo Bientinesi. 2012. A domain-specific compiler for linear algebra operations. In Proceedings of the International Conference on High Performance Computing for Computational Science. Springer, 346\u2013361."},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2010.02.002"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1972.5009071"},{"key":"e_1_3_2_22_1","unstructured":"Joshua Horacsek. 2021. Fast Spline. Retrieved from https:\/\/github.com\/jjh13\/fast-spline."},{"key":"e_1_3_2_23_1","article-title":"Fast and exact evaluation of box splines via the PP-form","author":"Horacsek J. J.","year":"2016","unstructured":"J. J. Horacsek and U. R. Alim. 2016. Fast and exact evaluation of box splines via the PP-form. ArXiv e-prints (June2016). arXiv:math.NA\/1606.08910.","journal-title":"ArXiv e-prints"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.gmod.2012.11.001"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.gmod.2012.11.001"},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2012.130"},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.gmod.2017.08.001"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2008.115"},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2008.115"},{"key":"e_1_3_2_30_1","unstructured":"Minho Kim Hyunjun Kim and Aaliya Sarfaraz. 2013. Efficient GPU isosurface ray-casting of BCC datasets. (2013)."},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11075-008-9231-6"},{"key":"e_1_3_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2010.11.027"},{"key":"e_1_3_2_33_1","article-title":"Dancing links","author":"Knuth Donald E.","year":"2000","unstructured":"Donald E. Knuth. 2000. Dancing links. arXiv preprint cs\/0011047 (2000).","journal-title":"arXiv preprint cs\/0011047"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019133501773"},{"key":"e_1_3_2_35_1","unstructured":"Chris Lattner and Vikram Adve. 2004. LLVM: A compilation framework for lifelong program analysis and transformation. San Jose CA 75\u201388."},{"key":"e_1_3_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/VISUAL.1994.346331"},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2010.2051808"},{"key":"e_1_3_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2011.230"},{"key":"e_1_3_2_39_1","volume-title":"GPU Gems 2: Programming Techniques for High-performance Graphics and General-Purpose Computation (GPU Gems)","author":"Pharr Matt","year":"2005","unstructured":"Matt Pharr and Randima Fernando. 2005. GPU Gems 2: Programming Techniques for High-performance Graphics and General-Purpose Computation (GPU Gems). Addison-Wesley Professional."},{"key":"e_1_3_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2830018.2830025"},{"key":"e_1_3_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02075467"},{"key":"e_1_3_2_42_1","article-title":"Nimble: Efficiently compiling dynamic neural networks for model inference","author":"Shen Haichen","year":"2020","unstructured":"Haichen Shen, Jared Roesch, Zhi Chen, Wei Chen, Yong Wu, Mu Li, Vin Sharma, Zachary Tatlock, and Yida Wang. 2020. Nimble: Efficiently compiling dynamic neural networks for model inference. arXiv preprint arXiv:2006.03031 (2020).","journal-title":"arXiv preprint arXiv:2006.03031"},{"key":"e_1_3_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10984-3_7"},{"key":"e_1_3_2_44_1","unstructured":"XLA Team et\u00a0al. 2017. XLA-TensorFlow Compiled. (2017)."},{"key":"e_1_3_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/79.799930"},{"key":"e_1_3_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.843002"},{"key":"e_1_3_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2004.827231"},{"key":"e_1_3_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.481786"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3577194","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,15]],"date-time":"2023-06-15T14:15:12Z","timestamp":1686838512000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3577194"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,15]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1145\/3577194"],"URL":"https:\/\/doi.org\/10.1145\/3577194","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,15]]},"assertion":[{"value":"2021-02-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-11","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}