Lower Bounds for Matrix Product Amir Shpilka Institute of Computer Science Hebrew University 2 Jerusalem, Israel 0 0 amirs@cs.huji.ac.il 2 n February 1, 2008 a J 2 Abstract ] We provelowerbounds onthe numberofproductgatesinbilinearandquadraticcircuits that C compute the productoftwo n×n matricesoverfinite fields. In particularwe obtainthe following C results: . s 1. We show that the number of product gates in any bilinear (or quadratic) circuit that com- c [ putes the product of two n×n matrices over GF(2) is at least 3n2−o(n2). 1 2. Weshowthatthenumberofproductgatesinanybilinearcircuitthatcomputestheproduct v of two n×n matrices over GF(p) is at least (2.5+ 1.5 )n2−o(n2). p3−1 1 0 These results improve the former results of [3, 1] who proved lower bounds of 2.5n2−o(n2). 0 1 0 1 Introduction 2 0 / s The problem of computing the product of two matrices is one of the most studied computational c problems: We are given two n× n matrices x = (x ), y = (y ), and we wish to compute their : i,j i,j v product, i.e. there are n2 outputs where the (i,j)’th output is i X n r a (x·y)i,j = xi,k ·yk,j . k=1 X In 69’ Strassen surprised the world by showing an upper bound of O(nlog27) [12]. This bound was later improved and the best upper bound today is O(n2.376) [5] (see also [7] for a survey). The best lower bound is a lower bounds of 2.5n2−o(n2), on the number of products needed to compute the function [3, 1]. Thus the following problem is still open: Can matrix product be computed by a circuit of size O(n2) ? Thestandardcomputationalmodelforcomputingpolynomialsisthemodelofarithmeticcircuits, i.e. circuits over the base {+, ·} over some field F. This is indeed the most general model, but for matrix product two other models are usually considered, quadratic circuits and bilinear circuits. In the quadratic model we require that product gates are applied only on two linear functions. In the bilinear model we also require that product gates are applied only on two linear functions, but in addition we require that the first linear function is linear in the variables of x and that the second linear function is linear in the variables of y. These models are more restricted than the general model of arithmetic circuits. However it is interesting to note that over infinite fields we can always assume w.l.o.g. that any circuit for matrix product is a quadratic circuit [13]. In addition we note that the best circuits that we have today for matrix product are bilinear circuits. In this paper we prove that any quadratic circuit that computes matrix product over the field GF(2) has at least 3n2−o(n2) product gates, and that any bilinear circuit for matrix product over the field GF(p) must have at least (2.5+ 1.5 )n2−o(n2) product gates. p3−1 From now on we will use the notation MP to denote the problem of computing the product of n two n×n matrices. 1.1 Known Lower Bounds In contrast to the major advances in proving upper bound, the attempts to prove lower bounds on the size of bilinear circuits that compute MPn were less successful. Denote by q∗(MPn) and bl∗(MPn) the number of product gates in a smallest quadratic circuit for MPn, and in a smallest bilinear circuit for MP respectively. We also denote by bl (MP ) the total number of gates in a n tot n smallest bilinear circuit for MPn. In 78’ Brocket and Dobkin proved that bl∗(MPn) ≥ 2n2−1 over any field [10]. This lower bound was later generalized by Lafon and Winograd to a lower bound on q∗(MPn) over any field [8]. In 89’ Bshouty showed that over GF(2), q∗(MPn) ≥ 2.5n2 −O(nlogn) [3]. Recently Bläser proved a lower bound of 2n2+n−3 on q∗(MPn) over any field [2]. In [1] Bläser proved that bl∗(MPn)≥ 2.5n2 −3n over any field. In [9] it is shown that any bounded depth circuit for MP , over any field, has a super linear (in n n2) size. Notice however, that the best known circuits for MP have depth Ω(logn). n 1.2 Bilinear Rank An important notion that is highly related to the problem of computing matrix product in bilinear circuits is the notion of bilinear rank. A bilinear form in two sets of variables x,y is a polynomial in the variables of x and the variables of y, which is linear in the variables of x and linear in the variables of y. Clearly each output of MP is a bilinear form in x = {x }, y = {y }. The bilinear rank of a set of bilinear forms n i,j i,j { b (x,y), ..., b (x,y) } is the smallest number of rank 1 bilinear forms that span b , ..., b , 1 m 1 m where a rank 1 bilinear form is a product of a linear form in the x variables and a linear form in the y variables. We denote by R (b , ···, b ) the bilinear rank of { b , ..., b } over the field F. For F 1 m 1 m further background see [4, 7]. We denote by R (MP ) the bilinear rank over F of the n2 outputs of matrix product, i.e. it is F n the bilinear rank of the set { n x ·y } over F. k=1 i,k k,j i,j The following inequalitiesPare obvious (over any field). • q∗(MPn) ≤ bl∗(MPn)≤ 2q∗(MPn). • RF(MPn)= bl∗(MPn). • The following inequality is less obvious, but also not so hard to see. bl∗(MPn) ≤bltot(MPn) ≤ poly(logn)·bl∗(MPn). 2 I.e. up to polylogarithmic factors, the number of product gates in a smallest bilinear circuit for MP , over any field F, is equal to the total number of gates in the circuit. n 1.3 Results and Methods We prove that anyquadratic circuit that computes MP over thefield GF(2) hasat least 3n2−o(n2) n product gates (i.e. q∗(MPn) ≥ 3n2 −o(n2) over GF(2)). We also prove that over the field GF(p) everybilinearcircuitforMPn musthaveatleast(2.5+p13.−51)n2−o(n2)productgates(i.e. bl∗(MPn)≥ (2.5+ 1.5 )n2−o(n2) over GF(p)). Both of these results actually hold for the bilinear rank as well. p3−1 The proof of the lower bound over GF(2) is based on techniques from the theory of linear codes. However, we cannot use known results from coding theory in a straightforward way, since we are not dealing with codes in which every two words are distant, but rather with codes on matrices in which the distance between two code words, of two matrices, is proportional to the rank of the difference of the matrices. The reduction from circuits to codes and the proof of the bound are given in section 4. The proof of the second bound is based on a lemma proved by Bläser in [1]. We prove that in the case of finite fields we can use the lemma with better parameters than those used by Bläser. This result is proved in section 5. 1.4 Organization of the paper In section 2 we present the models of bilinear circuits and quadratic circuits. In section 3 we present some algebraic and combinatorial tools that we need for the proofs of our lower bounds. In section 4 we introduce the notion of linear codes of matrices, and prove our lower bound on bilinear and quadratic circuits that compute MP over GF(2). In section 5 we prove our lower n bound on bilinear circuits that compute MP over GF(p). n 2 Arithmetic Models Inthis section we presentthe modelsof quadratic circuits and bilinear circuits. Thesearethemodels for which we prove our lower bounds. We first give the definition of a general arithmetic circuit. An arithmetic circuit over a field F is a directed acyclic graph as follows. Nodes of in-degree 0 are called inputs and are labeled with input variables. Nodes of out-degree 0 are called outputs. Each edge is labeled with a constant from the field and each node other than an input is labeled with one of the following operations { + , · }, in the first case the node is a plus gate and in the second case a product gate. The computation is done in the following way. An input just computes the value of the variable that labels it. Then, if v , ..., v are the vertices that fan into v then we multiply the 1 k result of each v with the value of the edge that connects it to v. If v is a plus gate we sum all the i results, otherwise v is a product gate and we multiply all the results. Obviously the value computed by each node in the circuit is a polynomial over F in the input variables. We are interested in the problem of computing the product of two n×n matrices, MP . The n input consists of two n×n matrices x, y. The output is the matrix x·y, i.e., there are n2 outputs, 3 and the (i,j)’th output is: n (x·y) = x ·y . i,j i,k k,j k=1 X Each output (x·y) is hence a bilinear form in x and y. i,j Since each output of MP is a bilinear form, it is natural to consider bilinear arithmetic circuits n for it. A bilinear arithmetic circuit is an arithmetic circuit with the additional restriction that product gates are applied only on two linear functions, one function is linear in the variables of x and the other function is linear in the variables of y. Thus, bilinear circuits have the following structure. First, there are many plus gates computing linear forms in x and linear forms in y. Then there is one level of productgates that compute bilinear forms, and finally there are many plus gates that eventually compute the outputs. We will be interested in bounding from below the number of products in any bilinear circuit for MP . This model is more restricted than the general model of n arithmetic circuits but we note that all the known upper bounds (over any field) for MP are by n bilinear circuits. Another model that we will consider is the model of quadratic circuits. A quadratic circuit is an arithmetic circuit with the additional restriction that product gates are applied only on two linear functions. Notice that the only difference between quadratic circuits and bilinear circuits is that in the quadratic model the product gates compute quadratic forms in x, y, whereas in the bilinear model the product gates compute bilinear forms in x, y. This model is more general than the model of bilinear circuits, but it is still more restricted than the general model. However it is interesting to note that over infinite fields we can assume w.l.o.g. that any arithmetic circuit for MP is a n quadratic circuit [13]. 3 Algebraic and Combinatorial tools In this section we present some algebraic and combinatorial tools that we will use. The following lemma is an extremely weak variant of the famous Schwartz-Zippel lemma which shows that every non zero polynomial (non zero as a formal expression) over a large enough field has a non zero assignment in the field (see [11, 15]). Lemma 1 Let P be a polynomial of degree d in x , ..., x over some field F, such that d < |F|, 1 n and such that at least one of the coefficients of P is not zero. Then we can find an assignment, ρ∈ Fn, to the x ’s, such that P(ρ ,...,ρ )6= 0. i 1 n We say that two polynomials p,q in n variables are equivalent over a field F, if p(x ,...,x ) = 1 n q(x ,...,x ) for any x , ..., x ∈ F. We denote p ≡ q if p and q are equivalent over F (we omit F 1 n 1 n from the notation as the field that we deal with will be clear from the context). Lemma 2 Let P be a polynomial of degree d in the variables x , ..., x over a field F. If P 6≡ 0 1 n then we can find an assignment, ρ ∈ Fn, to the x ’s such that at most d of the ρ ’s get a nonzero i i value, and such that P(ρ ,...,ρ ) 6= 0. 1 n Proof: P is equal (as a function) to a polynomial P¯ in which the degree of each variable is at most |F|−1. We call P¯ the reduction of P. Considersome monomial M in P¯ whosecoefficient is not zero. We assign all the variables that do not appear in M to zero. The resulting polynomial (after the 4 assignment), isapolynomialinthevariables ofM, whichisnotthezeropolynomialas itisareduced polynomial which has a monomial with a non zero coefficient (M of course). Therefore according to lemma 1 there is some assignment to the variables of M, that gives this polynomial a nonzero value. Therefor we have found an assignment which gives nonzero values only to the variables of M (and there are at most d such variables) under which P 6= 0. ♣ The following useful lemma, which is a straightforward implication of the previous lemma, is the key lemma in most of our proofs. The lemma deals with linear forms in n2 variables. From now on we shall think about such linear forms as linear forms in the entries of n×n matrices. Lemma 3 Let µ1, ..., µn2 be n2 linearly independent linear forms in n2 variables over some field F. Let P be a polynomial of degree d in kn2 variables over F, i.e. we can view P as a polynomial P(x ,...,x ) in the entries of k matrices, x ,...,x , of size n×n each. Assume that P 6≡ 0. Then we 1 k 1 k can find k matrices a , ..., a ∈ M (F) such that P(a ,...,a ) 6= 0 and such that there exist n2−d 1 k n 1 k linear forms among µ1,...,µn2’s that vanish on all the ai’s. Proof: The idea of the proof is the following. Let b1, ..., bn2 be the dual basis of µ1,...,µn2, i.e. it is a basis of M (F) satisfying ∀i,j µ (b ) = δ . We wish to find k matrices, a ,...,a , such that n i j i,j 1 k P(a ,...,a ) 6= 0, and such that there exist b ,...,b that span all of them. If we manage to find 1 k i1 id such matrices, then since the b ’s are the dual basis to the µ ’s we will get that n2 −d of the µ ’s i i i vanish on a ,...,a . The way to find such matrices that are contained in the span of a small subset 1 k of the b ’s, is based on lemma 2. i So let b1, ..., bn2 be the dual basis to µ1, ..., µn2, i.e. ∀i,j µi(bj) = δi,j. We now change the variables of P. Let α j = 1...k, i = 1...n2, be a set of kn2 variables. Denote x = n2 α b . i,j j i=1 i,j i Thus P(x ,...,x ) can be viewed as a polynomial of degree d in the kn2 variables α . Therefore 1 k i,jP P 6≡ 0 as a polynomial in the α ’s. Hence, according to lemma 2 there exists an assignment, ρ, i,j to the α ’s such that at most d of them get a nonzero value. Define a = n2 ρ b . Clearly i,j j i=1 i,j i P(a ,...,a ) 6= 0. Since at most d of the ρ ’s got non zero values, we see that there are at most 1 k i,j P d b ’s such that all the a ’s are linear combinations of them. Since the b ’s are the dual basis to i j i µ1, ..., µn2 we get that there are at least n2 −d of the µi’s that vanish on all the aj’s. Therefore a , ..., a satisfy the requirements of the lemma. ♣ 1 k Thenextlemmawillenableustotranslatepropertiesofmatrices overlargefieldsofcharacteristic p to properties of matrices (of higher dimension) over GF(p). Lemma 4 There exist an embedding, φ : GF(pn) ֒→ M (GF(p)). That is there exist a mapping n φ: GF(pn)7→ M (GF(p)) such that n • φ is a one to one linear transformation. • φ(1) = I, where I is the n×n identity matrix. • φ is multiplicative, i.e. ∀x,y ∈GF(pn) we have that φ(xy) =φ(x)·φ(y). This embedding also induces an embedding M (GF(pn)) ֒→ M (GF(p)). k nk This lemma is a standard tool in algebra, but for completeness we give the proof. 5 Proof: GF(pn) is an n dimensional vector space over GF(p). Each element x ∈ GF(pn) can be viewed as a linear transformation x: GF(pn) 7→ GF(pn) in the following way: ∀y ∈ GF(pn) x(y) = x·y . Clearly this is a linear transformation of GF(pn) into itself, as a vector space over GF(p). Therefore, by picking a basis to GF(pn) we can represent the linear transformation corresponding to each x ∈ GF(pn) by a matrix a ∈ M (GF(p)). Thus, we have defined a mapping φ: GF(pn) 7→ M (GF(p)) x n n such that φ(x) = a , and it is easy to verify that this mapping is an embedding of GF(pn) into x M (GF(p)). The way to generalize it to an embedding of M (GF(pn)) into M (GF(p)) is the n k nk following. Let a= (a )∈ M (GF(pn)) be some matrix. Every entree of a of a, is some element of i,j k i,j GF(pn). Wecan nowreplace a withthematrixφ(a ). Thustheresultingmatrix willbeakn×kn i,j i,j matrix whose entries are in GF(p). Again it is easy to verify that this is indeed an embedding of M (GF(pn)) into M (GF(p)). ♣ k nk In addition to the algebraic lemmas we also need the following combinatorial tools. Definition 1 Let F be a field, and let v, u be two vectors in Fm. We denote by weight(v) the number of nonzero coordinates of v. Let dH(v,u) = weight(v − u), i.e. dH(v,u) is the number of coordinates on which u and v differ. dH(v,u) is also known as the Hamming distance of u and v. We also denote by agree(u,v) the number of coordinates on which u and v are equal, i.e. agree(u,v) = m−dH(v,u). Thenext lemma shows that if a vector space contains a set of vectors such that every pair/triplet of them don’t agree on many coordinates (i.e. their Hamming distance is large) then it is of large dimension. There are numerous similar lemmas in coding theory, and in particular the first part of our lemma is the famous Plotkin bound (see [14]). Lemma 5 1. In every set of k vectors in GF(p)t, such that p < k, there are two vectors that agree on at least (t − t) coordinates. p k 2. In every set of k vectors in GF(p)t, such that 2p < k, there are three vectors that agree on at least ( t − 3t) coordinates. p2 pk Proof: We begin by proving the first claim. Let v ,...,v be k vectors in GF(p)t. We are going to 1 k estimate agree(v ,v ) in two different ways. On the one hand this sum is at most k times the i

Lower Bounds for Matrix Product

Similar Lower Bounds for Matrix Product