Algebraic Complexity Theory

The primary topic of this chapter is the design and analysis of algorithms that solve various problems concerning the symbolic manipulation of polynomials and power series. By symbolic computation we mean procedures for computing the coefficients of the resulting polynomials and power series from the coefficients of the inputs. Among these problems are the multiplication, inversion, division, and composition of polynomials and power series. We shall analyse both the total number of arithmetic operations and the number of nonscalar operations of the algorithms. (In the latter case, addition, subtraction, and scalar multiplication are free of charge.) This gives upper bounds for the total and nonscalar complexity of the problem under investigation. In later chapters we shall see that most of these algorithms are optimal or close to optimal.

The classical Euclidean algorithm typically amounts to order n ² nonscalar operations to construct the greatest common divisor G and the continued fraction expansion A₁/A₂ = Q₁ + 1/(Q₂ + 1/(Q3...)) of two univariate polynomials A₁, A₂ with n = deg A₁ ≥ deg A₂ ≥ 1. The first section discusses the Knuth-Schönhage algorithm [301, 451] that performs this task with only O(n log n) nonscalar operations. Strassen’s local analysis [500], presented in the subsequent section, yields the improved upper bound O(n(H + 1)), where H is the entropy of the probability vector n^-1(deg G, deg Q₁, deg Q₂, ...). On the other hand, Strassen proved a lower bound of the same order of magnitude for uniformly almost all inputs, see Chap. 10. Thus under the nonscalar cost measure, the Knuth-Schönhage algorithm is uniformly most powerful for computing continued fraction expansions together with greatest common divisors. (For the total number of arithmetic operations one obtains the upper bound O(n(H + 1) log n), if the groundfield supports FFTs.) In Sect. 3.3 we combine efficient greatest common divisor computations and Huffman coding to solve algorithmic problems around the Chinese remainder theorem, such as evaluation and interpolation.

The standard models for investigating issues in computational complexity in the discrete setting are the Turing machine and the random access machine. However, these models are not well-suited for a discussion of complexity questions in a general algebraic framework, where one assumes that arithmetic operations (over the reals, say) can be performed with infinite-precision at unit cost. For the search of lower bounds in such an algebraic framework, two computational models have proved to be particularly useful: the straight-line program, also called arithmetic circuit, and the computation tree.

In 1955 Motzkin discovered that Homer’s rule is not the fastest way to evaluate a polynomial when allowing for preconditioning of the coefficients. He found that the minimum number of multiplications needed to evaluate almost all real univariate polynomials of degree n ∉ (3, 5, 7, 9) equals ⌊n/2⌋ + 1 when starting from the variable, real constants and allowing arbitrarily many additions. In the cases n ∈ 3, 5, 7, 9 he claimed that the optimal number of multiplications equals ⌊n/2⌋ + 2. Motzkin also determined the multiplicative complexity of a “typical” univariate rational function. Unfortunately, only an abstract of his results without proofs is published [386]. Belaga [35] exhibited algorithms to evaluate any complex univariate polynomial of degree n with ⌊(n + 3)/2⌋ multiplications and n + 1 additions. Furthermore, he proved that n additions are necessary in general. Pan [404] obtained similar results for real polynomials.

In 1954 Ostrowski published his note [403] “On two problems in abstract algebra connected with Homer’s rule” which led to numerous investigations on the complexity of algebraic problems. In this paper he inquired about the optimality of the so-called Homer’s rule, a rule which was however already known to Newton (see [548, p. 222]). Ostrowski conjectured that there is no general evaluation procedure to evaluate a polynomial of degree n (in the polynomial ring) which requires less than n multiplications. In the cases n ≤ 4 he succeeded to prove his conjecture. It is remarkable that Ostrowski, guided by good mathematical intuition, already suggested the nonscalar counting. In 1966 Pan [405] invented the substitution method and proved Ostrowski’s conjecture (even when divisions are allowed). We remark that the optimality of Homer’s rule with respect to the number of additions and subtractions had already been settled before by Belaga [35] (compare Chap. 5). The substitution method was further developed by Winograd [552] and Strassen [495].

We will investigate two problems which will prove to be of particular importance for the rest of the book. The first question is how much divisions may help for the computation of a set of polynomials. The example of the univariate polynomial f = X ³¹ shows that divisions indeed can help. Strassen discovered in 1973 [498] a technique for transforming a straight-line program for a set of rational functions to a division free straight-line program for the “coefficients” of the Taylor series of these functions (Thm. (7.1)). In particular, he showed that divisions do not help for the computation of a set of quadratic forms. This result, which marks the beginning of the theory of bilinear complexity, will be exploited later in Chap. 14. Following Baur and Strassen [32] we will show in the second part of the present chapter how to transform a straight-line program for computing a multivariate rational function into one that computes this function and its gradient. Combined with other lower bound techniques, such as Strassen¹ s degree bound introduced in the next chapter, this so-called derivative inequality (7.7) allows us to derive sharp lower bounds for the nonscalar complexity of numerous computational problems. The results of this chapter will also be used extensively in Chap. 16 where we will show that several computational problems in linear algebra are about as hard as matrix multiplication.

Strassen’s degree bound [497], one of the fundamental tools for proving nonlinear lower bounds in algebraic complexity theory, states that the multiplicative complexity of a finite set of rational functions is bounded from below by the logarithm of the geometric degree of the graph of the associated rational map. Before discussing this bound in Sect. 8.3, we start with one of its field theoretic versions which can be derived in an elementary way and which will suffice to prove that most of the algorithms derived in Chap. 2 are essentially optimal. In Sect. 8.2 we proceed by defining the geometric degree and deduce a special version of the Bézout inequality. Our intention has been to give a detailed account for non-specialists in algebraic geometry by keeping the prerequisites at a minimum. Applications not easily implied by the field theoretic version of the degree bound will be discussed in Sect. 8.4, before developing methods for estimating the degree in Sect. 8.5. In the last section of this chapter we show how the degree bound can be employed to derive lower bounds for the complexity of rational functions over finite fields.

We discuss various techniques for exhibiting specific polynomials of provably high complexity which originate in a landmark paper by Strassen [499] written in 1974. In the first section we restrict ourselves to computations in the polynomial algebra (no divisions) and derive a lower bound in an elementary way. In the next section we study computations in the ring of formal power series, define complexity classes, and prove a representation theorem for them. Based on this, a general lower bound theorem on the multiplicative complexity follows. As a result we exhibit in Sect. 9.3 various specific polynomials with algebraic coefficients which are hard to compute. Some tools from algebraic number theory are required for computing the degrees of the occurring field extensions. In Sect. 9.4 we proceed with rather technical lower bound proofs for polynomials with rapidly growing integer coefficients. Finally, in Sect. 9.5, we extend most of what we have done so far to other complexity measures, in particular to additive complexity.

We present a degree bound for computation trees with equality testing due to Strassen [504]. More specifically, we prove a general lower bound on the multiplicative complexity of collections for subsets of k ⁿ, where k is algebraically closed, resp. an arbitrary infinite field. Two applications to the problem of computing the Euclidean representation of two polynomials are discussed. First, we give Strassen’s optimality proof of the Knuth-Schönhage algorithm which has been presented in Sect. 3.1. Then we discuss Schuster’s lower bound [467] for the problem of computing just the degree pattern of the Euclidean representation. The latter relies on an analysis of the Euclidean representation by means of the subresultant theorem.

In the first section we derive the Milnor-Thom bound [366, 516] which gives a quantitative estimate on the number of connected components of a semi-algebraic set in R ⁿ described by polynomial equalities and inequalities. This estimate depends on the number of variables n, the number of inequalities and the maximum of the degrees of the occurring polynomials. Its proof is based on Bézout’s inequality and on the Morse-Sard theorem. In the next section we investigate computation trees over R which solve the membership problem for a semi-algebraic subset W of R ⁿ . Ben-Or’s lower bound [37] on the multiplicative branching complexity of such membership problems in terms of the number of connected components of W is deduced from the Milnor-Thom bound. Then we discuss applications to the real knapsack problem and to several problems of computational geometry (such as the computation of the convex hull of a finite set of points in the plane).

We prove Khovanskii’s theorem [300] which gives an upper bound on the number of non-degenerate real solutions of a system of n polynomial equations in n variables which depends only on n and the number of distinct terms occurring in the polynomials. This result is in fact a consequence of a more general result dealing with certain systems of transcendental equations. A variant of Rolle’s theorem and Bézout’s inequality enter in the proof. As a consequence we deduce Grigoriev’s and Risler’s lower bound [209, 438] on the additive complexity of a univariate real polynomial in terms of the number of its real roots.

In this chapter we study the linear complexity of a matrix A, which is the minimum number of additions, subtractions, and scalar multiplications to compute the product AX, where X is a generic input vector. In Sect. 13.2 we first follow Winograd to determine the exact linear complexity of a generic matrix, and then proceed with deriving reasonable upper complexity bounds for some classes of structured matrices. There, we also prove Morgenstern’s theorem [382], which yields a lower bound of order n log n for the number of additions and multiplications by scalars of bounded absolute value to compute the discrete Fourier transform of length n over the complex field. A reformulation of the linear computational model in terms of graph theory is presented in Sect. 13.3. As a first application of this approach, we give a short proof of Tellegen’s theorem, which (in a special case) states that an invertible matrix and its transpose have the same linear complexity. Sect. 13.4 discusses the linear complexity of superregular and totally regular matrices in terms of graph theory. We prove Shoup and Smolensky’s theorem [477] that sometimes gives nonlinear lower bounds for superregular matrices, as well as Valiant’s theorem [525] that yields a lower bound for the linear complexity of totally regular n x n-matrices as a linear function of the minimal number of edges in an n-superconcentrator. We also prove Pinsker and Valiant’s theorem [418, 525] stating that n-superconcentrators with O(n) edges exist. The last section is concerned with discrete Fourier transforms for arbitrary finite groups. We present results of Baum, Beth, and Clausen that generalize the classical Cooley-Tukey FFT to wider classes of finite groups. In particular, Baum’s theorem [24] shows that every supersolvable group of order n has a DFT of linear complexity O (n log n).

This chapter introduces the framework of the theory of bilinear complexity and is the basis for the study of Chap. 15–20. The language and concepts introduced here will, e. g., allow for a concise treatment of the fast matrix multiplication algorithms which we will discuss in the next chapter. We shall first turn our attention to the computation of a set of quadratic polynomials. According to Cor. (7.5) divisions do not help for the computation of such polynomials (at least when the field is infinite). The proof of that theorem in the case of quadratic polynomials implies a different characterization of the multiplicative complexity of these polynomials. We then associate to a set of quadratic polynomials quadratic maps between finite dimensional k-spaces and study the maps rather than the polynomials; this gives rise to the notion of computation for such maps. Specializing the quadratic maps further to bilinear maps and modifying the computations will lead to the important notion of rank or bilinear complexity of a bilinear map.

This chapter is devoted to the discussion of fast matrix multiplication algorithms. We define the exponent ω of matrix multiplication, a quantity measuring the asymptotic complexity of this problem. Strassen’s original algorithm gives ω ≤ 2.81 (see Chap. 1). The robustness of the exponent with respect to various cost functions, and its invariance with respect to field extensions is shown. (Further motivation for the investigation of ω is given in Chap. 16.) We introduce the concept of border rank of tensors due to Bini, Capovani, Lotti, and Romani [49], and deduce Schönhage’s asymptotic sum inequality [460], which has become one of the main tools for gaining upper estimates of the exponent. Then we present the laser method [508] and its generalization by Coppersmith and Winograd [134], and prove their estimate ω < 2.39. Finally, an extension of the asymptotic sum inequality to the multiplication of partially filled matrices is considered. As an application, we describe Coppersmith’s construction of astonishingly rapid algorithms for the multiplication of rectangular matrices.

Fast matrix multiplication algorithms play a fundamental role in the design of algorithmic solutions to several problems in computational linear algebra. In this chapter we will show that the complexities of problems such as matrix inversion, computation of the determinant, LUP-decomposition, computing the characteristic polynomial, or orthogonal basis transform, are dominated asymptotically by the complexity of matrix multiplication. Though we shall restrict ourselves to the muliplicative complexity only, the algorithms we exhibit show that these upper bounds also hold for the total complexity. On the other hand, matrix multiplication can be reduced to special instances of these problems, which shows that — from a computational point of view — all these problems are asymptotically equivalent. To put this sort of reasoning into a formal framework, we shall begin by introducing the notion of an exponent for a certain type of problems. We then show, by exhibiting specific algorithms, that all the above problems (and some others) have the same exponent as matrix multiplication. In the last section of this chapter we show how fast matrix multiplication algorithms can be used to compute the transitive closure of a graph.

We discuss methods for proving lower bounds for the multiplicative complexity of bilinear maps; as usual, we shall focus on multiplication maps of (associative) algebras and on matrix multiplication. The first section discusses various lower bounds, the highlight being Lafon and Winograd’s theorem [311] which gives a general lower bound for the multiplicative complexity of matrix multiplication. The methods of Sect. 17.1 will be unified in the second section where we prove Alder and Strassen’s theorem [6], a lower bound for the multiplicative complexity of associative algebras in terms of their dimension and their number of maximal two-sided ideals. The question naturally arises for which algebras this lower bound is sharp. In Sect. 17.3 we investigate division algebras and characterize all those which have minimal multiplicative complexity. Finally, in Sect. 17.4 we give a complete characterization, due to de Groote and Heintz [220], of all commutative algebras which have minimal rank.

Although the bilinear complexity of a bilinear map ϕ over a finite field may not be the minimum number of multiplications and divisions necessary for computing ϕ, the study of such maps gives some insight into the problem of computing a bilinear map over the ring of integers of a global field, such as the ring Z of integers: any bilinear computation defined over Z (that is, whose coefficients belong to Z) gives via reduction of constants modulo a prime p a bilinear computation over the finite field F _p . In this chapter we introduce a relationship observed by Brockett and Dobkin [80] between the rank of bilinear maps over a finite field and the theory of linear error-correcting codes. More precisely, we associate to any bilinear computation of length r of a bilinear map over a finite field a linear code of block length r; the dimension and minimum distance of this code depend only on the bilinear map and not on the specific computation. The question about lower bounds for r can then be stated as the question about the minimum block length of a linear code of given dimension and minimum distance. This question has been extensively studied by coding theorists; we use their results to obtain linear lower bounds for different problems, such as polynomial and matrix multiplication. In particular, following Bshouty [85, 86] we show that the rank of n x n-matrix multiplication over F₂ is 5/2n² — o(n²). In the last section of this chapter we discuss an interpolation algorithm on algebraic curves due to Chudnovsky and Chudnovsky [110]. Combined with a result on algebraic curves with many rational points over finite fields, this algorithm yields a linear upper bound for R(F _q ⁿ/F _q )for fixed q.

It is easy to compute the rank of a matrix: one transforms it to echelon form for example via Gaussian elimination; the rank can then be read off this form. In the first part of this chapter we show that similar results also hold for a pair of matrices. Following the Weierstraß-Kronecker theory, we define certain invariants for pairs of matrices and give a formula, due to Grigoriev [207, 208] and Ja’Ja’ [265, 266] for the rank of such a pair in terms of these invariants. For triples of matrices, resp. 3-slice tensors, no such formula is known. In the second part of this chapter we present some results due to Strassen [505]. We prove a lower bound for the border rank of 3-slice tensors. Moreover, we show that for the format (n, n, 3), n ≥ 3 odd, the complement of the set of tensors of maximal border rank is a hypersurface and we explicitly determine its equation. For this we will also rely on a result which will be obtained in Chap. 20.

The typical rank R(f) of a format f is the rank of Zariski almost all tensors of that format. Following Strassen [505] and Lickteig [331] we determine the asymptotic growth of the function R and determine its value for some special formats. In particular, we consider the formats of 3-slice tensors and prove a result needed in Chap. 19. The problem amounts to determining the dimension of higher secant varieties to Segre varieties. We achieve this by computing the dimension of the tangent space to these varieties, for which some machinery is developed. In the appendix we give a topological characterization of the border rank due to Alder [5], on which all our investigations in this chapter are based.

One of the most important topics in structural complexity theory is the question, whether nondeterministic polynomial time for Turing machine computations is more powerful than deterministic polynomial time. Some insight into Cook’s hypothesis “P ≠ NP” is provided by polynomial time reductions which allow to single out the NP-complete problems as the hardest problems in NP, see Cook [124], Karp [297], and Levin [328]. This chapter discusses Valiant’s nonuniform algebraic analogue of NP-completeness [526, 529] which grew out of his studies of enumeration problems culminating in the theory of #P-completeness. The first section introduces Valiant’s algebraic complexity classes VP and VNP, as well as p-projections as an algebraic analogue of polynomial time reductions. The elements of these classes are certain families of multivariate polynomials over some fixed field k. Valiant’s hypothesis “VP ≠ VNP” gains interest by his theorem stating that the family PER = (PER _n) of generic permanents is VNP-complete over any field of characteristic different from 2. The proof of this fundamental result, which is the main goal of this chapter, is based on an alternative characterization of VNP in terms of the expression or formula size of polynomials, see Sect. 21.2. In the third section it is shown that every polynomial of expression size u is a projection of PER_2u+2. Sect. 21.4 presents a simplified proof of Valiant’s theorem based on a generalized Laplace expansion theorem. In the last section we prove Brent’s theorem [72] which describes the close connection between depth and expression size, as well as results of Hyafil [260] and Valiant, Skyum, Berkowitz, and Rackoff [530] estimating the depth of a polynomial in terms of its degree and complexity. On the basis of these results the extended Valiant hypothesis can be formulated in purely algebraic terms: for any fixed positive constant c there is no possibility of writing all generic permanents as PER _n = DET _m(n) (A), where A is an m(n) x m(n) matrix over k ⋃ X_μυ|μ,υ ϵ n and m(n) = 2^O(log^cn).