From:	IN%"xhuang@email.gc.cuny.edu" 20-DEC-1997 12:48:28.23To:	IN%"vpan@lcvax.lehman.cuny.edu"  "Victor Pan"CC:	Subj:	Paper Rectangular Matrix Multiplication and Employment AgencyReturn-path: <xhuang@email.gc.cuny.edu>Received: from vice1.lehman.cuny.edu by lcvax.lehman.cuny.edu (PMDF #12809) id <01IREBHCOZ0W000CZL@lcvax.lehman.cuny.edu>; Sat, 20 Dec 1997 12:48 ESTReceived: from broadway.gc.cuny.edu by vice1.lehman.cuny.edu (5.51/SMI-3.0DEV3) id AA05035; Fri, 19 Dec 97 09:25:17 ESTReceived: from localhost (xhuang@localhost) by broadway.gc.cuny.edu (8.8.5/ankDU-96) with SMTP id MAA18305 for <vpan@lcvax.lehman.cuny.edu>; Sat, 20 Dec 1997 12:45:18 -0500 (EST)Date: Sat, 20 Dec 1997 12:45:18 -0500 (EST)From: xhuang@email.gc.cuny.eduSubject: Paper Rectangular Matrix Multiplication and Employment AgencyTo: Victor Pan <vpan@lcvax.lehman.cuny.edu>Message-id: <Pine.OSF.3.93.971220123757.18138A-100000@broadway.gc.cuny.edu>Content-type: TEXT/PLAIN; charset=US-ASCIIX-Sender: xhuang@broadway.gc.cuny.eduMime-Version: 1.0From: Xiaohan HuangTo: Prof. PanEmployment Agency Address:   Communications Excellence, Inc.   540 Marl Road, Colts Neck, NJ 07722   Tel#: (908) 741-6703, or (732) 741-6703    Fax#: (908) 530_0883, or (732) 530-0883Paper:------------------------------------------------------------------------\documentstyle[11pt]{article}\topmargin -0.4in\oddsidemargin 0.05in\evensidemargin 0.05in\textheight 9.6in\textwidth 6.7in\headheight 0in\headsep 0in\footskip 0.5in\footheight 0in\renewcommand{\baselinestretch}{1.55}\newtheorem{theorem}{\sc \bf Theorem}[section]\newtheorem{prop}{\sc \bf Proposition}[section]\newtheorem{defs}{\sc \bf Definition}[section]\newtheorem{lemma}{\sc \bf Lemma}[section]\newtheorem{remark}{\sc \bf Remark}[section]\newtheorem{coro}{\sc \bf Corollary}[section]\newtheorem{fact}{\sc \bf Fact}[section]\newtheorem{summary}{\sc \bf Summary}[section]\title{\bf Fast Rectangular Matrix \\ Multiplications and Applications \thanks{Supported by NSF Grant CCR 9625344and PSC CUNY Awards 667340 and 668365.}}\author{Xiaohan ${\rm Huang^{[1]},~~~~~~Victor~Y.~Pan^{[2]}}$\and\\$^{[1]~~}$Ph.D. Program in Mathematics,\\%$^{[2]~~}$Ph.D. Program in Computer Science,\\Graduate School and University Center\\City University of New York\\33 West 42nd Street, New York, NY 10036, USA\\Internet: xhuang@email.gc.cuny.edu\and\\$^{[2]~~}$Department of Mathematics and Computer Science \\Lehman College, City University of New York\\Bronx, NY 10468, USA\\Internet: vpan@lcvax.lehman.cuny.edu}\begin{document}\maketitle\newpage\begin{abstract}~~~~~In sections 1-8, we study a symptotically fast algorithms for rectangular matrix multiplication.We begin with new algorithms formultiplication of an $n\times n$ matrixby an $n\times n^2$ matrix in arithmetic time$O(n^{\omega})$, $\omega=3.333953\ldots$, which is less by 0.041 than the previous record $3.375477\ldots$.Then, we present fast multiplication algorithmsfor matrix pairs of arbitrary dimensions, estimate the asymptoticrunning time as a function of the dimensions, and optimize the exponents of the complexity estimates.For a large class of input matrix pairs, we improve the knownexponents.In sections 9-11, we show three applications of our results of sections 1-8:a) we decrease from 2.851 to 2.837 the known exponent of the workbounds for fast deterministic (NC) parallel evaluation of the determinant, the characteristic polynomial, the solution to a nonsingular linear system of $n$ equations, and the inverseof an $n\times n$ matrix,b) we asymptotically accelerate the known sequential algorithmsfor the univariate polynomial composition mod $x^n$, yielding the complexitybound $O(n^{1.667})$ versus the old record of $O(n^{1.688})$, andfor the univariate polynomial factorization over a finite field, and c) we improve slightly the known complexity estimates for computingbasic solutions to the linear programming problem with $m$ constraintsand $n$ variables.\end{abstract}\noindent{\bf Key words:} rectangular matrix multiplication, asymptoticarithmetic complexity, bilinear algorithms, parallel complexity,polynomial composition, polynomial factorization over finite fields, linear programming.\section{Introduction}\subsection{Our subject and results}Acceleration of matrix multiplication is a major subject of theoryand practice of computing (see [Pan], [Pan,a], [CW90], [GL89/96]). In  some sense this is a basic problem in the study of computationalcomplexity, because a very large class of computationswith matrices, graphs, regular and Boolean expressions can be reducedto matrix multiplication, so that the estimates for the asymptoticcomplexity of all these computations is represented by the same exponentas matrix multiplication [Pan], [BP94]. In this large class thereis a subclass of important computational problems whose recordasymptotic complexity is reduced to that of rectangular matrixmultiplication. This motivates our study in the presentpaper, that is,we improve the known upper estimates forthe asymptotic complexity of multiplying rectangular matrices of large sizes and demonstrate further impact of our results.In particular, this impact includes the improvement of the known deterministic asymptotic upper bounds on the work-complexity of some of the most fundamental parallel (NC) matrix computations, such as the evaluation of the determinant, the inverse,and the charateristic polynomial of an $n\times n$ matrix  as well as solvinga nonsingular system of $n$ linear equations. Furthermore, we decrease the known asymptotic complexity estimates forpolynomial composition, factorizationof univariate polynomials over finite fields, and computing a basis solution to a linear programming problem. Our progress relies on extending the powerful techniques of [CW90]for fast multiplication of square matrices to rectangular matrixmultiplication and on the reduction of other listed computationalproblems ( of parallel matrix computation, polynomial compositionand factorization and linear programming ) to rectangular matrixmultiplication.Matrix computations on present day computers are known to be highly efficient [GL96], and the reduction to them is a practicalmeans of improving the known solution of other computational problems.This gives some practical motivation to our study of the reductionsof polynomial computations and linear programming to rectangularmatrix multiplication. Otherwise our motivation is the theoreticalimprovement of the known asymptotic estimates for arithmetic complexity.As in [CW90], as well as in [Sc81], [CW82], [Co82], [St86], [St87],[St88], [GP89], [Co97], [BM98], we rely on the improvement of theknown arithmetic complexity for operations with matrices of verylarge sizes, which are far beyond the sizes encountered in practice, and our improvement is expressed in terms of decreasing the exponents $\beta$ of the complexity bounds of the form $O(N^{\beta})$,$N\rightarrow \infty$, $N$ representing the size of the input.In particular, the known complexity estimate for multiplicationof an $n\times n$ matrix by an $n\times n^2$ matrix was$O(n^{3.375477\ldots})$ ( based on the straightforward applicationof [CW90] ), and we decreased this exponent by roughly $0.041$, to yield$O(n^{3.333953\ldots})$. For the cited problems of parallel $NC$ computations for $n\times n$ input matrices, the known estimatefor their work-complexity was $O(n^{2.851})$ [GP89], and we yielded$O(n^{2.837})$. For polynomial composition modulo $x^n$, we decreasedthe known sequential complexity exponent from $O(n^{1.688})$( obtained by combining [BK78] and [CW90] ) to $O(n^{1.667})$with the respective decrease of the asymptotic complexity of the known fast algorithms [GS92], [KS95] for factorization of univariatepolynomials in finite fields; furthermore, we showed some additional ways to the improvement of the factorization by its reduction to rectangular matrix multiplication ( see the details in section 10 ).Finally, application of our fast algorithms for rectangular matrixmultiplication immediately enabled us to improve the estimate$O(m^{1.594}n)$ of [BM98], to yield $O(m^{1.575}n)$, for computingbasic solutions to the linear programming problem with $m$constraints and $n$ variables.\subsection{Some related work}Asymptotic arithmeticcomplexity of square $n\times n$ matrix multiplication has beenstudied very extensively and intensively for many years (see e.g. [St69], [Sc81], [CW82],[Pan], [Pan,a], [St86], [St87], [St88], [CW90]).So far, this study has culminated in the record upper bound$O(n^{\omega})$, $\omega<2.376$ (in terms of the number of arithmetic operations involved) [CW90], which marks long but still uncompletedway from the classical $\omega=3$ (before 1969) down towards the best lower bound 2.Less attention has been paid so far to the complexity of rectangularmatrix multiplication, where the most important works are [BD76],[Co82] and [Co97]. The papers [BK78], [GP89], [GS92], [KS95], [BM98]also studied the applications of rectangular matrix multiplicationto the computational problems that we consider in our present paper.\subsection{Organization of our paper}We organize our presentation as follows.In section 2, we recall some basic concepts, definitionsand results on matrix multiplicatins. In particular, we introducethe notation $<m,n,p>$ for the problem of $m\times n$ by $n\times p$matrix multiplication.In sections 3 and 4, we modify slightly the technique of section 6 of [CW90], which gives usan algorithm for $<n,n,n^2>$ having complexity $O(n^{3.3399})$. This will be a basic pattern for our further study.In section 5, we extend the technique of section 7 of [CW90], to improve our algorithm for $<n,n,n^2>$ and to yield the bound $O(n^{3.33396})$.In section 6, we show a basic fast algorithm for $<n^t,n,n^r>$ for an arbitrary pair of non-negative rational numbers $t$ and $r$,which we improve further in section 7. In section 8, we compare the algorithms developed in our paperwith various other effective algorithms and optimize the process of combining all these old and new algorithms together.We extend our improvement of rectangular matrix multiplication to the improvement of the known upper estimatesfor the work-complexity of determinstic parallel matrix computations in section 9,for polynomial composition and univariatepolynomial factorization over finite fields in section 10,and for finding basic solutions to the linear programmingproblem in section 11.{\bf Acknowledgement.} Erich Kaltofen pointed us out the applicationof rectangular matrix multiplication to polynomial factorization.\begin{center}{\Large \bf Part I. Acceleration of Rectangular Matrix Multiplication}\end{center} \section{Definitions and Some Background.}In this section, we introduce some basic concepts and definitionsconcerning matrix multiplication, define some new concepts, and recall some basic results.The problem of multiplying an $m \times n$ matrix by an $n \times p$matrix is denoted $<m,n,p>$.  Indices $i,j,k$ range from 0 to$m-1,~n-1,~p-1$, respectively.The asymptotic complexity of $m\times n$ by $n\times p$ matrixmultiplication can be expressed in terms of $A(m,n,p)$ denotingthe minimum number of arithmetic operations involved. There isa good motivation, however, to confine the study to bilinear algorithms. \\\noindent{\bf Definition 2.1,} {\itbilinear algorithms for matrix multiplication.}Given a pair of $m\times n$ and $n\times p$ matrices $X=[x_{i,j}]$, $Y=[y_{j,k}]$, compute $XY$ in the followingorder: First evaluate the linear forms in the $x$-variablesand in the $y$-variables,$$L_q=\sum_{i,j}f_{ijq}x_{ij}~,~~~~~~~~~~L_q^{\prime}=\sum_{j,k}f^*_{jkq}y_{jk}~,\eqno(2.1)$$then the products $P_q=L_qL^{\prime}_q$ for$q=0,1,\cdots,M-1$, and finally the entries$\sum_jx_{ij}y_{jk}$ of $XY$, as the linear combinations$$\sum_jx_{ij}y_{jk}=\sum_{q=0}^{M-1}f_{kiq}^{**}L_qL_q^{\prime}~,\eqno(2.2)$$where $f_{ijq},~f_{jkq}^*$ and $f_{kiq}^{**}$ are constantssuch that (2.1) and (2.2) are the identities in the indeterminates $x_{ij}$, $y_{jk}$, for $i=0,1,\cdots,m-1$; $j=0,1,\cdots,n-1$; $k=0,1,\cdots,p-1$.$M$, the total number of all multiplications of $L_q$ by$L_q^{\prime}$, is called the {\it rank of the algorithm},and the multiplications of $L_q$ by $L_q^{\prime}$ arecalled the {\it bilinear steps} of the algorithm or{\it bilinear multiplications}.\\The minimum number $M(m,n,p)$ of bilinearmultiplications used in all bilinear algorithms for $m\times n$by $n\times p$ matrix multiplication,  $<m,n,p>$, is an appropriate measurefor the asymptotic complexity of $<m,n,p>$due to the following known bound(cf. e.g. [Pan]):$$A(m^h,n^h,p^h)=O((M(m,n,p))^h)~~{\rm as}~~h\rightarrow \infty.\eqno(2.3)$$Besides, presently and historically, all the known algorithmssupporting the record asymptotic complexity estimates for matrixmultiplication have been devised as bilinear algorithms.We have the following simple known estimates (cf. e.g. [Pan]):$$M(m,n,1)=mn~,\eqno(2.4)$$$$M(m,n,p)\le M(m/q,n/q,p/q)M(q,q,q)\eqno(2.5)$$ for any $q$ that divides $m,~n$, and $p$. Furthermore, we have the following equations:$$M(m,n,p)=M(m,p,n)=M(n,p,m)=M(n,m,p)=M(p,n,m)=M(p,m,n),\eqno(2.6)$$of {\rm [Pan72]},$$M(n,n,r(n))=n^2+o(n)~~~{\rm if}~~~r(n)=o(\log n),~n\rightarrow \infty~~~~~~{\rm [BD76]}~,$$$$A(n,n,n^r)=O(n^{2+\epsilon})~~{\rm for~any}~~\epsilon>0~~{\rm if}~~r\le 0.197,~n\rightarrow \infty~~~~~~{\rm [Co82]}~,$$$$A(n,n,n^r)=O(n^{2+\epsilon})~~{\rm for~any}~~\epsilon>0~~{\rm if}~~r\le 0.294,~n\rightarrow \infty~~~~~~{\rm [Co97]}~.$$By extending (2.5), we obtain that $$M(m,n,p)=O(q^{\omega})\max(mn,np,pm)/q^2,~~~~ q=\min(m,n,p)\rightarrow \infty~,$$ provided that $M(q,q,q)=O(q^{\omega})$.Hereafter, the notation $L \rightarrow <m,n,p>$ indicates theexistence of a bilinear algorithm requiring $L$ essential (bilinear)multiplications in order to compute the indicated matrix product.If the algorithm is an ``any precision approximation (APA)algorithm'' [BCLR], we write$L \stackrel{\lambda}{\rightarrow} <m,n,p>$.If $k$ disjoint matrix products of the size $<m,n,p>$ are computed (sharing novariables), we write$L \rightarrow k <m,n,p>$.In this paper, we study the problems of matrix multiplication of the form $<n^r,n^s,n^t>$ with positive integers $n$ and non-negative rational numbers $r,~s$, and $t$. Let $O(n^{\omega(r,s,t)})$ denote the bilinearcomplexity of $<n^r,n^s,n^t>$, that is, $O(n^{\omega(r,s,t)})$ bilinear multiplications suffice for  solving the problem $<n^r,n^s,n^t>$. The $\omega(r,s,t)$ will be calledthe exponent for the problem $<n^r,n^s,n^t>$.Due to (2.6), we have$$\omega(r,s,t)=\omega(t,r,s)=\omega(s,t,r)=\omega(r,t,s)=\omega(s,r,t)=\omega(t,s,r)~.\eqno(2.7)$$Therefore, it suffices to estimate any oneof the six latter exponents for given $n,~r,~s$ and $t$.Since$$O(n^{\omega(ar,as,at)})=O((n^a)^{\omega(r,s,t)})=O(n^{a\omega(r,s,t)})~,$$the exponents $\omega(r,s,t)$ satisfy the following homogeneityequation: $$\omega(ar,as,at)=a\omega(r,s,t).$$ There is the straightforward (information) lower bound:$$\omega(r,s,t)\ge \max\{r+s,s+t,t+r\}~.\eqno(2.8)$$If $r=s=t$, then $<n^r,n^s,n^t>=<n^r,n^r,n^r>$ represents a squarematrix multiplication. Computing its bilinear complexity is reduced to computing the exponent $\omega(r,r,r)=r\cdot \omega(1,1,1)$,that is, to computing $\omega(1,1,1)$, by homogeneity. Currentrecord upper bound $\omega(1,1,1)=\omega<2.376$ is due to [CW90].If $r=s\ne t$, then $<n^r,n^s,n^t>$ represents multiplication of a square matrix by a rectangular matrix.Computing its bilinear complexity is reduced tocomputing the exponent $\omega(r,r,t)$,that is, to computing $\omega(1,1,t/r)=\omega(r,r,t)/r$, by homogeneity. The upper bound$$\omega(1,1,t/r)=2+o(1)~~~{\rm for}~~~t/r\le 0.294~~~{\rm [Co96]}$$ matchesthe lower bound $\omega(1,1,t/r)\ge 2$ of (2.2), up to the term $o(1)$.In this paper, we study the problem $<n^r,n^s,n^r>$ ofmultiplication of a rectangular matrix by a rectangular matrix,where $r,~s$ and $t$ are distinct from each other or at least $s\ne r$.We will use the following basic results.\begin{theorem}{\rm (Sch\"{o}nhage [Sc81]).} Assume given a field ${\bf F}$, coefficients $\alpha_{i,j,h,l},~\beta_{j,k,h,l},~\gamma_{k,i,h,l}$ in ${\bf F}(\lambda)$$($the field of rational functions in a single indeterminate $\lambda~)$,and polynomials $f_g$ over ${\bf F}$, such that$$\sum_{l=1}^L\left(\sum_{i,j,h}\alpha_{i,j,h,l}x_{i,j}^{(h)}\right)\left(\sum_{i,j,h}\beta_{j,k,h,l}y_{j,k}^{(h)}\right)\left(\sum_{i,j,h}\gamma_{k,i,h,l}z_{i,j}^{(h)}\right)$$$$=\sum_h\left(\sum_{i=1}^{m_h}\sum_{j=1}^{n_h}\sum_{k=1}^{p_h}x_{i,j}^{(h)}y_{j,k}^{(h)}z_{k,i}^{(h)}\right)+\sum_{g>0}\lambda^gf_g(x_{i,j}^{(h)},y_{j,k}^{(h)},z_{k,i}^{(h)})$$is an identity in $x_{i,j}^{(h)},~y_{j,k}^{(h)},~z_{k,i}^{(h)},~\lambda$.Then, given $\epsilon>0$, one can construct an algorithm to multiply$N\times N$ square matrices in $O(N^{3\tau+\epsilon})$ operations,where $\tau$ satisfies$$L=\sum_h(m_hn_hp_h)^{\tau}~.$$\end{theorem}Theorem 2.1 enables us to estimate $\omega(r,s,t)$ from above as soon aswe obtain a bilinear algorithm for a disjoint matrix multiplication,in particular, for $k$ disjoint problems $<m,n,p>.$\begin{theorem}{\rm (Salem and Spencer [SS42]).} Given $\epsilon>0$, there exists$M_{\epsilon}\simeq 2^{c/\epsilon^2}$ such that for all $M>M_{\epsilon}$,there is a set $B$ of $M'>M^{1-\epsilon}$ distinct integers,$$0<b_1<b_2<\cdots<b_{M'}<M/2,$$with no three terms in an arithmetic progression: for any tripleof $b_i,~b_j,~b_k\in B$, we have$$b_i+b_j=2b_k~~~{\it iff}~~~b_i=b_j=b_k~.$$\end{theorem}In our presentation, we will closely follow the line of [CW90]. In particular, as in [CW90], we will use theorem 2.2in order to transform tensor product construction into the form$k<m,n,p>$ for sufficiently large $k,~m,~n$ and $p$.\\{\bf Remark 2.1} Our study of matrix multiplication applies to the computation over arbitrary field of constants.\section{Basic Algorithm for $<n,n,n^2>$}~~~~~In this and the next sections, we will extensively use the techniquesof [CW90] (compare [Pan] and [St86] on some preceding work).We begin with a basic algorithm from [CW90], equation (5),which gives us one of the most effective examples of the trilinearaggregating techniques first introduced in [Pan72](cf. also [Pan] and [Pan,a]).For a given value of the integer $q$, we will call thisconstruction $D_q$.$$\begin{array}{l}\sum_{i=1}^q \lambda^{-2} (x_0^{[0]} + \lambda x_i^{[1]})(y_0^{[0]} + \lambda y_i^{[1]})(z_0^{[0]} + \lambda z_i^{[1]}) \\%\, \\~-\lambda^{-3} (x_0^{[0]} + \lambda^2\sum_{i=1}^q x_i^{[1]})(y_0^{[0]} + \lambda^2\sum_{i=1}^q y_i^{[1]})(z_0^{[0]} + \lambda^2\sum_{i=1}^q z_i^{[1]}) \\%\, \\~+[ \lambda^{-3}-q\lambda^{-2} ] (x_0^{[0]})(y_0^{[0]})(z_0^{[0]}) \\%\, \\~=\sum_{i=1}^q ( x_0^{[0]} y_i^{[1]} z_i^{[1]} + x_i^{[1]} y_0^{[0]} z_i^{[1]} + x_i^{[1]} y_i^{[1]} z_0^{[0]}) + O(\lambda).\end{array}\eqno{(3.1)}$$The $x$-variables in (3.1) consist of two blocks:$X^{[0]}=\{x_0^{[0]}\}$ and$X^{[1]}=\{x_1^{[1]},\cdots,x_q^{[1]}\}$. Similarly, the $y$-variables consist of blocks $Y^{[0]}$ and$Y^{[1]}$, and the $z$-variables consist of blocks $Z^{[0]}$ and $Z^{[1]}$. Our next goal is to estimate the exponent $\omega(1,1,2)$.Consider the $4N^{th}$ tensor power of (3.1). Each variable$x_i^{[I]}$ in the tensor power is the tensor productof $4N$ variables $x_j^{[J]}$, one from each of $4N$ copiesof the original algorithm (3.1). $j$ ranges in $\{0,1,2,\cdots, q\}$.The subscript $i$ is avector of dimension $4N$ formed by the $4N$ subscripts $j$. $J$ ranges in $\{0,1\}$. The superscript[$I$] is a vector of dimension $4N$ having entries in$\{0,1\}$, formed by the $4N$ superscripts $[J]$. Clearly,$[I]$ is uniquely determined by $i$.In our tensor power, there are $3^{4N}$ triples$(X^{[I]},Y^{[J]},Z^{[K]})$; each of them is a matrix product ofsome size $<m,n,p>$ with $mnp=q^{4N}$.We will eliminate some triples by setting to zero some blocks of variables$x,~y$ and/or $z$, so as to stay with some triples of the form$<q^N,q^N,q^{2N}>$sharing no variables.Then we will estimate the number of the remaining triples, which willdefine the exponent $\omega(1,1,2)$. When we zero a block $X^{[I]}$ (respectively, $Y^{[I]}$, $Z^{[I]}$), we will set to zero all the$x$-(respectively, $y$-, $z$-) variables with the given superscriptpattern.Hereafter,$\pmatrix{Q\cr Q_1, Q_2,\cdots,Q_s}$, for positive integers$Q,~Q_1,~Q_2,~\cdots,~Q_s$ satisfying $$Q_1+Q_2+\cdots+Q_s=Q,$$denote the multinomial expansion coefficient. Our presentationwill closely follow section 6 of [CW90].For all $i$ and $I$, set $x_i^{[I]}=0$, unless$I$ consists of $2N$ indices of 0 and exactly as many indicesof 1. For all $j$ and $J$, set $y_j^{[J]}=0$ unless$J$ consists of $N$ indices of 0 and $3N$ indices of 1, and similarly for $z_k^{[K]}$. When we complete thisprocedure, there still remain $\pmatrix{4N\cr 2N, N, N}$ blocksof triples $(X^{[I]},Y^{[J]},Z^{[K]})$. The blocks are compatible, which means that the locations of their zeroindices are disjoint, i.e. among the superscript vectors of$X^{[I]}Y^{[J]}Z^{[K]}$, there is one and only one zero in thelocation of the same component. (For example, for $N=2$,the block $X^{[10110100]}Y^{[11011011]}Z^{[01101111]}$ is compatible). Among them, for each block of variables $Z^{[K]}$, there are $\pmatrix{3N\cr 2N, N}$pairs$(X^{[I]},Y^{[J]})$ sharing this block; for each block $Y^{[K]}$, there are also $\pmatrix{3N\cr 2N, N}$pairs $(X^{[I]},Z^{[K]})$     sharing it; and for each block $X^{[I]}$, there are$\pmatrix{2N\cr N, N}$pairs $(Y^{[J]},Z^{[K]})$ sharing it. Set$M=2\pmatrix{3N\cr 2N, N}+1$. Select a sufficiently small positive$\epsilon$ and a sufficiently large $N$, so that the latter value$M$ would satisfy the assumptions of the Salem-Spencer theoremfor this $\epsilon$; construct a Salem-Spencer set $B$ (cf. [SS42], [Be46], and [CW90]), where the cardinality of $B$ is $M'\ge M^{1-\epsilon}$.In the next section, by revisiting the techniques of section 6 of [CW90], we obtain at least$$H={1\over 4}{M'\over M^2}\pmatrix{4N\cr 2N, N, N}\eqno(3.2)$$non-zero block products represented by the triples $(X^{[I]}Y^{[J]}Z^{[K]})$ and pairwise sharing no variables$X^{[I]},~Y^{[J]}$ or $Z^{[K]}$. The fine structure ofeach block scalar product represents a matrix product of the size$$<q^N,q^N,(q^N)^2>~.$$For $q^N=n$, this turns into $<n,n,n^2>$.For example, for $N=1$, the fine structure of the compatibletriple $X^{[1010]}Y^{[1101]}Z^{[0111]}$ is$$X_{i0k0}^{[1010]}Y_{ij0l}^{[1101]}Z_{0jkl}^{[0111]}~,~~~~i,j,k,l=1,2,\cdots,q,$$which represents the matrix product $$\pmatrix{x_{1010}&\cdots&x_{q010}\cr\vdots&\vdots&\vdots\crx_{10q0}&\cdots&x_{q0q0}}\pmatrix{y_{1101}&\cdots&y_{1q01}&|&\cdots&|&y_{110q}&\cdots&y_{1q0q}\cr\vdots&\vdots&\vdots&|&\cdots&|&\vdots&\vdots&\vdots\cry_{q101}&\cdots&y_{qq01}&|&\cdots&|&y_{q10q}&\cdots&y_{qq0q}}\pmatrix{z_{0111}&\cdots&z_{01q1}\cr\vdots&\vdots&\vdots\crz_{0q11}&\cdots&z_{0qq1}\cr\vdots&\vdots&\vdots\crz_{011q}&\cdots&z_{01qq}\cr\vdots&\vdots&\vdots\crz_{0q1q}&\cdots&z_{0qqq}}~.$$We deduce from the above algorithm and from theorem 2.2 that$$(q+2)^{4N}\ge cHn^{\omega(1,1,2)}~,\eqno(3.3)$$where $c$ is the overhead constant of $O(n^{\omega(1,1,2)})$ and $H$ is defined by (3.2). By applying Stirling's formula$$\lim_{n\rightarrow \infty}{\sqrt{2\pi n}\left({n\over e}\right)^n\over n!}=1\eqno{(3.4)}$$in order to estimate $H$, we obtain$$(q+2)^{4N}\ge c'N^{-{1\over 2}(1-\epsilon)}\left({4^4\over 3^3}\right)^N\left({2^2\over 3^3}\right)^{N\epsilon}q^{N\omega(1,1,2)}~~,\eqno{(3.5)}$$where $c'$ is a constant. Let $\epsilon \rightarrow 0$,$N\rightarrow \infty$, takethe $N^{th}$ roots and then logarithms of both sides of (3.5), and obtain that$$(q+2)^4\ge \left({4^4\over 3^3}\right)q^{\omega(1,1,2)}~,$$$$\omega(1,1,2)\le {1\over \log q}\log\left({27(q+2)^4\over 256}\right).$$The right-hand side is minimized for $q=10$:$$\omega(1,1,2)\le 3.339848783\ldots\le 3.3399~.\eqno{(3.6)}$$\section{The Number of Disjoint Nonscalar Block Products}~~~~~In this section, we will proceed again along the line of section 6 of [CW90]modified slightly so as to estimate$\omega(1,1,2)$, rather than $\omega(1,1,1)$.Choose integers $w_j$ at random in the interval from $0$ to $M-1$, for $j=0,1,2,\cdots,4N$, and compute the integers$$b_X(I)\equiv \sum_{j=1}^{4N}I_jw_j~(~{\rm mod}~M~),~~~~~~~~~~~~~~~~~~$$$$b_Y(J)\equiv w_0+\sum_{j=1}^{4N}J_jw_j~(~{\rm mod}~M~),~~~~~~~~~~~~~$$$$b_Z(K)\equiv (w_0+\sum_{j=1}^{4N}(2-K_j)w_j)/2~(~{\rm mod}~M~)~,$$where $I=(I_1,\cdots,I_{4N})\in \{0,1\}^{4N}$, $I_j$ is 0 or 1, $j=1,\cdots,4N$. As in [CW90], obtain that$$b_X(I)+b_Y(J)-2b_Z(K)\equiv 0~{\rm mod}~M~,$$for any triple of blocks ($X^{[I]},~Y^{[J]},~Z^{[K]}$) whoseproduct $X^{[I]}Y^{[J]}Z^{[K]}$ appears in the trilinear form. [Indeed, examine the contribution of each $w_j$ andobserve that for each of the three terms$$x_0^{[0]}y_i^{[1]}z_i^{[1]},~~~~~ x_i^{[1]}y_0^{[0]}z_i^{[1]},~~~~~ x_i^{[1]}y_i^{[1]}z_0^{[0]},$$we have $I_j+J_j+K_j=2$ in the basic construction.]Set $X^{[I]}=0$ unless $b_X(I)$ is in the Salem-Spencer set $B$,set $Y^{[J]}=0$ unless $b_Y(J)\in B$,  and set $Z^{[K]}=0$ unless $b_Z(K)\in B$.Then, for each triple ($I,J,K$),where $X^{[I]}Y^{[J]}Z^{[K]}\neq 0$, we have$$b_X(I)+b_Y(J)\equiv 2b_Z(K)~{\rm mod}~M~,~~~b_X(I),~b_Y(J),~b_Z(K)\in B~,$$and therefore,$$b_X(I)=b_Y(J)=b_Z(K)~,$$by the virtue of Salem-Spencer's theorem.We recall that theblock $X^{[I]}$ is the set of$q^{4N}$ variables $x_i^{[I]}$, with nonzero indices in $2N$ specified places, that is, sharing a common superscript $I$,a nonzero block is one which has not yet been set to zero;blocks $X^{[I]},~Y^{[J]},~Z^{[K]}$ are compatible if the locationsof their zero indices are pairwise disjoint. Let us complete the pruning procedure, as in [CW90]. Make listsof triples $(X^{[I]},Y^{[J]},Z^{[K]})$ representingcompatible nonzero blocks,with $b_X(I)=b_Y(J)=b_Z(K)=b$ for all $b\in B$. If any triple $(X^{[I]},Y^{[J]},Z^{[K]})$ on the list shares a block(say, $Z^{[K]}$) with another triple$(X^{[I']},Y^{[J']},Z^{[K']})$ occurring earlier in the list, then eliminate the former triple bysetting to zero one of the other blocks (say, $X^{[I]}$). Now, we apply the counting argument of [CW90] and extend the lemmaof section 6 of [CW90] as follows:\begin{lemma}The expected number of triples remaining on each list, afterpruning, is at least$${1\over 4M^2}\pmatrix{4N\cr 2N,N,N}~.$$\end{lemma}{\bf Proof:} Compare the expected number,$\pmatrix{4N\cr 2N,N,N}M^{-2}$, of triples in the listbefore pruning, for each $b\in B$, with the upper estimate$${3\over 2}\pmatrix{4N\cr 2N,N,N}\left(\pmatrix{2N\cr N,N}-1\right)M^{-3}$$for the expected number of unordered pairs of compatible triplessharing a $Z$-block, a $Y$-block, or an $X$-block. The latter number is anupper bound on the expected number of eliminated pairs of triples,which is easily showed to be not less than the expected number ofeliminated triples. Comparison of the two upper estimates givesus Lemma 4.1.~~~~~~~~~~~~~~~~$\Box$\\It follows from Lemma 4.1 thatthe expected number of triples remaining on all lists afterpruning (average over all the choices of $w_j$) is at least $H$ of (3.2).Therefore, we mayfix a choice of $w_j$ that achieves at least as many triples on the list.The procedure of computing $H$ can be summarized in thefollowing way:\\                \noindent{\bf Procedure 4.1}{\bf Step 1:} First compute the number of triples of blocks, having a fixedpatern $<n^r,n^s,n^t>$ among all the triples$(X^{[I]},Y^{[J]},Z^{[K]})$ that we have after taking the tensor power of agiven basic trilinear algorithm [like (3.1)]. In section 3, $<n^r,n^s,n^t>=<n,n,n^2>$,%such a number of special triples isand there are $\pmatrix{4N\cr 2N,N,N}$ special triples among a total of$3^{4N}$.{\bf Step 2:} Compute the numbers of pairs ($X^{[I]},Y^{[J]}$) sharing a single block $Z^{[K]}$,of pairs ($X^{[I]},Z^{[K]}$) sharing a single block $Y^{[J]}$, andof pairs ($Y^{[J]},Z^{[K]}$) sharing a single block $X^{[I]}$( in section 3, these numbers are $$\pmatrix{3N\cr 2N,N},~~~\pmatrix{3N\cr 2N,N},~~~\pmatrix{2N\cr N,N}~,$$respectively).Determine the largest of them ( here, the largest is$\pmatrix{3N\cr 2N,N}$ ).{\bf Step 3:} Perform the pruning procedure extending the one presented in this section in the straightforward wayand show that there still remain at least$$H={{\rm the~number~from~step~1}\over 4~\times~{\rm the~largest~from~step~2}}$$triples $(X^{[I]},Y^{[J]},Z^{[K]})$sharing no variables. \\ The latter procedure will be repeatedly applied in the next sections. \section{Improved Algorithm for $<n,n,n^2>$}~~~~~In this section, we will improve our upper bound on the exponent$\omega(1,1,2)$ from $3.3399$ to $3.333953$by combining the technique of Section 7 of [CW90] and the same ideas as in the previous section. The improvement will be due to using a more complicated starting algorithm, that is,the basic algorithm from [CW90], equation (10): $$\begin{array}{l}\sum_{i=1}^q \lambda^{-2} (x_0^{[0]} + \lambda x_i^{[1]})(y_0^{[0]} + \lambda y_i^{[1]})(z_0^{[0]} + \lambda z_i^{[1]}) \\%\, \\~~- \lambda^{-3} (x_0^{[0]} + \lambda^2\sum_{i=1}^q x_i^{[1]})(y_0^{[0]} + \lambda^2\sum_{i=1}^q y_i^{[1]})(z_0^{[0]} + \lambda^2\sum_{i=1}^q z_i^{[1]}) \\%\, \\~~+ [ \lambda^{-3}-q\lambda^{-2} ] (x_0^{[0]} + \lambda^3 x_{q+1}^{[2]})(y_0^{[0]} + \lambda^3 y_{q+1}^{[2]})(z_0^{[0]} + \lambda^3 z_{q+1}^{[2]}) \\%\, \\= \sum_{i=1}^q ( x_0^{[0]} y_i^{[1]} z_i^{[1]} + x_i^{[1]} y_0^{[0]} z_i^{[1]} + x_i^{[1]} y_i^{[1]} z_0^{[0]}) \\%\, \\~~+ x_0^{[0]} y_0^{[0]} z_{q+1}^{[2]} + x_0^{[0]} y_{q+1}^{[2]} z_0^{[0]} + x_{q+1}^{[2]} y_0^{[0]} z_0^{[0]} + O(\lambda).\end{array}\eqno{(5.1)}$$%\noindentThe subscripts now form three classes:$\{0\}$, $\{q+1\}$ and $\{1,2,\cdots,q\}$, which will againbe denoted $i$. Again, the subscripts uniquely determinethe superscripts (block indices).Take the $4N^{th}$ power of this construction. Each variable$x_i^{[I]}$ in the tensor power is the tensor productof $4N$ variables $x_j^{[J]}$, one from each of $4N$ copiesof the original algorithm (5.1). Its subscript $i$ is avector of dimension $4N$ with entries in                $\{0,1,2,\cdots, q, q+1\}$, formed by the $4N$ subscripts $j$. Its superscript[$I$] is a vector of dimension $4N$ with entries in$\{0,1,2\}$, formed by the $4N$ superscripts $[J]$. Set$L=\lceil \beta N \rceil$, where $\beta$ is a small positive number (which will be specified later on, roughly at the level of 0.02).As in the previous section, we currently have$6^{4N}$ triples $(X^{[I]},Y^{[J]},Z^{[K]})$.Set $x_i^{[I]}=0$, unless$I$ has exactly $2N$ indices of 0, exactly $2N-2L$ indicesof 1, and exactly $2L$ indices of 2; set $y_j^{[J]}=0$, unless $J$ has exactly $N+2L$ indices of 0, exactly $3N-3L$ indices of 1, and exactly $L$ indices of 2, andsimilarly for $z_k^{[K]}$. When we complete thisprocedure, there still remain$$\pmatrix{4N\cr L,L,2L,2N-2L,N-L,N-L}$$ blocks of triples $(X^{[I]},Y^{[J]},Z^{[K]})$.Namely, among the $4N$ copiesof construction (5.1), we pick$x_0^{[0]} y_i^{[1]} z_i^{[1]}$ from $2N-2L$ copies, $x_i^{[1]} y_0^{[0]} z_i^{[1]}$ from $N-L$ copies,$x_i^{[1]} y_i^{[1]} z_0^{[0]})$ from $N-L$ copies,$x_0^{[0]} y_0^{[0]} z_{q+1}^{[2]}$ from $L$ copies,$x_0^{[0]} y_{q+1}^{[2]} z_0^{[0]}$ from $L$ copies and$x_{q+1}^{[2]} y_0^{[0]} z_0^{[0]}$ from $2L$ copies.\\They are compatible, which means that the sum of indices at the samelocations of their superscripts $I$, $J$ and $K$ is 2. Among them, for each $Z^{[K]}$, there are $$\pmatrix{3N-3L\cr 2N-2L, N-L}\pmatrix{N+2L\cr N-L,2L,L}$$ pairs $(X^{[I]},Y^{[J]})$ sharing it; for each $Y^{[K]}$, there are as many pairs $(X^{[I]},Z^{[K]})$sharing it; but for each $X^{[I]}$, there are only $$\pmatrix{2N\cr 2N-2L,L,L}\pmatrix{2N-2L\cr N-L,N-L}$$ pairs $(Y^{[J]},Z^{[K]})$ sharing it. Select the larger (that is, the former) of the two numbers of pairs and set$$M=2\pmatrix{3N-3L\cr 2N-2L, N-L}\pmatrix{N+2L\cr N-L,2L,L}+1~~.$$ Construct a Salem-Spencer set$B$. Select random integers $0\le w_j<M,~j=0,1,2,\cdots,4N$.Then, by following the lines of section 7 of [CW90] and of our section 4, in particular, by applying Procedure 4.1,we obtain at least$$H^*={1\over 4}{M'\over M^2}\pmatrix{4N\cr L,L,2L,2N-2L,N-L,N-L}$$non-zero triples $(X^{[I]},Y^{[J]},Z^{[K]})$, which share no variables with each other, where $M'\ge M^{1-\epsilon}$, for a fixed positive $\epsilon$, is the cardinalityof $B$. Each of these triples corresponds toa matrix product of size$$<q^{N-L},q^{N-L},(q^{N-L})^2>~~,$$which turns into $<n,n,n^2>$ for $n=q^{N-L}$.Letting $M(n,n,n^2)=O(n^{\omega(1,1,2)})$ andsummarizing our estimates, we obtain$$(q+2)^{4N}\ge cH^*q^{(N-L)\omega(1,1,2)}~.$$Applying Stirling's formula to the value $H^*$, we obtain that$$(q+2)^{4N}\ge cN^{-1+{3\over 2}\epsilon}\left[{256\over \beta^{\beta}(3-3\beta)^{(3-3\beta)}(1+2\beta)^{(1+2\beta)}}\right]^N(c')^Nq^{N(1-\beta)\omega(1,1,2)}~.$$Let $\epsilon\rightarrow 0$, $N\rightarrow \infty$,take $N^{th}$ roots and then logarithms on both sides and deduce that$$(q+2)^4\ge {256\over \beta^{\beta}(3-3\beta)^{(3-3\beta)}(1+2\beta)^{(1+2\beta)}}q^{(1-\beta)\omega(1,1,2)}~,$$$$\omega(1,1,2)\le {1\over (1-\beta)\log q}\log\left({\beta^{\beta}(3-3\beta)^{(3-3\beta)}(1+2\beta)^{(1+2\beta)}(q+2)^4\over 256}\right)~.$$$q=9$ and $\beta=0.016$ minimizethe right-hand side of the latter inequality, and we obtain that$$\omega(1,1,2)\le 3.333953\ldots < 3.334~.$$\section{Basic Algorithm for $<n^r,n^s,n^t>$}~~~~~In this section, we will combine the ideas and techniques of sections 3 and 4so as to develop the basic algorithms for estimating the exponentsof rectangular matrix multiplications of arbitrary shape, that is, for the problem $<n^r,n^s,n^t>$. For convenience, we first classify the triples $<n^r,n^s,n^t>$,for all rational $r,~s,~t$ as follows:(1) $<n^r,n,n>$ with $r>1$;(2) $<n,n,n^t>$ with $0\le t\le 1$;(3) $<n^r,n,n^t>$ with $r>1>t>0$.Indeed, we have three respective classes of triples:(1) Among $r,~s,~t$, two are equal and the third one is larger. In this case, we may assume$r>s=t$ [cf. (2.1)]. Then, by homogeneity of the exponent,$\omega(r,s,t)=s\omega(r/s,1,1)$, $r/s>1$. (2) Among $r,~s,~t$, two are equal and the third one is not larger. In this case, we may assume$r=s\ge t$. Then, by homogeneity of the exponent, $\omega(r,s,t)=r\omega(1,1,t/r)$, $0\le t/r \le 1$. (3) Among $r,~s,~t$, all three are pairwise distinct. In this case, we may assume $r>s>t$. Then, by homogeneity of the exponent,$\omega(r,s,t)=s\omega(r/s,1,t/s)$, $r/s>1>t/s>0$. \subsection{The Case of $<n^r,n,n>$ with $r>1$}~~~~~Due to (2.6), we may assume that $<n,n,n^r>$ is case (1).We begin with the construction (3.1) again.Take the $(2+r)N^{th}$ tensor power of (3.1), where $N$is sufficiently large so that $(2+r)N$ is an integer. Each variable $x_i^{[I]}$ in the tensor power is the tensor productof $(2+r)N$ variables $x_j^{[J]}$, one from each of $(2+r)N$ copiesof the original algorithm (3.1). Its subscript $i$ is avector of dimension $(2+r)N$ with entries in$\{0,1,2,\cdots, q\}$, made up of the $(2+r)N$ subscripts $j$. Its superscript[$I$] is a vector of dimension $(2+r)N$ with entries in$\{0,1\}$, made up of the $(2+r)N$ superscripts $[J]$. Clearly,$[I]$ is uniquely determined by $i$.In our tensor power, there are totally $3^{N(2+r)}$ triples$(X^{[I]},Y^{[J]},Z^{[K]})$. We will eliminate sometriples and preserve those of dimension$<q^N,q^N,(q^N)^r>$, sharing no variables with each other.Then we will estimate the number of the remaining triples.Set $x_i^{[I]}=0$ unless$I$ has exactly $rN$ indices of 0 and exactly $2N$ indicesof 1, set $y_j^{[J]}=0$ unless$J$ has exactly $N$ indices of 0 and exactly $(1+r)N$ indices of 1, and similarly for $z_k^{[K]}$. When we complete thisprocedure, there still remain $\pmatrix{(2+r)N\cr N, N, rN}$ blocksof triples $(X^{[I]},Y^{[J]},Z^{[K]})$. They are compatible, which means that the locations of their zeroindices are disjoint. Among them, for each $Z^{[K]}$, there are $\pmatrix{(1+r)N\cr N, rN}$ pairs$(X^{[I]},Y^{[J]})$ sharing it; for each $Y^{[K]}$, thereare as many pairs $(X^{[I]},Z^{[K]})$sharing it; for each $X^{[I]}$, there are only $\pmatrix{2N\cr N,N}$ pairs $(Y^{[J]},Z^{[K]})$ sharing it. We select the larger(former) of the two latter estimates and set$$M=2\pmatrix{(1+r)N\cr N, rN}+1~.$$ Construct a Salem-Spencer set $B$ (cf. [SS42] and [Be46]), where the cardinality of $B$ is $M'\ge M^{1-\epsilon}$.In the same way as in the previous sections, we obtain at least$$\widetilde{H}={1\over 4}{M'\over M^2}\pmatrix{(2+r)N\cr N, N, rN}$$non-zero triples $(X^{[I]},Y^{[J]},Z^{[K]})$sharing no variables with each other,that is, our algorithm computes at least $\widetilde{H}$ blockproducts $(X^{[I]},Y^{[J]},Z^{[K]})$. The fine structure ofeach block product is a matrix product of size$$<q^N,q^N,(q^N)^r>~,$$which is $<n,n,n^r>$ for $q^N=n$. It follows that$$(q+2)^{(2+r)N}\ge c\widetilde{H}n^{\omega(1,1,r)}~,$$where $c$ is the overhead constant of $O(n^{\omega(1,1,r)})$. Applying Stirling's formulato approximate $\widetilde{H}$, we obtain$$(q+2)^{(2+r)N}\ge cN^{-{1\over 2}(1-\epsilon)}\left({(2+r)^{(2+r)}\over (1+r)^{(1+r)}}\right)^N(c')^{N\epsilon}q^{N\omega(1,1,r)}~~,$$where $c$ and $c'$ are constants. Let $\epsilon\rightarrow 0,~N\rightarrow \infty$, take$N^{th}$ roots, and obtain$$(q+2)^{(2+r)}\ge \left({(2+r)^{(2+r)}\over (1+r)^{(1+r)}}\right)q^{\omega(1,1,r)}~.$$By solving for $\omega(1,1,r)$, we obtain$$\omega(1,1,r)\le {1\over \log q}\log\left({(1+r)^{(1+r)}(q+2)^{(2+r)}\over (2+r)^{(2+r)}}\right)~.\eqno{(6.1)}$$\subsection{The Case of $<n,n,n^t>$ with $0\le t \le 1$}~~~~~We replace $t$ by $r$, for convenience.In this case the algorithm is almost completely the same as in the case of $<n^r,n,n>$ with $r>1$. The small difference is that we now set$$M=2\pmatrix{2N\cr N,N}+1~,$$since $\pmatrix{2N\cr N,N}$ exceeds $\pmatrix{(1+r)N\cr N,rN}$.We proceed as in subsection 6.1 and obtain that$$\omega(1,1,r)\le {1\over \log q}\log\left({2^2r^r(q+2)^{(2+r)}\over (2+r)^{(2+r)}}\right)~,\eqno{(6.2)}$$for $0\le r \le 1$.\subsection{The Case of $<n^r,n,n^t>$ with $r>1>t>0$}~~~~~Due to (2.6), we may assume that $<n^t,n,n^r>$ with $r>1>t>0$, instead of$<n^r,n,n^t>$ with $r>1>t>0$.In this case, wetake the $(t+1+r)N^{th}$ tensor power of (3.1), where $N$is sufficiently large so that $(t+1+r)N$ is an integer. In our tensor power, there are a total of $3^{N(t+1+r)}$ triples$(X^{[I]},Y^{[J]},Z^{[K]})$. As before, we will eliminate sometriples and preserve those of the dimension$<(q^N)^t,q^N,(q^N)^r>$ sharing no variables with each other.Then we will estimate the number of the remaining triples.Set $x_i^{[I]}=0$ unless $I$ has exactly $rN$ indices of 0 and exactly $(t+1)N$ indicesof 1, set $y_j^{[J]}=0$ unless $J$ has exactly $tN$ indices of 0 and exactly $(1+r)N$ indices of 1, and set $z_k^{[K]}=0$unless $K$ has exactly $N$ indices of 0 and exactly$(t+r)N$ indices of 1.When we complete this procedure, there still remain $\pmatrix{(t+1+r)N\cr tN, N, rN}$ blocks of triples $(X^{[I]},Y^{[J]},Z^{[K]})$. They are compatible, which means that the locations of their zeroindices are disjoint. Among them,  for each $Z^{[K]}$, there are $\pmatrix{(t+r)N\cr tN, rN}$pairs $(X^{[I]},Y^{[J]})$ sharing it; for each $Y^{[J]}$, there are $\pmatrix{(1+r)N\cr N, rN}$pairs $(X^{[I]},Z^{[K]})$ sharing it; for each $X^{[I]}$, there are$\pmatrix{(t+1)N\cr tN, N}$pairs $(Y^{[J]},Z^{[K]})$ sharing it. Since $r>1>t>0$, the second of these three estimates is the largest.So we set $$M=2\pmatrix{(1+r)N\cr N, rN}+1~.$$Similarly to subsection 6.1, we obtain that$$\omega(t,1,r)\le {1\over \log q}\log\left({(1+r)^{(1+r)}t^t(q+2)^{(t+1+r)}\over (t+1+r)^{(t+1+r)}}\right)~.\eqno{(6.3)}$$\\\section{Improved Algorithm for $<n^r,n^s,n^t>$}~~~~~In this section, we will improve our algorithmof section 6 for the problem $<n^r,n^s,n^t>$by combining the ideas from sections5 and 6. We break this section into threesubsections and respectively discuss the three cases, as in section 6.\subsection{The Case of $<n,n,n^r>$ with $r>1$}~~~~~We begin with the construction (5.1).Take the $(2+r)N^{th}$ tensor power of this construction, where $N$ is sufficiently large so that $(2+r)N$ is an integer. Each variable$x_i^{[I]}$ in the tensor power is the tensor productof $(2+r)N$ variables $x_j^{[J]}$, one from each of $(2+r)N$ copiesof the original algorithm (5.1). The subscript $i$ is avector of dimension $(2+r)N$ with entries in$\{0,1,2,\cdots, q, q+1\}$, made up of the $(2+r)N$ subscripts $j$. The superscript[$I$] is a vector of dimension $(2+r)N$ with entries in$\{0,1,2\}$, consisting of the $(2+r)N$ superscripts $[J]$.   Set$L=\lceil \beta N \rceil$, where $\beta$ is a small number to be determined later on (roughly at the level between 0.005 and 0.05). We currently have $6^{(2+r)N}$ triples $(X^{[I]},Y^{[J]},Z^{[K]})$.Set $x_i^{[I]}=0$ unless$I$ has exactly $r(N-L)+2L$ indices of 0, exactly $2(N-L)$ indicesof 1 and exactly $rL$ indices of 2; set $y_j^{[J]}=0$ unless $J$ has exactly $N+rL$ indices of 0, exactly $(1+r)(N-L)$ indices of 1 and exactly $L$ indices of 2, andsimilarly for $z_k^{[K]}$. When thisprocedure is completed, there still remain $$\pmatrix{(2+r)N\cr L,L,rL,r(N-L),(N-L),(N-L)}$$ blocks of triples $(X^{[I]},Y^{[J]},Z^{[K]})$,which means that, among the $(2+r)N$ copiesof construction (5.1), we pick$x_0^{[0]} y_i^{[1]} z_i^{[1]}$ from $r(N-L)$ copies, $x_i^{[1]} y_0^{[0]} z_i^{[1]}$ from $(N-L)$ copies,$x_i^{[1]} y_i^{[1]} z_0^{[0]}$ from $(N-L)$ copies,$x_0^{[0]} y_0^{[0]} z_{q+1}^{[2]}$ from $L$ copies,$x_0^{[0]} y_{q+1}^{[2]} z_0^{[0]}$ from $L$ copies, and$x_{q+1}^{[2]} y_0^{[0]} z_0^{[0]}$ from $rL$ copies.\\They are compatible, which means that the sum of indices at the samelocations of their superscripts $I$, $J$ and $K$ is 2. Among them, for each $Z^{[K]}$, there are $$\pmatrix{(1+r)(N-L)\cr (N-L),r(N-L)}\pmatrix{N+rL\cr (N-L),L,rL}$$ pairs $(X^{[I]},Y^{[J]})$ sharing it; for each $Y^{[K]}$, there are as many pairs $(X^{[I]},Z^{[K]})$sharing it; for each $X^{[I]}$, there are only $$\pmatrix{r(N-L)+2L\cr r(N-L),L,L} \pmatrix{2(N-L)\cr (N-L),(N-L)}$$ pairs $(Y^{[J]},Z^{[K]})$ sharing it. We select the larger former bound and set$$M=2\pmatrix{(1+r)(N-L)\cr (N-L),r(N-L)}\pmatrix{N+rL\cr (N-L),L,rL}+1~.$$ Construct a Salem-Spencer set$B$. Select random integers $$0\le w_j<M,~~~j=0,1,2,\cdots,(2+r)N.$$As before, we obtain at least$$\widehat{H}={1\over 4}{M'\over M^2}\pmatrix{(2+r)N\cr L,L,rL,r(N-L),(N-L),(N-L)}$$non-zero triples $(X^{[I]},Y^{[J]},Z^{[K]})$, which share no variables with each other, where $M'$ is the cardinalityof $B$ and $M'\ge M^{1-\epsilon}$. Each of them corresponds toa matrix product of size$$<q^{(N-L)},q^{(N-L)},q^{r(N-L)}>.$$For $n=q^{(N-L)}$, this turns into $<n,n,n^r>$.Letting $M(n,n,n^r)=O(n^{\omega(1,1,r)})$ andsummarizing, we obtain$$(q+2)^{(2+r)N}\ge c\widehat{H}q^{(N-L)\omega(1,1,r)}~.$$Applying Stirling's formula to approximate the value of right-hand side, we have$$(q+2)^{(2+r)N}\ge cN^{-1+{3\over 2}\epsilon}\left[{(2+r)^{(2+r)}\over \beta^{\beta}((1+r)(1-\beta))^{(1+r)(1-\beta)}(1+r\beta)^{(1+r\beta)}}\right]^N(c')^{\epsilon N}q^{N(1-\beta)\omega(1,1,r)}~.$$Letting $\epsilon \rightarrow 0, N\rightarrow \infty$,and taking $N^{th}$ roots, we obtain$$(q+2)^{(2+r)}\ge {(2+r)^{(2+r)}\over \beta^{\beta}((1+r)(1-\beta))^{(1+r)(1-\beta)}(1+r\beta)^{(1+r\beta)}}q^{(1-\beta)\omega(1,1,r)}~.$$Taking logarithms on both sides and solving for $\omega(1,1,r)$, we obtain the estimate $$\omega(1,1,r)\le {1\over (1-\beta)\log q}\log\left({\beta^{\beta}((1+r)(1-\beta))^{(1+r)(1-\beta)}(1+r\beta)^{(1+r\beta)}(q+2)^{(2+r)}\over (2+r)^{(2+r)}}\right)~.\eqno{(7.1)}$$\subsection{The Case of $<n,n,n^r>$ with $0\le r \le 1$}~~~~~We treat this case similarly to the case $r>1$. The small difference is that now$$\pmatrix{(1+r)(N-L)\cr (N-L),r(N-L)}\pmatrix{N+rL\cr (N-L),L,rL}<\pmatrix{r(N-L)+2L\cr r(N-L),L,L}\pmatrix{2(N-L)\cr (N-L),(N-L)}~.$$ Therefore, we set$$M=2\pmatrix{r(N-L)+2L\cr r(N-L),L,L} \pmatrix{2(N-L)\cr (N-L),(N-L)}+1~.$$ In the same way as in the preceeding subsection, we obtain the exponent bound$$\omega(1,1,r)\le {1\over (1-\beta)\log q}\log\left({(r\beta)^{(r\beta)}(2(1-\beta))^{2(1-\beta)}(r(1-\beta)+2\beta)^{(r(1-\beta)+2\beta)}(q+2)^{(2+r)}\over (2+r)^{(2+r)}}\right).\eqno{(7.2)}$$\subsection{The Case of $<n^r,n,n^t>$ with $r>1>t>0$}~~~~~Due to (2.6), we will discuss the problem$<n^t,n,n^r>$ with $r>1>t>0$, instead of$<n^r,n,n^t>$ with $r>1>t>0$.In this case, take the $(t+1+r)N^{th}$ tensor power of (5.1), where $N$is sufficiently large, so that $(t+1+r)N$ is an integer. Each variable$x_i^{[I]}$ in the tensor power is the tensor productof $(t+1+r)N$ variables $x_j^{[J]}$, one from each of $(t+1+r)N$ copiesof the original algorithm (5.1). The subscript $i$ is avector of dimension $(t+1+r)N$ with entries in$\{0,1,2,\cdots, q, q+1\}$, made up of the $(t+1+r)N$ subscripts $j$. The superscript[$I$] is a vector of dimension $(t+1+r)N$ with entries in$\{0,1,2\}$, made up of the $(t+1+r)N$ superscripts $[J]$. Set $L=\lceil \beta N \rceil$, where a small number $\beta$ will be determined later on (roughly at the level between 0.005 and 0.05). We currently have$6^{(t+1+r)N}$ triples $(X^{[I]},Y^{[J]},Z^{[K]})$.Set $x_i^{[I]}=0$ unless$I$ has exactly $tL+L+r(N-L)$ indices of 0, exactly $(t+1)(N-L)$ indices of 1 and exactly $rL$ indices of 2; set $y_j^{[J]}=0$ unless $J$ has exactly $t(N-L)+L+rL$ indices of 0, exactly $(1+r)(N-L)$ indices of 1, and exactly $tL$ indices of 2;set $z_k^{[K]}=0$ unless $K$ has exactly $tL+(N-L)+rL$ indices of 0, exactly $(t+r)(N-L)$ indices of 1 and exactly $L$ indices of 2.When we complete this procedure, there still remain at least$$\pmatrix{(t+1+r)N\cr tL,L,rL,t(N-L),(N-L),r(N-L)}$$ blocks of triples $(X^{[I]},Y^{[J]},Z^{[K]})$.%where (10.01) is a combination number and In accordance with this estimate, among the $(t+1+r)N$ copiesof construction (5.1), we pick$x_0^{[0]} y_i^{[1]} z_i^{[1]}$ from $r(N-L)$ copies, $x_i^{[1]} y_0^{[0]} z_i^{[1]}$ from $t(N-L)$ copies,$x_i^{[1]} y_i^{[1]} z_0^{[0]}$ from $(N-L)$ copies,$x_0^{[0]} y_0^{[0]} z_{q+1}^{[2]}$ from $L$ copies,$x_0^{[0]} y_{q+1}^{[2]} z_0^{[0]}$ from $tL$ copies, and$x_{q+1}^{[2]} y_0^{[0]} z_0^{[0]}$ from $rL$ copies.\\They are compatible, which means that the sum of indices at the samelocations of their superscripts $I$, $J$ and $K$ is 2. Among them, for each block $Z^{[K]}$, there are $$\pmatrix{(t+r)(N-L)\cr t(N-L),r(N-L)}\pmatrix{tL+(N-L)+rL\cr tL,(N-L),rL}$$ pairs $(X^{[I]},Y^{[J]})$ sharing it; for each $Y^{[K]}$, there are$$\pmatrix{(1+r)(N-L)\cr (N-L),r(N-L)}\pmatrix{t(N-L)+L+rL\cr t(N-L),L,rL}$$ pairs $(X^{[I]},Z^{[K]})$ sharing it; for each $X^{[I]}$, there are$$\pmatrix{(t+1)(N-L)\cr t(N-L),(N-L)}\pmatrix{tL+L+r(N-L)\cr tL,L,r(N-L)}$$ pairs $(Y^{[J]},Z^{[K]})$ sharing it. Since $r>1>t>0$, the largest of these three bounds is the second one. So, we set $$M=2\pmatrix{(1+r)(N-L)\cr (N-L),r(N-L)}\pmatrix{t(N-L)+L+rL\cr t(N-L),L,rL}+1~.$$ Along the line of subsection 7.1, we now obtain the exponent bound$$\omega(t,1,r)\le {1\over (1-\beta)\log q}\times$$$$\log\left({(t\beta)^{t\beta}((1+r)(1-\beta))^{(1+r)(1-\beta)}(t(1-\beta)+(1+r)\beta)^{(t(1-\beta)+(1+r)\beta)}(q+2)^{(t+1+r)}\over (t+1+r)^{(t+1+r)}}\right)~.\eqno(7.3)$$\\\section{Discussion on Optimization of Algorithms for Fast Rectangular Matrix Multiplications} ~~~~~In this section, we will compare our algorithms for rectangularmatrix multiplication of this paper with other possibleeffective algorithms and will choose some combination of our designsso as to optimize the exponents.We will discuss three cases, as in sections 6 and 7.\subsection{The Case of $<n,n,n^r>$ with $r>1$}~~~~~In this case, if we apply square matrix multiplication algorithm(cf. [CW90]), we obtain$$M(n,n,n^r)=n^{r-1}M(n,n,n)=n^{r-1}O(n^{\omega})=O(n^{r-1+\omega})~.$$Due to $\omega<2.376$ ([CW90]), $\omega(1,1,r)=r-1+\omega<r+1.376$.Let $g(r)=r+1.376$, then $g(r)$ is an increasinglinear function in the interval $[1,\infty)$ and passes throughthe points $(1,2.376)$ and $(2,3.376)$, where$g(1)=2.375477\ldots$ agrees with the result of section 8 of [CW90].Let $f(r)$ denote the right-hand side of (7.1), that is, the exponentestimate for$<n,n,n^r>$ based on the algorithmof subsection 7.1. By combining the results of section 5 and 7, we obtain that$f(r)$ is an increasing function in the interval $[1,+\infty)$ passing through the points $(1,~2.38719)$ and (2,~3.334). For $r=1$, $f(1)=2.38719$agrees with the result of section 7 of [CW90], and$f(2)=3.334$ agrees with the result of section 5. Near the point $r=1.171$, we have $f(r)\approx g(r)=r+1.376$. For $q=7$ and $\beta=0.0336$, $f(1.171)=2.546462806\ldots<g(1.171)=2.546477\ldots$.According to this examination, (7.1) minimizes the exponent for $r\ge 1.171-\epsilon$ for an appropriate small positive $\epsilon$.\subsection{The Case of $<n,n,n^r>$ with $0\le r \le 1$}~~~~~In this case, we let $f(r)$ be the right-hand side of (7.2).$f(r)$ is a monotone increasing continuous function in the interval $[0,~1]$passing through the points $(0,~2+\epsilon)$ and $(1,~2.38719)$.The exponent estimate given by $f(r)$ for $r\in [0,1]$ is not yet the best, however.A better exponent bound for $r\in [0,1]$ is given by$$\omega(1,1,r)=\left\{ \begin{array}{ll}2+o(1)~,& \mbox{$0\le r\le 0.294=\alpha$},\\{2(1-r)+(r-\alpha)\omega\over 1-\alpha}~,& \mbox{$0.294<r\le 1$}~.\end{array} \right.~ \eqno(8.1)$$Here is its derivation:$\omega(1,1,r)\le 2+o(1),~0\le r\le 0.294=\alpha$ comes from [Co96], andwe also have$$\omega(1,1,r)\le {2(1-r)+(r-\alpha)\omega\over 1-\alpha},~~\alpha=0.294<r\le 1~.$$Indeed, $$\begin{array}{l}~~M(n,n,n^r)\\=M(n^{1-r\over 1-\alpha}\cdot n^{r-\alpha\over 1-\alpha},n^{1-r\over 1-\alpha}\cdot n^{r-\alpha \over 1-\alpha},n^{(1-r)\alpha \over 1-\alpha}\cdot n^{r-\alpha \over 1-\alpha})\\\le M(n^{1-r\over 1-\alpha},n^{1-r\over 1-\alpha},n^{(1-r)\alpha\over 1-\alpha})\cdot M(n^{r-\alpha\over 1-\alpha},n^{r-\alpha\over 1-\alpha},n^{r-\alpha\over 1-\alpha})~~~~\\%({\rm cf.~[Sc81]})\\=O((n^{1-r\over 1-\alpha})^{2+\epsilon}(n^{r-\alpha\over 1-\alpha})^{\omega})\\=O(n^{2(1-r)+(r-\alpha)\omega\over 1-\alpha})~.\end{array}$$Summarizing the two cases above, we have the optimal choice of our parameters represented by the curves of {\bf Figure 1}. %\input{fig011.tex}\begin{figure}\begin{picture}(470,450)(0,0)\put(10,10){\thicklines \vector(0,1){450}}\put(10,10){\thicklines \vector(1,0){415}}\put(10,190){\line(1,0){90}}\put(10,100){\line(1,0){5}}\put(10,280){\line(1,0){5}}\put(10,370){\line(1,0){5}}\put(3,188){2}\put(3,98){1}\put(3,278){3}\put(3,368){4}%\put(100,10){\line(0,1){180}}\put(100,10){\line(0,1){5}}\put(190,10){\line(0,1){5}}\put(280,10){\line(0,1){5}}\put(370,10){\line(0,1){5}}%\put(460,10){\line(0,1){5}}\put(1,2){(0,0)}\put(98,2){1}\put(188,2){2}\put(278,2){3}\put(368,2){4}%\put(458,2){5}\put(430,7){$r$}\put(0,465){$\omega(1,1,r)$}\put(100,190){\line(1,1){250}}\put(10,190){\line(1,1){220}}\put(145,326){\vector(-1,2){20}}\put(70,370){upper bound is $2+r$}\put(325,413){\vector(1,-2){20}}\put(300,365){lower bound is $1+r$} \put(300,345){if $r>1$, and is 2 if}\put(300,325){$0\le r\le 1$.}\put(100,213.84){\circle*{1}}\put(100,213.84){\line(1,1){240}}\put(280,395.86){\vector(-1,2){20}}\put(200,443.90){$\omega(1,1,r)=r+1.376$}\put(100,214.8471){\circle*{1}}\put(100,214.8471){\line(3,2){36}}\put(100,214.8471){\line(-4,-1){85}}\put(50,201){\vector(3,-1){120}}\put(175,155){(7.2)}\put(136,238.8471){\line(1,1){220}}\put(230,330.86){\vector(1,-2){20}}\put(250,280){(7.1)}\put(100,216.3276){\circle*{1}}\put(100,216.3276){\line(3,2){30}}\put(130,236.3276){\line(1,1){220}}\put(190,298.86){\vector(-1,2){10}}\put(165,320.90){(6.1)}\put(100,216.3276){\line(-4,-1){85}}\put(30,200){\vector(0,1){30}}\put(25,233){(6.2)}\put(100,213.84){\line(-3,-1){70}}\put(40,193){\vector(0,-4){40}}\put(25,144){(8.1)}\put(22,189){\vector(1,-4){9}}%\put(475,7){$r$}\put(0,465){$\omega(1,1,r)$}\put(100,190){\line(1,1){250}}\put(55,120){Notes:}\put(55,100){1. The curve of $\omega(1,1,r)=r+1.376$ is parallel tothe lower bound $1+r$}\put(72,80){for $r\ge 1$;}\put(55,60){2. (6.1) and (7.1) have the lower bound $1+r$ as anasymptote as $r\rightarrow \infty$;}\put(55,40){3. $\omega(1,1,r)=r+1.376$ is existing record upper bound for $r\ge 1$.}%\put(135,80){(7.1) is ``better'' than $1+r$ for $r\ge 1.171$.}\end{picture}\caption{Illustration of exponent curves $\omega(1,1,r)$ for $<n,n,n^r>$, $0\le r<+\infty$.(6.1), (6.2), (7.1), (7.2) and (8.1) refer to the respective equations of this paper.}\end{figure}%\input{figure2.tex}\begin{figure}\begin{picture}(470,200)(1,2)\put(10,10){\thicklines\vector(0,1){150}}\put(10,10){\thicklines\vector(1,0){415}}\put(100,100){\line(1,0){320}}\put(100,36.46){\line(1,0){320}}\put(16,100){1}\put(10,100){\line(1,0){5}}\put(16,36.46){0.294}\put(10,36.46){\line(1,0){5}}\put(100,10){\line(0,1){90}}\put(190,10){\line(0,1){5}}\put(280,10){\line(0,1){5}}\put(370,10){\line(0,1){5}}%\put(460,10){\line(0,1){5}}\put(1,2){(0,0)}\put(98,2){1}\put(188,2){2}\put(278,2){3}\put(368,2){4}%\put(458,2){5}\put(430,7){$r$}\put(10,165){$t$}\put(115.39,100){\line(1,-1){10}}\put(125.39,90){\line(3,-1){30}}\put(155.39,80){\line(6,-1){240}}\put(396,39.5){\line(1,0){25}}\put(100.39,105){(1.171~,~1)}\put(120,18){$g(r,0\le t\le 0.294)=1+r+\epsilon$}\put(120,50){$g(r,0.294<t\le 1)$}\put(275.39,80){(7.3)~~$f(r,t)$}\end{picture}\caption{the three areas are, respectively, the optimal regionof the three exponent functions for$<n^t,n,n^r>$, $0\le t\le 1\le r$.}\end{figure}\subsection{The Case of $<n^t,n,n^r>$ with $r>1>t>0$}~~~~~In this case, we first deduce a small upper bound on the exponent $\omega(t,1,r)$.[For lower bound, see (2.4).]\begin{theorem} Let $\omega(t,1,r)$ be the exponent of $<n^t,n,n^r>$. Then$$\omega(t,1,r)=\left\{ \begin{array}{ll}r+1+\epsilon~,& \mbox{$0\le t\le 0.294=\alpha$}~,\\{r(1-\alpha)+(1-t)+(\omega-1)(t-\alpha)\over 1-\alpha}~,& \mbox{$0.294<t\le 1$}~.\end{array} \right. \eqno(8.2)$$\end{theorem}\noindent{\bf Proof:} For $0\le t\le 0.294=\alpha$, we have$$\begin{array}{l}~~M(n^t,n,n^r)\\=n^{r-1}M(n,n,n^t)\\\le n^{r-1}M(n,n,n^{\alpha})\\=n^{r-1}O(n^{2+\epsilon})~~~~(\rm cf.~[Co96])\\=O(n^{r+1+\epsilon})~,\end{array}$$that is, $\omega(t,1,r)=r+1+\epsilon$.For $\alpha=0.294<t\le 1$, the current best exponent estimate can be derived as follows:$$\begin{array}{l}~~M(n^t,n,n^r)=M(n^r,n,n^t)\\=M(n^{r-{t-\alpha\over 1-\alpha}}\cdot n^{t-\alpha\over 1-\alpha},n^{1-t\over 1-\alpha}\cdot n^{t-\alpha\over 1-\alpha},n^{(1-t)\alpha\over 1-\alpha}\cdot n^{t-\alpha\over 1-\alpha})\\\le M(n^{r-{t-\alpha\over 1-\alpha}},n^{1-t\over 1-\alpha},n^{(1-t)\alpha\over 1-\alpha})\cdot M(n^{t-\alpha\over 1-\alpha},n^{t-\alpha\over 1-\alpha},n^{t-\alpha\over 1-\alpha})~~~~\\ %({\rm cf.~[Sc81]})\\=O((n^{r-{t-\alpha\over 1-\alpha}+{1-t\over 1-\alpha}+\epsilon})(n^{t-\alpha\over 1-\alpha})^{\omega})\\=O(n^{r-{t-\alpha\over 1-\alpha}+{1-t\over 1-\alpha}+{\omega(t-\alpha)\over 1-\alpha}})\\=O(n^{r(1-\alpha)+(1-t)+(\omega-1)(t-\alpha)\over 1-\alpha})~.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\Box\end{array}$$Let $f(r,t)$ denote the right-hand side of (7.3), let $g(r,0\le t\le \alpha)=1+r+\epsilon$, and let$$g(r,\alpha<t\le 1)={r(1-\alpha)+(1-t)+(\omega-1)(t-\alpha)\over 1-\alpha}~.\eqno(8.3)$$We combine these relations, and in {\bf figure 2}, we representthe resulting exponents in this parameter range.%\input{figure2.tex}\pagebreak\newpage%\part{Applications of Algorithms for %Fast Rectangular Matrix Multiplications %to Accelerations of Parallel Matrix Computations and of Composition%and Factorization of Polynomials over Finite Fields}\newpage%\section{Improved Complexity of Parallel Evaluation of the Determinant%and of the Inverse of a Matrix}\begin{center}{\Large \bf Part II. Applications of Fast Rectangular Matrix Multiplication}\end{center}\section{Application to Parallel Matrix Computations}~~~~~In this section, we will assume the customary EREW PRAM machinemodel of parallel computing [EG88], [KR90] and apply the results of section 8 in order to improve the record work-complexity deterministic estimates of [GP89] for fast (NC) parallel solution of the three following problems:1) compute the determinant and the characteristic polynomial of a given$n\times n$ rational, real, or complex matrix $A$;2) solve a linear system $Ax=b$;3) invert $A$.We first repeat some basic definitions from [GP89], which are used in themain theorem and its corollary in [GP89].\\\noindent{\bf Definition 9.1.} $P(n)$ is the minimum number of arithmeticprocessors, and $W(n)=O(P(n)\log^2n)$ is the minimum arithmetic work ( that is, the product of time and processor bounds ) supporting$O(\log^2 n)$ parallel time bound for solving problems (1), (2) and (3)under the EREW PRAM model of parallel computing;$P(*,m,n,p)$ is the minimum number of arithmetic processors, and$$W(*,m,n,p)=O(P(n)\log(mnp))$$ is the minimum arithmetic work supporting$O(\log(mnp))$ parallel time bound for multiplication of $m\times n$by $n\times p$ matrices; $P(*,n)=P(*,n,n,n)$, $W(*,n)=W(*,n,n,n)$.  The following theorem and its corollary are from [GP89]:\begin{theorem}The solution to Problem (1) and (2) can be computed by using $O(\log^2 n)$parallel steps and simultaneously$$P(det,n)=\max\{P(*,n^{1.25},n,n^{1.25}),P(*,n^{0.5},n^2,n^{0.5})\}$$processors, yielding the work-complexity bound$$W(det,n)=O(P(det,n)\log^2n)=\max\{W(*,n^{1.25},n,n^{1.25}),W(*,n^{0.5},n^2,n^{0.5})\}.$$The solution to Problem (3) can be computed by using $O(\log^2 n)$ stepsand                                            $$P(n)=\min_{v,u}\max\{P(det,n),P(*,u+1,v,n^2),P(*,n,nu,n)\}$$processors, where the minimum is over all pairs $v$ and $u$ such that$$vu\le n+1\le (v+1)u~.$$This yields the work bound$$W(n)=\min_{v,u}\max\{W(det,n),W(*,u+1,v,n^2),W(*,n,nu,n)\}.$$\end{theorem}Substitute the bound $P(*,n)=O(n^{2.376})$ and obtain\noindent{\bf Corollary 9.1.}{\it The solutions to Problems (1), (2) and (3) can be computed by usingsimultaneously $O(\log ^2 n)$ steps, $P(n)=O(n^{2.851})$ arithmetic processors and $W(n)=O(n^{2.851})$ arithmetic work.}\\We will also need the following result, which extends Proposition 4.3.2 of [BP94]from the case of square to rectangular matrices:\begin{theorem}The product $XY$ of an $n^{ts}\times n^s$ matrix $X$ by an $n^s\times n^{rs}$matrix $Y$ can be computed by using parallel time $O((t+r+1)s\log n)$ and  $O(n^{\overline{\omega}(t,1,r)s})$ arithmetic processors, where $n>1,~s\rightarrow \infty$, and$\overline{\omega}(t,1,r)$ is any number exceeding the value $\omega(t,1,r)$ defined in section 2.\end{theorem}{\bf Proof:} With no loss of generality, we may assume (see, for instance, [BM75],section 2.5, or [Pan]) that an $n^t\times n$ by $n\times n^r$ matrixproduct $X_0Y_0$ is computed by means of a bilinear algorithm(cf. Definition 2.1).Now we apply the tensor product construction to such a bilinear algorithm,that is, we apply this algorithm recursively in order to multiply thematrices $X$ and $Y$ whose entries are $n^t\times n$ and $n\times n^r$matrices, respectively. This will give us a recursive bilinear algorithmsfor multiplication of $n^{ts}\times n^s$ by $n^s\times n^{rs}$ matrices,for $s=1,2,\cdots$, and we have$$t_{s+1}\le t_s+(1+\max(r,t))\log_2 n+\log_2 M+4~,$$$$p_{s+1}\le \max\{n^{(r+t+2)(s+1)},n^{(r+t)(s+1)}M,p_sM\}~,$$where $N=n^{\max(1+r,1+t,r+t)}$, $t_l$ and $p_l$ denote the parallel time and the number of arithmeticprocessors used in the above recursivebilinear algorithm for $n^l\times n^l$ matrix multiplication. Since  $M\le n^{\overline{\omega}(t,1,r)}$, the latter recursive relationsimmediately lead to Theorem 9.2.~~~~~~~~~~~~~~~~$\Box$\\Next, we will apply the results of our section 8 in order to improve the boundson $P(n)$ and $W(n)$ from $O(n^{2.851})$ of Corollary 9.1to $O(n^{2.837})$. Due to Theorems 9.1 and 9.2,it suffices to improvethe upper estimate $O(n^{2.837})$for the sequential complexity of the fourfollowing problems of rectangular matrix multiplication$$<n^{1.25},n,n^{1.25}>,~~~~<n^{1/3},n^{2/3},n^2>,~~~~<n,n^{4/3},n>,~~~~<n^{0.5},n^2,n^{0.5}>~,$$defined by the four following exponents:$$\omega(1.25,1,1.25),~~~\omega(1/3,2/3,2),~~~\omega(1,4/3,1),~~~\omega(0.5,2,0.5)~~.$$By applying the results of section 8, we obtain that$$\omega(1.25,1,1.25)=1.25\omega(1,1,0.8)=2.8368\ldots<2.837~~~~(~{\rm by~applying~(8.1)~for}~\omega=2.376~),$$$$\omega(1/3,2/3,2)={2\over 3}\omega(0.5,1,3)=2.7398\ldots~~~~(~{\rm by~applying~(8.2)~for}~\omega=2.376~),$$$$\omega(1,4/3,1)=\omega(1,1,1.33\cdots)=2.6993\ldots~~~~(~{\rm by~selecting}~q=7,~\beta=0.033~{\rm in~(7.1)}~), $$$$\omega(0.5,2,0.5)=0.5\omega(1,1,4)=2.6390\ldots~~~~(~{\rm by~selecting}~q=14,~\beta=0.0026~{\rm in~(7.1)}~).$$Combining the four latter bounds with Theorems 9.1 and 9.2, we arrive at the bounds $W(n)=O(n^{2.837})$ and$P(n)=O(W(n))$.\\\noindent{\bf Remark 9.1} The bound $W(n)=O(n^{2.837})$ can be decreased if$\omega=\omega(1,1,1)$ is decreased below 2.376 and also if $\alpha$is increased above 0.294. Namely, our argument above, togetherwith (8.1) and (8.2) implies that$$W(n)=O(\max\{W_1(n),W_2(n),W_3(n),W_4(n)\})~,$$where $$W_1(n)=n^{\omega_1},~~~\omega_1=\omega(1.25,1,1.25)=1.25{0.4+(0.8-\alpha)\omega \over 1-\alpha}~~~[{\rm cf.}~(8.1)],$$$$W_2(n)=n^{\omega_2},~~~\omega_2=\omega(1/3,2/3,2)={2\over 3}\omega(0.5,1,3)=\left({2\over 3}\right){3(1-\alpha)+0.5+(\omega-1)(0.5-\alpha)\over 1-\alpha}\eqno[{\rm cf.}~(8.2)],$$$$W_3(n)=n^{\omega_3},~~~\omega_3=\omega(1,4/3,1)<2.7,$$$$W_4(n)=n^{\omega_4},~~~\omega_4=\omega(0.5,2,0.5)<2.64.$$Clearly, $\omega_1$ and $\omega_2$ decrease as $\omega$ decreasesand/or $\alpha$ increases.\noindent{\bf Remark 9.2} Randomized parallel solution of the listed problems(1)-(3) only requires polylogarithmic time and work $O(n^{2.376})$(cf. [BP94]).\section{Acceleration of Polynomial Composition and Factorization of Polynomials over Finite Fields}We will extend our results of Part I to accelerate polynomial composition and factorization.To reach maximum effect, we will modify some of the known reductionsof these polynomial computations to matrix multiplication( see subsection 10.5 ).\subsection{Introduction}In this section, we will apply the results of Part I on fast rectangularmatrix multiplication in order to improve the known estimatesfor the computational complexity of polynomial composition and thefactorization of univariate polynomials over finite fields, whichare major problems of algebraic computing. We refer the reader to[GS92] and [KS95] on the background of the latter fundamental problem. \subsection{Some Definitions and Preliminary Results}For reader's convenience,in this subsection, we restate some definitions and results of Part I, that we will apply in this section. ``Ops'' stands for ``arithmeticoperations'', and ``bms'' stands for ``bilinear multiplications''. $<m,n,p>$ denotes the problem of multiplying a pair of $m\times n$ by $n\times p$ matrices. We represent the complexity of $<n^r,n^s,n^t>$ by the number of bilinearmultiplications (bms) required, $M(n^r,n^s,n^t)$.  \noindent\begin{theorem} {\rm (Part I, section 5)}. The problem $<n,n,n^2>$ of rectangular matrix multiplication can be solved by using $O(n^{3.333953\ldots})$ bms, that is, the exponent of the arithmeticcomplexity of $<n,n,n^2>$ is $\omega(1,1,2)\le 3.333953\ldots$.\end{theorem}\noindent\begin{theorem} {\rm (Part I, section 7)}.The problem $<n,n,n^r>$ of rectangular matrix multiplication can be solved by using $O(n^{\omega(1,1,r)})$ bms, where $r\ge 1$ is a rational number, the matrix exponent$\omega(1,1,r)$ is bounded as follows:$$\omega(1,1,r)\le \min_{l,b}{1\over (1-b)\log l}\log\left({b^b((1+r)(1-b))^{(1+r)(1-b)}(1+rb)^{(1+rb)}(l+2)^{(2+r)}\over (2+r)^{(2+r)}}\right)~,$$where $l\ge 2$ is an integer and $0\le b \le 1$.\end{theorem}\noindent\begin{theorem} {\rm (Part I, section 8)}.The problem $<n^t,n,n^r>$ of Rectangular Matrix Multiplication (where $0\le t\le 0.294,~r\ge 1$) can be solved by using $O(n^{r+1+\epsilon})$ bms.\end{theorem}\subsection{Complexity of Modular Polynomial Composition}\begin{theorem}Let$$p(x)=p_0+p_1x+p_2x^2+\cdots+p_nx^n~,$$$$q(x)=q_0+q_1x+q_2x^2+\cdots+q_nx^n$$be two polynomials. The arithmetic complexity of computing thecoefficients of the polynomial$$p(q(x))~{\rm mod}~x^{n+1}$$is $O(M(n,\sqrt{n},\sqrt{n}))=O(n^{3.334/2})=O(n^{1.667})$.\end{theorem}{\bf Proof.} Algorithm 2.1 of [BK78] for computing $p(q(x))~{\rm mod}~x^{n+1}$has its complexity dominated by the complexity of the problem $<n,\sqrt{n},\sqrt{n}>$.Consequently, Theorem 10.4 immediately follows from Theorem 10.1. $~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\Box$\\For comparison, the known exponent for the complexity of the aboveproblem of modular polynomial composition was obtained by reductionof the problem $<n,\sqrt{n},\sqrt{n}>$ to $\sqrt{n}$ blocks ofsquare $\sqrt{n}\times \sqrt{n}$ matrix multiplication, so that  $$M(n,\sqrt{n},\sqrt{n})\le \sqrt{n} M(\sqrt{n},\sqrt{n},\sqrt{n})$$( cf. e.g. [KS95] ). The resulting exponent 1.688 exceeds oneof Theorem 10.4 by 0.021.\subsection{Factorization of Polynomial over Finite Fields( Two Approaches )}There are two major approaches to the factorization of aunivariate polynomial of a degree $n$ over the finite field${\bf F}_q$ with $q$ elements. These approaches are due to Berlekam [B70] and Cantor and Zassenhaus [CZ81]. Both of the approaches lead to randomized algorithms and were recentlyimproved in [GS92] and [KS94], to yield the current record complexity estimates for the factorization problem. We willshow further improvemnent of all these record estimates, byusing fast matrix multiplication. We will follow the flowchartof [KS94], where the two cited approaches are treated separatelyand the Cantor/Zassenhaus approach is partitioned into the studyof the two cases-of the equal-degree and distinct-degree factorization of a polynomial, where all the factors must havethe some (equal) degree or all must have distinct degrees,respectively. Thus we will study these two approaches ( one withtwo subcases ) in the next three sections.Our Theorems 10.5-10.7 will specify our record complexity estimatesfor polynomial factorization, which depend on the two parameters,$n$ ( the degree of the polynomial ) and $q$ ( the cardinality ofthe field ). In particular, we yield the factorization over${\bf F}_q$ by using$O(n^{1.8536}+n^{1.763}\log q)$ field operations or alternatively,$O(n^{1.80535}\log q)$, versus the previous record bounds$O(n^{1.852}+n^{1.763}\log q)$ and $O(n^{1.815}\log q)$ of [KS94].As in [KS94], our latter record bound is obtained based on each of the two approaches, that is, Cantor/Zassenhaus' and Berlekamp's.\subsection{Complexity of Equal-Degree Polynomial Factorizationover Finite Fields}The probabilistic algorithm of von zur Gathen and Shoup (cf. [GS92]) solves the equal-degree factorization problem for a univariate polynomial of a degree $n$ overthe finite field ${\bf F}_q$ with $q$ elements by using the expected number of $$O(n^{(\omega+1)/2+o(1)}+n^{1+o(1)}\log q)$$or$$O(n^{1.688}+n^{1+o(1)}\log q)$$operations in ${\bf F}_q$. Here, $n^{(\omega+1)/2+o(1)}$is the estimated complexity of polynomial composition modulo $x^n$.Due to our Theorems 10.1 and 10.4 and Remark 2.1, the bound on the complexity of the equal-degree factorization problem can be immediately improved as follows.\noindent\begin{theorem}The equal-degree factorization of a univariate polynomial of a degree $n$ over the finite field ${\bf F}_q$ with $q$ elementscan be computed probabilistically by using an expected number of$$O(M(n,\sqrt{n},\sqrt{n}))=O(n^{1.667}+n^{1+o(1)}\log q)$$operations in ${\bf F}_q$.\end{theorem}\subsection{Complexity of Distinct-Degree Factorization overa Finite Field}Section 2 of [KS95] presents a (deterministic) algorithm(Algorithm D) for the distinct-degree factorization of a polynomialof a degree $n$ over the finite field ${\bf F}_q$ with $q$ elements.The algorithm uses$$O(n^{(\omega+1)/2+(1-\beta)(\omega-1)/2}+n^{1+\beta+o(1)}\log q)$$operations in ${\bf F}_q$, for any $\beta$ in the interval $0\le \beta\le 1$ (see Theorem 3 in [KS95]).By substituting $\omega<2.375477$ of [CW90] and thenminimizing the exponent of $n$, Kaltofen and Shoup obtained the estimate of $O(n^{1.815}\log q)$operations in ${\bf F}_q$ ( cf. [KS95], Theorem 3 ). We will next improve this bound as follows:\noindent\begin{theorem}Distinct degree factorization of a univariate polynomial overa finite field ${\bf F}_q$ with $q$ elements can be computeddeterministically by using$$O(n^{\omega(1,1-\beta/2,1-\beta/2)}+n^{1+\beta+o(1)}\log q)$$operations in ${\bf F}_q$, for any $\beta$ from the interval$0\le \beta \le 1$. For $\beta=0.805347$, this bound can be turned into $O(n^{1.80535}\log q)$.\end{theorem} By comparing Theorems 10.5 and 10.6, we obtained that the estimatesof Theorem 10.6 dominates the overall asymptotic complexity ofpolynomial factorization over ${\bf F}_q$ in terms of the numberof the field operations used, although we need randomizationto apply the estimates of Theorem 10.5 and do not need it toapply Theorem 10.6.\\{\bf Proof.} To prove Theorem 10.6, we will first recall and improve Lemmas 3 and 4 of [KS95]. Lemma 3 of [KS95] states: {\itGiven a polynomial $f\in {\bf K}[x]$ of a degree $n$ over an arbitrary field ${\bf K}$ and $k+1$ polynomials$g_1,~g_2,\cdots,~g_k,~h~\in~{\bf K}[x]$, all of degrees less than$n$, where $k=O(n^{\delta}),~0\le \delta\le 1$, it suffices to apply$$O(n^{(\omega+1)/2}k^{(\omega-1)/2})$$operations in ${\bf K}$ to compute}$$g_1(h)~{\rm mod}~f,\cdots,~g_k(h)~{\rm mod}~f~\in~{\bf K}[x]~.$$In the proof of Lemma 3 of [KS95],the latter complexity bound relies on theestimates for the complexity of the problem$<n,\sqrt{nk},\sqrt{nk}>$, for which[KS95] uses the bound $$O(n/\sqrt{nk})M(\sqrt{nk},\sqrt{nk},\sqrt{nk})~.$$ We will replacethis estimate by $M(n,\sqrt{nk},\sqrt{nk})$. As is pointed out in section 8 of Part I, for most of the selections of $k$, our algorithmsfor rectangular matrix multiplication achieve better results thanapplication of square matrix multiplication. Lemma 4 of [KS95] states: {\it Let $f\in {\bf F}_q[x]$ be a polynomial of a degree $n$. Suppose that we are given $x^{q^r}~{\rm mod}~f\in {\bf F}_q[x]$.Then $O(n^{(\omega+1)/2}K^{(\omega-1)/2})$operations in ${\bf F}_q$ suffices to compute$$x^{q^r}~{\rm mod}~f,~x^{q^{2r}}~{\rm mod}~f~,\cdots,           x^{q^{Kr}}~{\rm mod}~f~\in~{\bf F}_q[x]~,$$for $K=O(n^{\delta}),~0\le \delta\le 1$.}For the sake of completeness of our argument, let us outline the short proof of Lemma 4.\noindent{\bf Proof of Lemma 4 of [KS95]}: For $i\ge 1$, let $G_i=x^{q^{ir}}~{\rm mod}~f\in {\bf F}_q[x]$. Assume that we have computed$G_1,\cdots,G_m$. Then we can obtain $G_{m+1},\cdots,G_{2m}$by computing$$G_1(G_m)~{\rm mod}~f,~\cdots~,~G_m(G_m)~{\rm mod}~f$$ by means of the algorithm supporting Lemma 3. Therefore, to compute $G_1,\cdots,G_K$ given $G_1$, we simplyrepeat the above ``doubling'' step $O(\log K)$ times, and thenachieve the stated running-time estimate. The procedure above can be specified in the following waywhere we incorporate our improved version of Lemma 3:Step 1. For a given $G_1$, computing ~~$G_1(G_1)$ mod $f=G_2$~~is equivalentto solving the problem $<n,\sqrt{n},\sqrt{n}>$ (i.e. let $k=1$ in Lemma 3).Step 2. For a given $G_1$ and $G_2$ from step 1, computing$$G_1(G_2)~{\rm mod}~f=G_3~~~{\rm and}~~~G_2(G_2)~{\rm mod}~f=G_4$$is equivalent to solving the problem$<n,\sqrt{2n},\sqrt{2n}>$ (i.e. let $k=2$ in Lemma 3).$\cdots \cdots$Step $\log K-1$. For $G_1,\cdots,G_{K/8}$ from the previous steps,computing$$G_1(G_{K/8})~{\rm mod}~f=G_{1+K/8},~\cdots~,~G_{K/8}(G_{K/8})~{\rm mod}~f=G_{K/4}$$is equivalent to solving the problem$<n,\sqrt{n(K/4)},\sqrt{n(K/4)}>$ (i.e. let $k=K/4$ in Lemma 3).Step $\log K$. For $G_1,\cdots,G_{K/4}$ from the previous steps,computing$$G_1(G_{K/4})~{\rm mod}~f=G_{1+K/4},~\cdots~,~G_{K/4}(G_{K/4})~{\rm mod}~f=G_{K/2}$$is equivalent to solving the problem$<n,\sqrt{n(K/2)},\sqrt{n(K/2)}>$ (i.e. let $k=K/2$ in Lemma 3).We recall that $$M\left(n,\sqrt{n(K/2^{i+1})},\sqrt{n(K/2^{i+1})}\right)\le {1\over 2}M\left(n,\sqrt{n(K/2^i)},\sqrt{n(K/2^i)}\right),~~~i=1,2,\cdots,\log K~.$$Now we sum the complexity estimates for all steps from 1 to $\log K$, to arrive at the overall complexity bound of$$\left({1\over 2^{\log K}}+\cdots+{1\over 2}\right)M\left(n,\sqrt{nK},\sqrt{nK}\right)< M\left(n,\sqrt{nK},\sqrt{nK}\right)~.$$Therefore, we may replace $O(n^{(\omega+1)/2}K^{(\omega-1)/2})$by $M\left(n,\sqrt{nK},\sqrt{nK}\right)$. According to Algorithm D, we have $K=n^{1-\beta}$, which leads tothe result of Theorem 3 of [KS95]. Now, by replacing $K$ by$n^{1-\beta}$ in $M(n,\sqrt{nK},\sqrt{nK})$, we deduce the bound of$$M(n,\sqrt{n^{2-\beta}},\sqrt{n^{2-\beta}})=M(n,n^{1-\beta/2},n^{1-\beta/2})=O(n^{\omega(1,1-\beta/2,1-\beta/2)})~.$$The latter argument enables us to replace the term$$n^{(\omega+1)/2+(1-\beta)(\omega-1)/2}$$ in the estimate of Theorem 3 of [KS95] by$$n^{\omega(1,1-\beta/2,1-\beta/2)}~,$$ so as to yield the bound of$$O(n^{\omega(1,1-\beta/2,1-\beta/2)}+n^{1+\beta+o(1)}\log q)$$on the complexity of the distinct-degree factorization in${\bf F}_q$ ( cf. our Remark 2.1 ).To minimize the exponent of $n$ in the latter bound,we choose $\beta=0.805347$. Furthermore, in Theorem 10.2 of oursubsection 10.2, we choose $b=0.023$ and $l=8$. Then we arrive at the estimate$$\omega(1,1-\beta/2,1-\beta/2)\le 1.805346859\ldots<1.80535~.$$Since $\beta+o(1)$ is bounded from above by 0.80535, we finally arrive at the complexity bound$O(n^{1.80535}\log q)$, thus completing the proof of Theorem 10.6 to yield a new record complexity estimate for the distinct-degree factorization ( and consequently, for the entirefactorization algorithm ).$$\eqno{\Box}$$\subsection{Complexity of the Fast Black Box Berlekamp Algorithm}In this subsection, we will follow the line of section 3 of [KS95]but will utilize the results of our Part I on rectangular matrix multiplication to improve the estimates[KS95] for the complexity of the fast randomized Black Box Berlekamp Algorithm. The latter algorithm is a versionof Berlekamp's algorithm ameliorated in [KS95] for the factorizationof a monic square-free polynomial over the finite field ${\bf F}_q$with $q$ elements. By following [KS95], we will refer to thisalgorithm as {\it Algorithm B}.First, let us recall the result of Theorem 4 of [KS95], which states that {\it for any constant $\beta$ with $0\le \beta\le 1$, Algorithm B of [KS95]can be implemented so as to use an expected number of$$O(n^{(\omega+1)/2+(3-\omega)|\beta-1/2|+o(1)}+n^{(\omega+1)/2+(1-\beta)+o(1)}+n^{1+\beta+o(1)}\log q)\eqno(10.7.1)$$operations in ${\bf F}_q$. By choosing $\omega<2.375477$ andminimizing the exponent $n$, one obtains the bound of$$O(n^{1.880}+n^{1.808}\log q)$$operations in ${\bf F}_q$}. We will next improve the latter bound to yield$$O(\min \{n^{1.860}+n^{1.808}\log q,n^{1.8335}\log q\}),$$then we will also improve a refined estimate of [KS95] forthe complexity of Algorithm B.Note first that the term $O(n^{1.880}+n^{1.808}\log q)$ is obtained bychoosing $\beta=0.808$ in (10.7.1); also note that $n^{(\omega+1)/2}$comes from the complexity bound for the problem of modular polynomialcomposition, which we bound by$O(n^{3.334/2})=O(n^{1.667})$, due to our Theorems 10.1 and 10.4.Then, we will bound the exponents of the first and the second termsby $1.8591\ldots$ and of the third term by 1.808, that is, we havethe overall complexity bound of $O(n^{1.860}+n^{1.808}\log q)$. To yield the estimate $O(n^{1.8335}\log q)$, we first note that $(\omega+1)/2$ inthe second term of (10.7.1) can be replaced by $\omega(1,1,2)<3.333953$, then optimize the exponent of $n$by choosing an appropriate $\beta$, to bound the sum by $O(n^{1.8335}\log q)$, and then, finally,prove that the exponent of the first term can also be decreased to $1.8335$. Towards the latter goal, let us follow the proof ofTheorem 4 of [KS95] so as to cover Step AE2 of Algorithm AE and the calculation ofits complexity. The bound $$O(n^{(\omega+1)/2+(3-\omega)|\beta-1/2|+o(1)})$$ comes fromthe complexity estimate for rectangular matrix multiplication problem$<m,t,n>$, where $m=n^{1-\beta}$ and $t=n^{\beta}$, or conversely, $t=n^{1-\beta}$ and $m=n^{\beta}$, that is,$$O(n^{(\omega+1)/2+(3-\omega)|\beta-1/2|+o(1)})$$ comes from the bound$$M(n^{1-\beta},n^{\beta},n)=O(n^{\omega(1-\beta,\beta,1)})~.$$ For $\beta=0.8335-o(1)$, among $1-\beta,~\beta$, and 1, the value $1-\beta=0.1665+O(1)$ is the smallest, 1 is the largest, and $(1-\beta)/\beta<0.294$.By applying our Theorem 10.3, we obtain$$\omega(1-\beta,\beta,1)=1+\beta+o(1)=1.8335~.$$Therefore, we achieve $O(n^{1.8335}\log q)$, thus improving Theorem 4 of [KS95].Theorem 4 is also improved by Theorem 5 of [KS95], which gives usthe record randomized complexity estimate for factorization over${\bf F}_q$ by the Fast Black Box Berlekamp Algorithm.Our results of Part I will enable us to improve the estimates of Theorem 5 of [KS95] too.Theorem 5 of [KS95] states: {\it For any constant $\beta$ with $0\le \beta\le 1$, Algorithm Bcan be implemented so as to use an expected number of$$O(n^{(\omega+1)/2+(3-\omega)|\beta-1/2|+o(1)}+n^{(\omega+1)/2+(1-\beta)(\omega-1)/2+o(1)}+n^{1+\beta+o(1)}\log q)\eqno(10.7.2)$$operations in ${\bf F}_q$. In particular, by choosing $\omega<2.375477$ andminimizing the exponent of $n$, one obtains the bound of$$O(n^{1.852}+n^{1.763}\log q)$$operations in ${\bf F}_q$. Furthermore, for $\omega=2.375477$, by making use of the techniques for fast rectangular matrix multiplication, the estimate (10.7.2) can be reduced to$$O(n^{(\omega+1)/2+(1-\beta)(\omega-1)/2+o(1)}+n^{1+\beta+o(1)}\log q)~\eqno(10.7.3)$$and, in particular, to $O(n^{1.815}\log q)$ for an appropriatechoice of $\beta$.}We will next prove the record estimates for the asymptotic complexity of polynomial factorization over ${\bf F}_q$ based on Algorithm B.\noindent\begin{theorem}The bounds $O(n^{1.852}+n^{1.763}\log q)$ and $O(n^{1.815}\log q)$on the complexity of the $n$-th degree polynomial factorization over ${\bf F}_q$ based on Algorithm B of [KS95] can be improved to yield $O(n^{1.8356}+n^{1.763}\log q)$ and $O(n^{1.80535}\log q)$, respectively.\end{theorem}{\bf Proof.}Note that the second term of (10.7.2),$$O(n^{(\omega+1)/2+(1-\beta)(\omega-1)/2+o(1)})~,$$ comes from the solution of the problem $<n,n^{1-\beta/2},n^{1-\beta/2}>$ ( cf. our Theorem 10.4 )and thus can be replaced by$$M(n,n^{1-\beta/2},n^{1-\beta/2})=O(n^{\omega(1,1-\beta/2,1-\beta/2)})~$$ (as in the preceding sectionwhere we improved the result of Theorem 3 of [KS95]).By choosing again $b=0.023$ and$l=8$ in Theorem 10.2 of subsection 10.2 ( as we did at the end of subsection 10.6 ) but choosing $\beta=0.763-o(1)$, we arrive at the bound$$\omega(1,1-\beta/2,1-\beta/2)\le 1.835532965\cdots~.$$In the proof of Theorem 5 of [KS95],  $$O(n^{(\omega+1)/2+(1-\beta)(\omega-1)/2+o(1)})$$ is an upper bound on $M(n^{1-\beta},n,n^{\beta})$.For $\beta=0.763-o(1)$, we have$$\begin{array}{l}~~~M(n^{1-\beta},n,n^{\beta})\\=M(n^{0.237+o(1)},n,n^{0.763-o(1)})\\=n^{0.013}M(n^{0.224+o(1)},n,n^{0.763-o(1)})\\=n^{0.013}O(n^{\omega(0.224+o(1),1,0.763-o(1))})~.\end{array}$$On the other hand, $$(0.224+o(1))/(0.763-o(1))\le 0.294$$ (compare the first term of (5.1) in Theorem 4 of [KS95]). Consequently, by applyingTheorem 10.3 of subsection 10.2, we deduce that$$\omega(0.224+o(1),1,0.763-o(1))=1+0.763-o(1)\le 1.763~.$$Therefore, the expression$$n^{0.013}O(n^{\omega(0.224+o(1),1,0.763-o(1))})=O(n^{0.013+1.763})=O(n^{1.776})$$bounds the first term, and the latter bound is dominated by the second term.This enables us to improve the estimate $O(n^{1.852}+n^{1.763}\log q)$ to $O(n^{1.8356}+n^{1.763}\log q)$. Finally, we discuss the improvement from $O(n^{1.815}\log q)$ to $O(n^{1.80535}\log q)$. Since the second and the third terms of Theorem 5 of [KS95] [cf. (10.7.2)] are the same as in the Theorem 3 of [KS95], that is, bounded by$O(n^{1.80535}\log q)$, it remains to prove that the first termis dominated by $O(n^{1.80535})$. Choose $\beta=0.80535-o(1)$ and note that (as we mentioned above) the first term comes from the bound$$\begin{array}{l}~~~M(n^{1-\beta},n,n^{\beta})\\=M(n^{0.19465+o(1)},n,n^{0.80535-o(1)})\\=O(n^{\omega(0.19465+o(1),1,0.80535-o(1))}\\=O(n^{1.80535})~.\end{array}$$Now, due to the inequality $$(0.19465+o(1))/(0.80535-o(1))\le 0.294$$ and the applicationof our Theorem 10.3, we arrive at the desired boundof $O(n^{1.80535}\log q)$, thus proving Theorem 10.7.$$\eqno{\Box}$$\section{Application to Finding Basic Solutions of a Linear Programming Problem}In this section, we will apply the results on rectangularmatrix multiplications from section 8 to find basic solutionsof a linear programmingproblem with $m$ constraints and $n$ variables and improve its  record complexity estimate from  $O(m^{1.594})$ to $O(m^{1.575})$.First, let us follow [BM98] and briefly describe the problem.\noindent{\bf Problem 11.1 (Basis Crashing for a Linear Programming Problem):} {\it Consider the standard-form system of linear constraints:$$A~x=~b,~~~x\ge 0~~,$$where $A\in {\bf R}^{m\times n}$ is assumed to have $m$ linearly independent rows, $b\in {\bf R}^m$, and $x\in {\bf R}^n$, ${\bf R}$ denoting the field of real numbers. A solution $x$ of this system is said to be {\bf basic} if the set of columns $A_{\cdot j}$ with$x_j\ne 0$ is linearly independent. Thus, a basic solution hasat most $m$ positive components.} The problem of finding a basicsolution given a non-basic one arises frequently in linearprogramming, especially in the context of interior-pointmethods. For simplicity, we call this problem {\it basis crashing}.P.A. Beling and N. Megiddo in [BM98] reduced this problem toperforming rectangular matrix multiplication and proved thefollowing estimate.\noindent\begin{theorem} [BM98]. Problem 11.1 can be solved by using$$O((m^{1+2t}+m^{\omega(1,1,t)})n/m^t)=O((m^{1+t}+m^{\omega(1,1,t)-t})n)~~\eqno(11.1)$$arithmetic operations, for any $t$ in the interval $0\le t\le 1$.\end{theorem}To minimize (11.1), we seek $t$, $0\le t\le 1$, that minimizes$$\max\{1+t,\omega(1,1,t)-t\}~.$$ Substitute (8.1) and rewrite this expression as$$\max\{1+t,{2(1-t)+(t-\alpha)\omega \over 1-\alpha}-t\}~,\eqno(11.2)$$where $\omega=2.376$ and$\alpha=0.294$. The minimum is reached for$t=0.5747\ldots<0.575$, which implies the following estimate.\begin{theorem}The complexity of Problem 11.1 of computing basis solutions tothe linear programming problem with $m$ constraints and $n$variables is $O(m^{1.575}n)$.\end{theorem}\noindent{\bf Remark 11.1} In [BM98] the estimate similar to (11.2) was obtained, but for some reason, a slightly larger numerical valueof the exponent of $m$ (namely, 1.594) was deduced.\begin{thebibliography}{BCLR}\bibitem[B70]{B70} E.R. Berlekamp,Factoring Polynomials over Large Finite Fields,{\it Math. of Computation}, {\bf 24}, 713-735, 1970.\bibitem[BCLR]{BCLR} D. Bini, M. Capovani, G. Lotti and F. Romani,$O(n^{2.7799})$ complexity for matrix multiplication,{\it Inform. Process. Lett.}, {\bf 8}, 234-235, 1979.\bibitem[BD76]{BD76} R. W. Brockett and D. Dobkin, On the Number of Multiplications Required for Matrix Multiplications,{\it SIAM J. on Complexity}, {\bf 5}, 4, 624-628, 1976.\bibitem[Be46]{Be46} F. A. Behrend,On Sets of Integers Which Contain No Three Terms in ArithmeticalProgression,{\it Proc. Nat. Acad. Sci. USA}, {\bf 32}, 331-332, 1946.\bibitem[BK78]{BK78} R. P. Brent and H. T. Kung,Fast Algorithms for Manipulating Formal Power Series,{\it J. ACM}, {\bf 25}, 4, 581-595, 1978.\bibitem[BM75]{BM75} A. Borodin and I. Munro,{\it The Computational Complexity of Algebraic and Numeric Problems},American Elsevier, New York, 1975.\bibitem[BM98]{BM98} P.A. Beling and N. Megiddo,Using Fast Matrix Multiplication to Find Basic Solutions,{\it Theoretical Computer Science}, 1998 ( to appear ).\bibitem[BP94]{BP94} D. Bini and V. Y. Pan,{\it Polynomial and Matrix Computations, Vol.1: FundamentalAlgorithms}, Birkh\"{a}user, Boston, 1994.\bibitem[Co82]{Co82} D. Coppersmith,Rapid Multiplication of Rectangular Matrices,{\it SIAM J. Comput.}, {\bf 11}, 3, 467-471, 1982.\bibitem[Co97]{Co97} D. Coppersmith, Rectangular Matrix Multiplication Revisited,{\it J. of Complexity}, 13, 1997.\bibitem[CW82]{CW82} D. Coppersmith and S. Winograd,On the Aysmptotic Complexity of Matrix Multiplication,{\it SIAM J. Comput.}, {\bf 11}, 3, 472-492, 1982.\bibitem[CW90]{CW90} D. Coppersmith and S. Winograd,Matrix Multiplication via Arithmetic Progressions,{\it J. Symb. Comp.}, {\bf 9}, 251-280, 1990.\bibitem[CZ81]{CZ81} D.G. Cantor and H. Zassenhaus,A New Algorithm for Factoring Polynomials over Finite Fields,{\it Math. of Computation}, {\bf 36}, 587-592, 1981.\bibitem[EG88]{EG88} D. Eppstein and Z. Galil, Parallel Algorithmic Techniques for Combinatorial Computation,{\it Annual Review of Computer Science}, {\bf 3}, 233-283, 1988.\bibitem[GP89]{GP89} Z. Galil and V. Y. Pan,Parallel Evaluation of the Determinant and of the Inverse of a Matrix,{\it Information Proc. Letters}, {\bf 30}, 41-45, 1989.\bibitem[GS92]{GS92} J. von zur Gathen and V. Shoup,Computing Frobenius Maps and Factoring Polynomials,{\it Comput. Complexity}, {\bf 2}, 187-224, 1992.\bibitem[KR90]{KR90} R. Karp and V. Ramachandran,A Survey of Parallel Algorithms for Shared Memory Machines,{\it Handbook for Theoretical Computer Science} ( J. van Leeuwen Editor ), 869-941, North Holland, Amsterdam, 1990.\bibitem[KS95]{KS95} E. Kaltofen and V. Shoup,Subquadratic-Time Factoring of Polynomials over Finite Fields,{\it Proc. 27th Annual ACM Symp. Theory Comp.}, 398-406, ACM Press, New York, and {\it Math. Comput.}, in press.\bibitem[Pan72]{Pan72} V. Y. Pan,On Schemes for the Computation of Products and Inverse of Matrices,{\it Uspekhi Mat. Nauk}, 27, 5, 249-250, 1972. (In Russian.)\bibitem[Pan]{Pan} V. Y. Pan,{\it How to Multiply Matrices Faster},Lecture Notes in Computer Science, {\bf 179}, Springer, Berlin, 1984.\bibitem[Pan,a]{Pan,a} V. Y. Pan,How Can We Speed-up Matrix Multiplication ?,{\it SIAM Rewiew}, {\bf 26}, 3, 393-415, 1984.\bibitem[Sc81]{Sc81} A. Sch\"{o}nhage,Partial and Total Matrix Multiplication,{\it SIAM J. Comput.}, {\bf 10}, 3, 434-456, 1981.\bibitem[SS42]{SS42} R. Salem and D. C. Spencer,On Sets of Integers Which Contain No Three Terms in ArithmeticalProgression,{\it Proc. Nat. Acad. Sci. USA}, {\bf 28}, 561-563, 1942.%\bibitem[Be46]{Be46} F. A. Behrend,%On Sets of Integers Which Contain No Three Terms in Arithmetical%Progression.''%{\it Proc. Nat. Acad. Sci. USA}, {\bf 32}, 331-332, 1946.\bibitem[St69]{St69} V. Strassen,Gaussian Elimination Is Not Optimal,{\it Numerische Math.}, {\bf 13}, 354-356, 1969.%\bibitem[St81]{St81} V. Strassen,\bibitem[St86]{St86} V. Strassen,%Relative Bilinear Complexity and Matrix Multiplication,%{\it Preprint} (1986). See also, The Asymptotic Spectrum of Tensors and the Exponentof Matrix Multiplication,{\it Proc. 27th Ann. IEEE Symp. on Foundations of Computer Science},49-54, 1986.\bibitem[St87]{St87} V. Strassen, Relative Bilinear Complexity and Matrix Multiplication,{\it J. reine angew. Math.}, {\bf 375/376}, 406-443, 1987.\bibitem[St88]{St88} V. Strassen, The Asymptotic Spectrum of Tensor,{\it J. reine angew. Math.}, {\bf 384}, 102-152, 1988.\end{thebibliography}\end{document}