The algorithmic complexity of linear algebras

• D. Bini, M. Capovani, G. Lotti and F. Romani 1979, O(n^2.7799) complexity for matrix multiplication. Information Proc. Letters 8, pp. 234–235.

  Google Scholar 

• D. Bini 1979, Relations between EC-algorithms and APA-algorithms, applications. Nota interna B79/8 (March 1979) I.E.I. Pisa.

  Google Scholar 

• A. Borodin and I. Munro 1975, The Computational Complexity of Algebraic and Numeric Problems. American Elsevier.

  Google Scholar 

• R.W. Brockett and D. Dobkin 1978, On the optimal evaluation of a set of bilinear forms. Linear Algebra and its Applications 19, pp. 207–235.

  Article  Google Scholar 

• D. Dobkin 1973, On the arithmetic complexity of a class of arithmetic computations. Thesis, Harvard University.

  Google Scholar 

• C.M. Fiduccia and I. Zalcstein 1977, Algebras having linear multiplicative complexity. Journal of the ACM 24, pp. 311–331.

  Article  Google Scholar 

• H.F. de Groote 1978, On varieties of optimal algorithms for the computation of bilinear mappings II. Optimal algorithms for 2×2-matrix multiplication. Theoretical Computer Science 7, pp. 127–148.

  Article  Google Scholar 

• J. Hopcroft and L. Kerr 1971, On minimizing the number of multiplications necessary for matrix multiplication. SIAM J. Applied Math. 20. pp. 30–36.

  Article  Google Scholar 

• T.D. Howell and J.C. Lafon 1975, The complexity of the quaternion product. Cornell University TR 75–245.

  Google Scholar 

• J.C. Lafon and S. Winograd 1980, to appear.

  Google Scholar 

• A.M. Ostrowski 1954, On two problems in abstract algebra connected with Horner's rule. Studies presented to R. von Mises, Academic Press, New York, pp. 40–48.

  Google Scholar 

• V. Ya. Pan 1978, Strassen's algorithm is not optimal. Proc. 19th Ann. Symp. on Foundations of Computer Science, pp. 166–176.

  Google Scholar 

• V. Ya. Pan 1980, New Fast Algorithms for Matrix Operations. SIAM J. on Computing, 9/2, pp. 321–342.

  Article  Google Scholar 

• V. Ya. Pan 1979, Field Extension and Trilinear Aggregating, Uniting and Cancelling for the Acceleration of Matrix Multiplication, Proc. 20th Ann. Symp. on Foundations of Computer Science, pp. 28–38.

  Google Scholar 

• V.Ya. Pan 1980, New Combination of Methods for the Acceleration of Matrix Multiplication. Preprint, State University of New York at Albany.

  Google Scholar 

• A. Schönhage 1979, Partial and Total Matrix Multiplication. TR, Mathematisches Institut der Universität Tübingen, June 1979.

  Google Scholar 

• A. Schönhage 1980, Partial and Total Matrix Multiplication. TR, Math. Inst. Univ. Tübingen (January 1980). To appear.

  Google Scholar 

• H.J. Stoss 1979, Private communication.

  Google Scholar 

• V. Strassen 1969, Gaussian Elimination is not Optimal. Numer. Math. 13, pp. 354–356.

  Google Scholar 

• V. Strassen 1973, Vermeidung von Divisionen. J. für reine und angew. Mathematik 264, pp. 184–202.

  Google Scholar 

• S. Winograd 1971, On multiplication of 2×2 matrices. Linear Algebra Appl. 4, pp. 381–388.

  Article  Google Scholar 

• S. Winograd 1977, Some bilinear forms whose multiplicative complexity depends on the field of constants. Math. Systems Theory 10, pp. 169–180.

  Article  Google Scholar 

Download references