Constant-Depth Arithmetic Circuits for Linear Algebra Problems

We design polynomial size, constant depth (namely, $\text{AC}_{\mathbb{F}}^{0})$ arithmetic formulae for the greatest common divisor (GCD) of two polynomials, as well as the related problems of the discriminant, resultant, Bézout coefficients, squarefree decomposition, and the inversion of structured matrices like Sylvester and Bézout matrices. Our GCD algorithm extends to any number of polynomials. Previously, the best known arithmetic formulae for these problems required super-polynomial size, regardless of depth. These results are based on new algorithmic techniques to compute various symmetric functions in the roots of polynomials, as well as manipulate the multiplicities of these roots, without having access to them. These techniques allow $\text{AC}_{\mathbb{F}}^{0}$ computation of a large class of linear and polynomial algebra problems, which include the above as special cases. We extend these techniques to problems whose inputs are multivariate polynomials, which are represented by constant-depth arithmetic circuits. Here too we solve problems such as computing the GCD and squarefree decomposition in $\text{AC}_{\mathbb{F}}^{0}$.

Authors

• Robert Andrews 0003
• Avi Wigderson

Keywords

• Computer science
• Symmetric matrices
• Circuits
• Linear algebra
• Polynomials
• Matrix decomposition
• Arithmetic
• Algebraic Problem
• Arithmetic Circuits
• Linear Algebra Problem
• Linear Problem
• Symmetric Function
• Constant Depth
• Roots Of Polynomial
• Greatest Common Divisor
• Computational Model
• Parallelization
• Complex Class
• Dynamic Programming
• Input Size
• Arithmetic Operations
• Polynomial Coefficients
• Formal Series
• Rational Function
• Parallel Algorithm
• Symbolic Processing
• Univariate Polynomial
• Sum Of Power
• Monic Polynomial
• Computer Algebra
• Multiset
• resultant
• symmetric polynomials