Algebraic simplifiers are submodules of the SimianQuant processing pipeline that use isomorphisms of the rules taught in algebra class to reduce expression complexity. They are significantly more powerful than the constant folders and common subexpression eliminators that are a part of modern compilers, and are a major contributor to the performance step achieved by the library. This article illustrates that contribution.

Newcomers to the library often view algebraic simplification as a cute party trick, akin to pedagogic tools like cymath. While the algebraic simplifiers are functionally equivalent to these pedagogic tools for simple expressions with a dozen or so terms, their design principles are fundamentally different. They are industrial strength tools engineered to operate on large expressions, with more than a hundred thousand terms.

This article demonstrates the performance delta they can deliver over and above what mainstream optimizing compilers can achieve by considering several families of interpolators. In the examples that follow, the label degenerate refers to implementations generated with the simplifier modules turned off and simplified refers to cases with the modules turned on (which is obviously the default).

All measurements were made on an AWS c5 instance running at a clock speed of 3GHz.

One Dimensional

Axiomatically, only algebraically complex expressions are amenable to algebraic simplification. Linear interpolators fall below the threshold of the required complexity, and there isn’t much that the simplifiers can do to improve their performance. Cubic spline interpolators are marginally more complex, and the consequence of algebraic simplification is best illustrated by considering the evaluation of parametric sensitivity.

As the figure illustrates, algebraic simplification improves performance by a factor of approximately three. It should be noted that even without algebraic simplification, the SimianQuant implementations are more than 100x faster than their corresponding Strata implementations, as presented here.

Two Dimensional

The second class of problems considered is two-dimensional interpolation over a rectangular grid, with 11 points along the x-axis and 5 points along the y-axis. Here, the simplifiers reduce the two-dimensional problem into effectively a one-dimensional problem over a synthetic index.

For bilinear interpolation, this yields an approximately 6x improvement in performance. Obviously, the delta the simplifiers can deliver grows with the complexity of the initial expression. This is shown by the linearcubic case, where an 11x step was achieved.

Considering the results presented here, even without algebraic simplification, the SimianQuant implementation for bilinear interpolation is close to 3x faster and that for linearcubic interpolation is close to 14x faster than the corresponding Strata implementation. This is due to optimizations performed by modules downstream of algebraic simplification, which will be described in a future blog post.

Two Dimensional Parametric Sensitivity

The consequences of reducing the algebraic complexity become more pronounced as the atomic operations of the underlying field become more complex. To illustrate, consider the same interpolators as the previous section, but implemented over a dual field (for parametric sensitivity using algorithmic differentiation) instead of over a real field.

In this case, a 9x step is achieved for the bilinear case, compared with the 6x step of the previous section. In the linearcubic case, a 31x step is achieved compared with the 11x step of the previous section.

Harshad

There are no good kings, only beautiful palaces.