An algebraic branching program (ABP) over a field is an edge-labeled acyclic digraph with a distinguished
source 
and target 
.
Thus, it is a directed graph in which every edge
points from the source toward the target and no directed cycles occur. Edge labels
are usually variables or affine linear forms, i.e., expressions of the form 
,
which are affine functions of the variables. The
polynomial computed by the program is
 |
where the product is taken in path order. The same definition can be made over a semiring; for noncommuting labels, the order of the factors is essential.
An algebraic branching program is layered if every edge goes from one layer to the next. Its width is the maximum number of vertices in a layer. If the transition matrices
between successive layers are 
, 
, ..., 
, then the computed polynomial is an entry, or more generally
a bilinear form,
 |
of their product. Thus bounded-width algebraic branching programs are closely related to iterated matrix multiplication (Bringmann et al. 2018).
The size of an algebraic branching program is commonly measured by its number of vertices or edges, depending on convention. This is a shared directed graph model and therefore differs from the size of an algebraic formula, in which every repeated occurrence of a subexpression is counted separately. Algebraic branching programs are used in algebraic complexity over both commutative rings and noncommutative rings (Nisan 1991).
