Robust, vectorized search algorithms for interpolation on unstructured grids (Q1891117)

Several search algorithms for the interpolation of data associated with unstructured grids are reviewed and compared [e.g. \textit{D. E. Knuth}, The art of computer programming, Vol. 1: Fundamental algorithms (1968; Zbl 0191.179); Vol. 2: Seminumerical algorithms (1969; Zbl 0191.180); Vol. 3: Sorting and searching (1974; Zbl 0302.68010)]. The author highlights the pitfalls of these algorithms in reference to commonly encountered grids and the ways to improve their performance. It is shown that the most CPU-intensive portions of the search process may be vectorised. Timings of several problems show that speedups in excess of 1:5 can be achieved by appropriately designing interpolation algorithms. It is proposed that the above approach should be useful in field simulations with moving bodies, interdisciplinary problems approached via loose coupling, initialization and boundary condition update for field solvers attached to a discrete data base and visualization.