作者：
Pan, V. Ya.CUNY
Dept Math & Comp Sci Lehman Coll Bronx NY 10468 USA CUNY
Grad Ctr New York NY 10036 USA
Matrix multiplication is among the most fundamental operations of modern computations. By 1969 it was still commonly believed that the classical algorithm was optimal, although the experts already knew that this was n...
详细信息
Matrix multiplication is among the most fundamental operations of modern computations. By 1969 it was still commonly believed that the classical algorithm was optimal, although the experts already knew that this was not so. Worldwide interest in matrix multiplication instantly exploded in 1969, when Strassen decreased the exponent 3 of cubic time to 2.807. Then everyone expected to see matrix multiplication performed in quadratic or nearly quadratic time very soon. Further progress, however, turned out to be capricious. It was at stalemate for almost a decade, then a combination of surprising techniques (completely independent of Strassen's original ones and much more advanced) enabled a new decrease of the exponent in 1978-1981 and then again in 1986, to 2.376. By 2017 the exponent has still not passed through the barrier of 2.373, but most disturbing was the curse of recursion-even the decrease of exponents below 2.7733 required numerous recursive steps, and each of them squared the problem size. As a result, all algorithms supporting such exponents supersede the classical algorithm only for inputs of immense sizes, far beyond any potential interest for the user. We survey the long study of fast matrix multiplication, focusing on neglected algorithms for feasible matrix multiplication. We comment on their design, the techniques involved, implementation issues, the impact of their study on the modern theory and practice of Algebraic Computations, and perspectives for fast matrix multiplication. Bibliography: 163 titles.
It is shown that the approximate bilinear complexity of multiplying matrices of the order 2 × 2 by a matrix of the order 2 × 6 does not exceed 19. An approximate bilinear algorithm of complexity 19 is presen...
详细信息
Let mu(q2)(n, k)denote the minimum number of multiplications required to compute the coefficients of the product of two degree nk - 1 polynomials modulo the kth power of an irreducible polynomial of degree n over the ...
详细信息
Let mu(q2)(n, k)denote the minimum number of multiplications required to compute the coefficients of the product of two degree nk - 1 polynomials modulo the kth power of an irreducible polynomial of degree n over the q(2) element field F-q2. It is shown that for all odd q and all n = 1,2,..., lim inf(k ->infinity) mu(q2)(n, k)/kn <= 2(1 + 1/q - 2). For the proof of this upper bound, we show that for an odd prime power q, all algebraic function fields in the Garcia-Stichtenoth tower F-q2 over have places of all degrees and apply a Chudnovsky like algorithm for multiplication of polynomials modulo a power of an irreducible polynomial.
First we study asymptotically fast algorithms for rectangular matrix multiplication. We begin with new algorithms for multiplication of an n x n matrix by an n x n(2) matrix in arithmetic time O(n(omega)), omega = 3.3...
详细信息
First we study asymptotically fast algorithms for rectangular matrix multiplication. We begin with new algorithms for multiplication of an n x n matrix by an n x n(2) matrix in arithmetic time O(n(omega)), omega = 3.333953..., which is less by 0.041 than the previous record 3.375477.... Then we present fast multiplication algorithms for matrix pairs of arbitrary dimensions, estimate the asymptotic running 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 known exponents. Finally we show three applications of our results: (a) we decrease from 2.851 to 2.837 the known exponent of *** bounds for fast deterministic (NC) parallel evaluation of the determinant, the characteristic polynomial, and the inverse of an n x n matrix, as well as for the solution to a nonsingular linear system of n equations, (b) we asymptotically accelerate the known sequential algorithms for the univariate polynomial composition mod x(n), yielding the complexity bound O(n(1.667)) versus the old record of O(n(1.688)), and for the univariate polynomial factorization over a finite field, and (c) we improve slightly the known complexity estimates for computing basic solutions to the linear programming problem with n constraints and n variables. (C) 1998 Academic Press.
Until very recently, the lower bounds on the additive complexity of intensively studied linear and bilinear arithmetic algorithms for arithmetic computational problems have relied on the active operation-basic substit...
详细信息
Until very recently, the lower bounds on the additive complexity of intensively studied linear and bilinear arithmetic algorithms for arithmetic computational problems have relied on the active operation-basic substitution argument. Consequently, these bounds have not exceeded the dimension of the problems that is the total number of input variables and outputs. Another approach to the problem follows from the method presented by J. Morgenstern. A third approach reduces the problem to the study of a strong regularity of matrices. Mathematical notation.
A graph-theoretic model is introduced for bilinear algorithms. This facilitates in particular the investigation of the additive complexity of matrix multiplication. The number of additions/subtractions required for ea...
详细信息
A graph-theoretic model is introduced for bilinear algorithms. This facilitates in particular the investigation of the additive complexity of matrix multiplication. The number of additions/subtractions required for each of the problems defined by symmetric permutations on the dimensions of the matrices are shown to differ conversely as the size of each product matrix. It is noted that this result holds for any system of dual problems, not only dual matrix multiplication problems. This additive symmetry is employed to obtain various results, including the fact that 15 additive operations are necessary and sufficient to multiply two $2 \times 2$ matrices by a bilinear algorithm using at most 7 multiplication operations.
暂无评论