ROBUST, VECTORIZED SEARCH ALGORITHMS FOR INTERPOLATION ON UNSTRUCTURED GRIDS

Several search algorithms for the interpolation of data associated with unstructured grids are reviewed and compared. Particular emphasis is placed on the pitfalls these algorithms may experience for grids commonly encountered and on ways to improve their performance. It is shown how the most CPU-intensive portions of the search process may be vectorized. A technique for the proper interpolation of volumetric regions separated by thin surfaces is included. Timings for several problems show that speedups in excess of 1:5 can be obtained if due care is used when designing interpolation algorithms. (c) 1995 Academic Press, Inc.