Efficient and Scalable Data Structuresfor Topological Geometric Models

Principal Investigator: Dinesh Manocha
Funding Agency: Univ. of California Lawrence Livermore National Laboratory 
Agency Number: B555268

Abstract

The scope of this contract includes the development of data structures and algorithms that properly support the efficient implementation of topological algorithms by exploiting and enhancing their practical performance on modern workstations with complex memory hierarchies. Given the variety and complexity of the topological methods for which we want to use the results of this work, we will focus our attention of general-purpose techniques that can be applied broadly without specialization to a particular algorithm. In particular this work includes a study of the performance variations induced by permutations of the elements used to describe the input models (e.g. vertices of the domain mesh). Main challenges in this work include: (i) the development of a metric that allows assessing the A?qualityA? of a permutation or to predict the correlation between permutation and practical performance of an algorithm, (ii) efficient computation of different permutations in external memory, (iii) use of a multilevel optimization schemes for fast search of permutations with good quality.