Robust, vectorized search algorithms for interpolation on unstructured grids
type: Item
instance of: scholarly article
title: Robust, vectorized search algorithms for interpolation on unstructured grids
zbMATH Open document ID: 0826.65007
author: Rainald Löhner
published in: Journal of Computational Physics
publication date: 1995-11-26T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65D05
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 41A63
Mathematics Subject Classification ID: 41A05
zbMATH DE Number: 758641
zbMATH Keywords: search algorithms
zbMATH Keywords: unstructured grids
zbMATH Keywords: performance
zbMATH Keywords: interpolation algorithms
reviewed by: H. P. Dikshit
MaRDI profile type: Publication
full work available at URL: jcph.1995.1107
OpenAlex ID: W2141846244
DOI: 10.1006/JCPH.1995.1107
description: scientific article; zbMATH DE number 758641