About the Software
DELAUNAYSPARSE [1] contains both serial and parallel codes written in Fortran 2003 (with OpenMP 4.5) for performing medium- to high-dimensional interpolation via the Delaunay triangulation. To accommodate the exponential growth in the size of the Delaunay triangulation in high dimensions, DELAUNAYSPARSE computes only a sparse subset of the complete Delaunay triangulation, as necessary for performing interpolation at the user specified points. DELAUNAYSPARSE implements the algorithm in [2] and has been used for various applications including aerospace engineering [3], HPC performance modeling [4],[5], nonparametric statistics [6], machine learning regression [7], and graph generation [8].
An update to DELAUNAYSPARSE was recently published in [9], improving our methodology for projecting extrapolation points onto the convex hull.
Publications
[1] T. H. Chang, L. T. Watson, T. C. H. Lux, A. R. Butt, K. W. Cameron, and Y. Hong, "Algorithm 1012: DELAUNAYSPARSE: Interpolation via a Sparse Subset of the Delaunay triangulation in Medium to High Dimensions", ACM Trans. Math. Software, 46, Article 38 (2020), 20 pages.
[2] T. H. Chang, L. T. Watson, T. C. H. Lux, B. Li, L. Xu, A. R. Butt, K. W. Cameron, and Y. Hong, "A polynomial time algorithm for multivariate interpolation in arbitrary dimension via the Delaunay triangulation", in Proc. 2018 ACMSE Conference., Association of Computing Machinery, Richmond, KY, USA, 2018, Article No. 13.
[3] M. Jrad, R. K. Kapania, J. A. Schetz, and L. T. Watson, "Self-learning, adaptive software for aerospace engineering applications: Example of oblique shocks in supersonic flow", in AIAA Scitech 2019 Forum, American Institute of Aeronautics and Astronautics, Inc., San Diego, CA, USA, 2019, 1704.
[4] T. H. Chang, L. T. Watson, T. C. H. Lux, J. Bernard, B. Li, L. Xu, G. Back, A. R. Butt, K. W. Cameron, and Y. Hong, "Predicting system performance by interpolation using a high-dimensional Delaunay triangulation", in Proc. SpringSim 2018, the 26th High Performance Computing Symposium (HPC '18), Society for Modeling and Simulation International, Baltimore, MD, USA, 2018, Article No. 2.
[5] T. C. H. Lux, L. T. Watson, T. H. Chang, J. Bernard, B. Li, L. Xu, G. Back, A. R. Butt, K. W. Cameron, and Y. Hong, "Predictive modeling of I/O characteristics in high performance computing systems", in Proc. SpringSim 2018, the 26th High Performance Computing Symposium (HPC '18), Society for Modeling and Simulation International, Baltimore, MD, USA, 2018, Article No. 8.
[6] T. C. H. Lux, L. T. Watson, T. H. Chang, J. Bernard, B. Li, X. Yu, L. Xu, A. R. Butt, K. W. Cameron, Y. Hong, and D. Yao, "Nonparametric distribution models for predicting and managing computational performance variability", in Proc. IEEE SoutheastCon 2018, Institute of Electrical and Electronics Engineers, St. Petersburg, FL, USA, 2018, 7 pages.
[7] T. C. H. Lux, L. T. Watson, T. H. Chang, Y. Hong, and K. W. Cameron, "Interpolation of sparse high-dimensional data", Numerical Algorithms, (2020) 33 pages.
[8] T. H. Chang, "Mathematical Software for Multiobjective Optimization Problems". Ph.D. thesis, Virginia Polytechnic Institute and State University, Blacksburg, VA, USA, 2020.
[9] T. H. Chang, L. T. Watson, S. Leyffer, T. C. H. Lux, and H. M. J. Almohri, "Remark on Algorithm 1012: Computing projections with large data sets", ACM Trans. Math. Software, to appear (2024), 8 pages.