Internal versus external balancing in the evaluation of graph-based number types
For developers of exact computation libraries, this work provides guidance on optimizing number type performance by choosing between graph restructuring and error bound balancing.
The paper compares two strategies for improving the evaluation efficiency of graph-based exact number types: restructuring the graph versus internally balancing error bounds. Experimental results show that internal balancing can significantly improve performance without the overhead of graph restructuring.
Number types for exact computation are usually based on directed acyclic graphs. A poor graph structure can impair the efficency of their evaluation. In such cases the performance of a number type can be drastically improved by restructuring the graph or by internally balancing error bounds with respect to the graph's structure. We compare advantages and disadvantages of these two concepts both theoretically and experimentally.