Restructuring expression dags for efficient parallelization

DOI10.4230/LIPICS.SEA.2018.20MaRDI QIDQ5140732zbMATH OpenOpenAlexFDO

Authors Martin Wilhelm

Publication date 16 December 2020

Full work available at URL https://arxiv.org/abs/1804.03256

zbMATH Keywords

exact computationrestructuringparallel evaluationexpression dag

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)

Abstract: In the field of robust geometric computation it is often necessary to make exact decisions based on inexact floating-point arithmetic. One common approach is to store the computation history in an arithmetic expression dag and to re-evaluate the expression with increasing precision until an exact decision can be made. We show that exact-decisions number types based on expression dags can be evaluated faster in practice through parallelization on multiple cores. We compare the impact of several restructuring methods for the expression dag on its running time in a parallel environment.

Recommendations

• Deferring Dag Construction by Storing Sums of Floats Speeds-Up Exact Decision Computations Based on Expression Dags
• Balancing Expression Dags for More Efficient Lazy Adaptive Evaluation
• Recent progress in exact geometric computation
• Computations that require higher than double precision for robust and exact decision making
• Fast floating-point filters for robust predicates

Cites work

• scientific article; zbMATH DE number 1424302 (Why is no real title available?)
• A separation bound for real algebraic expressions
• Balancing Expression Dags for More Efficient Lazy Adaptive Evaluation
• On design and implementation of a generic number type for real algebraic number computations based on expression dags
• Precision-driven computation in the evaluation of expression-dags with common subexpressions: problems and solutions
• The Design of Core 2: A Library for Exact Numeric Computation in Geometry and Algebra
• The Parallel Evaluation of General Arithmetic Expressions
• Towards exact geometric computation

Cited in

(5)

• Scheduling expression DAGs for minimal register need
• Balancing Expression Dags for More Efficient Lazy Adaptive Evaluation
• Computations that require higher than double precision for robust and exact decision making
• Dag-calculus: a calculus for parallel computation
• Deferring Dag Construction by Storing Sums of Floats Speeds-Up Exact Decision Computations Based on Expression Dags

Describes a project that uses

Uses Software

• core 2
• LEDA

This page was built for publication: Restructuring expression dags for efficient parallelization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5140732)