Linearizing polynomial circuits #
Affine circuits compute affine functions (Frontier.exists_affine_trace): in a circuit over
the affine basis, the value of every wire is an affine function of the input.
Linearization (Frontier.exists_affine_circuit). Over an infinite field, a circuit with
polynomial operations that computes a linear map x ↦ M x can be replaced by a circuit over
the affine basis, with the same wires, that computes the same map. Each gate is replaced by its
first-order Taylor expansion at the point its arguments take when the input is zero
(Frontier.taylorOp, Frontier.linearize).
To see why this works, evaluate the circuit over the dual numbers F[ε], where ε² = 0, at the
input ε x. Because the operations are polynomials, a gate whose arguments are z + ε v takes
the value P(z) + ε ∑_a ∂_a P(z) v_a (Frontier.snd_aeval_dualNumber), and z is the value of
the arguments at the zero input. So where the circuit takes the value a + ε b at ε x, the
linearized circuit takes the value a + b at x (Frontier.trace_linearize). Over an
infinite field a polynomial is determined by its values, so the polynomial computed at an output
is the linear form ∑_j M_{ij} X_j, whose value at ε x is ε (M x)_i.
Affine circuits compute affine functions.
Polynomial interpretations over algebras #
The interpretation over an F-algebra R in which each operation o substitutes its
arguments into the polynomial P o. Every polynomial interpretation over F is of this form,
for a suitable choice of the polynomials P.
Equations
- Complexity.Frontier.polynomialInterpretation P R o x = (MvPolynomial.aeval x) (P o)
Instances For
An operation of a polynomial interpretation substitutes its arguments into its polynomial.
Evaluation of a program with polynomial operations commutes with algebra homomorphisms.
First-order Taylor expansion #
The real part of a polynomial at a dual number is its value at the real parts.
Taylor expansion over the dual numbers. The dual part of P(z + ε v) is
∑_a ∂_a P(z) v_a.
The affine operation computing the first-order Taylor expansion of P at z,
y ↦ P(z) + ∑_a ∂_a P(z) (y_a - z_a).
Equations
- One or more equations did not get rendered due to their size.
Instances For
The value of the first-order Taylor expansion of P at z.
Linearization #
The linearization of a program whose operations are the polynomials P: the program over
the affine basis with the same wires, in which each gate is replaced by its first-order Taylor
expansion at the point that its arguments take on the zero input.
Equations
- One or more equations did not get rendered due to their size.
- Complexity.Frontier.linearize P Cslib.Circuits.Program.empty = Cslib.Circuits.Program.empty
Instances For
Linearization preserves the arity of every gate.
Linearization preserves the inner gates.
Linearization preserves fan-in.
The real part of the value of a wire at the input ε x is its value at the zero input.
The linearized program. Where the original program takes the value a + ε b at the
input ε x, the linearized program takes the value a + b at the input x.
Over an infinite field, a circuit with polynomial operations that computes x ↦ M x takes
the value ε (M x)_i at its output i on the input ε x.
Linearization. Over an infinite field, a circuit with polynomial operations computing a linear map is matched by a circuit over the affine basis computing the same map, with the same number of gates, the same inner gates, and the same fan-in.