The pace of advancement of the top-end supercomputers historically followed an exponential curve similar to (and driven in part by) Moore's Law. Shortly after hitting the petaflop mark, the community started looking ahead to the next milestone: Exascale. However, many obstacles were already looming on the horizon, such as the slowing of Moore's Law, and others like the end of Dennard Scaling had already arrived. Anticipating significant challenges for the overall high-performance computing (HPC) community to achieve the next 1000x improvement, the U.S. Department of Energy (DOE) launched the Exascale Computing Program to enable and accelerate fundamental research across the many technologies needed to achieve exascale computing.

Matrix operations are common and expensive computations in a variety of applications. They occur frequently in high-performance computing, graphics, graph processing, and machine learning applications. This paper discusses how to map a variety of important matrix computations, including sparse matrix-vector multiplication (SpMV), sparse triangle solve (SpTS), graph processing, and dense matrix-matrix multiplication, to GPUs. Since many emerging systems will use heterogeneous architectures (e.g. CPUs and GPUs) to attain the desired performance targets under strict power constraints, this paper discusses implications and future research for matrix processing with heterogeneous designs. Conclusions common to the matrix operations discussed in this paper are: (1) Future algorithms should be written to ensure that the essential computations fit into local memory, which may require direct programmer management. (2) Algorithms are needed that expose high levels of parallelism. (3) While the scale of computation is often sufficient to support algorithms with superior asymptotic order, additional considerations, such as memory capacity and bandwidth, must also be carefully managed. (4) Libraries should be used to provide portable performance.

In this paper we show that in sorting-based applications of parametric search, Quicksort can replace the parallel sorting algorithms that are usually advocated, and we argue that Cole's optimization of certain parametric-search algorithms may be unnecessary under realistic assumptions about the input. Furthermore, we present a generic, flexible, and easy-to-use framework that greatly simplifies the implementation of algorithms based on parametric search. We use our framework to implement an algorithm that solves the Fréchet-distance problem. The implementation based on parametric search is faster than the binary-search approach that is often suggested as a practical replacement for the parametric-search technique.

A new hierarchical decomposition of a simple polygon is introduced. The hierarchy has depth O(log n), linear size, and its regions have maximum degree three. Using this hierarchy, circular ray shooting queries in a simple polygon can be answered in O(log* n) query time and O(nlogn) space. If the radius of the circle is fixed, the query time can be improved to O(logn) and the space to O(n). The decomposition is also applied to three other circular arc query problems: shortest directed arc, arc bending, and arc pushing. Using these queries, the largest empty lune determined by two query points in a simple polygon can be computed in O(log3 n) time, while the circular visibility region of a query point in a simple polygon can be reported in time O(m log3 n), where m is the output size.

For 2D or 3D meshes that represent a continuous function to the reals, the contours---or isosurfaces---of a specified value are an important way to visualize it. To find such contours, a seed set can be used for the starting points from which the traversal of the contours can start. This paper gives the first methods to obtain seed sets that are provably small in size. They are based on a variant of the contour tree (or topographic change tree). We give a new, simple algorithm to compute such a tree in regular and irregular meshes that requires O(n log n) time in 2D for meshes with n elements, and in O(n 2 ) time in higher dimensions. The additional storage overhead is proportial to the maximum size of any contour (linear in the worst case, but typically less). Given the contour tree, a minimum size seed set can be computed in polynomial time and storage. Since in practice at most linear storage is allowed, we develop a simple approximation algorithm giving a seed set of size at most...

In this paper we show how to traverse a subdivision and to report all cells, edges and vertices, without making use of mark bits in the structure or a stack. We do this by performing a depth-first search on the subdivision, using local criteria for deciding what is the next cell to visit. Our method is extremely simple and provably correct. The algorithm has applications in the field of geographic information systems (GIS), where traversing subdivisions is a common operation, but modifying the database is unwanted or impossible. We show how to adapt our algorithm to answer related queries, such as windowing queries and reporting connected subsets of cells that have a common attribute. Finally, we show how to extend our algorithm such that it can handle convex threedimensional subdivisions.

In this note we show how to traverse a subdivision and to report all cells, edges and vertices, without making use of mark bits in the structure or a stack.We do this by performing a depth-first search on the subdivision, using local criteriafor deciding what is the next cell to visit.Our method is extremely simple.The algorithm has applications in the field of Geographic Information Systems (GIS), where traversing subdivisions is a common operation, but modifying the database is unwanted or impossible.We can adapt our algorithm to answer related queries, such as windowing queries, reporting connected subsets of cells that have a common attribute, and reporting in 3-dimensional convex subdivisions.