Wengert

In numerical analysis and computer science, the term "Wengert list" or "Wengert tape" refers to a directed acyclic graph (DAG) representing a computational procedure, particularly for evaluating mathematical expressions. These lists are used to track the sequence of operations performed during a calculation, enabling techniques like automatic differentiation (also known as algorithmic differentiation or computational differentiation).

The fundamental idea behind a Wengert list is to decompose a complex mathematical function into a series of elementary operations (such as addition, subtraction, multiplication, division, trigonometric functions, and exponentiation). Each operation is represented as a node in the DAG, with edges indicating the flow of data (operands) between the operations. The input variables of the function are represented as source nodes (nodes with no incoming edges), and the final result of the computation is represented as a sink node (a node with no outgoing edges).

During the forward pass, the Wengert list is traversed in topological order, and each operation is executed using the values of its operands (which were computed in earlier steps). This process computes the value of the function.

Automatic differentiation uses the Wengert list to compute derivatives. The chain rule of calculus is applied by traversing the Wengert list in reverse order (backward pass). During this backward pass, the derivative of the output with respect to each intermediate variable and input variable is computed. The derivatives of the elementary operations are well-known, allowing for efficient computation of the overall derivative.

Wengert lists provide an efficient way to store and manipulate computational procedures, making them valuable for automatic differentiation and related optimization techniques. They provide an intermediate representation suitable for many forms of program analysis and transformation beyond simply computing gradients.