ICS 2011

Welcome to ICS2011

Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, 87-100, 978-7-302-24517-9
Tsinghua University Press

Extracting Roots of Arithmetic Circuits by Adapting Numerical Methods Authors : Maurice Jansen [Download PDF]

Abstract:
For two polynomials f ∈ F[x1, x2,...,xn, y] and p ∈ F[x1, x2,..., xn], we say that p is a root of f, if f(x1, x2,..., xn, p) ≡ 0. We study the relation between the arithmetic circuit sizes of f and p for general circuits and algebraic branching programs. An algebraic branching program (ABP) is given by a layered directed acyclic graph with source σ and sink τ , whose edges are labeled by variables or field constants. It computes the sum of weights of all paths from σ to τ, where the weight of a path is defined as the product of edge-labels on the path. For the size of an ABP we count the number of nodes in the underlying graph.
We address the following fundamental question: suppose the polynomial f can be computed by an ABP of sizes. Is the ABP size of every root p of f guaranteed to be bounded by a polynomial in s? For general circuits it is known that the circuit size of any root p of a polynomial f with circuit size s is at most poly(s,deg(p),m), where m is the multiplicity of p in f, i.e. m is the largest number such that (p − y)m divides f. This bound follows from a result about factors of arithmetic circuits independently obtained by Kaltofen [1] and Bürgisser [2].
In this paper, we study the above question for ABPs for the canonical case where f is assumed to factor as f = p0 · (p1 − y)(p2 − y)...(pr − y), for p0, p1,..., pr ∈ F[x1, x2,..., xn] with p0 ≡ 0, and where p1, p2,..., pr are pairwise distinct, i.e. all multiplicities are one. Our main result is that for this situation, provided F has characteristic zero, any root pi can be computed by an ABP of size polynomial in s. This demonstrates an important special case where the answer to the above mentioned question is a±rmative. To prove the above result, we view the question as a problem of computing eigenvalues. Roughly, the pis are made to appear as the eigenvalues of some matrix over the field F(x1, x2,..., xn) of rational functions. This problem is then solved by adapting the numerical method of power iteration to our situation. Using power iteration makes the computation amenable to be coded out as an ABP, since ABPs can efficiently compute iterated matrix multiplication.
In this work we adapt techniques which are well-known from numerical analysis, for use in the area of arithmetic circuit complexity. Staying with this theme, we also improve the above mentioned poly(s,deg(p),m) bound for the circuit size of a root p of a polynomial f computed by an (unrestricted) arithmetic circuit of size s. Rather than applying [1, 2], we develop a discrete analogue of Newton's Method.

Preview: