[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Fast rectangular matrix multiplication and some applications

  • Published:
Science in China Series A: Mathematics Aims and scope Submit manuscript

Abstract

We study asymptotically fast multiplication algorithms for matrix pairs of arbitrary dimensions, and optimize the exponents of their arithmetic complexity bounds. For a large class of input matrix pairs, we improve the known exponents. We also show some applications of our results: (i) we decrease from O(n 2 + n 1+o(1)logq) to O(n 1.9998 + n 1+o(1)logq) the known arithmetic complexity bound for the univariate polynomial factorization of degree n over a finite field with q elements; (ii) we decrease from 2.837 to 2.7945 the known exponent of the work and arithmetic processor bounds for fast deterministic (NC) parallel evaluation of the determinant, the characteristic polynomial, and the inverse of an n × n matrix, as well as for the solution to a nonsingular linear system of n equations; (iii) we decrease from O(m 1.575 n) to O(m 1.5356 n) the known bound for computing basic solutions to a linear programming problem with m constraints and n variables.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Coppersmith D, Winograd S. Matrix multiplication via arithmetic progressions. J Symb Comp, 9(3): 251–280 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  2. Huang X H, Pan V Y. Fast rectangular matrix multiplication and applications. J Complexity, 14: 257–299 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  3. Kaporin I. A practical algorithm for faster matrix multiplication. Numer Linear Algebra Appl, 6: 687–700 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  4. Dumas J G, Gautier T, Pernet C. Finite field linear algebra subroutines. In: Proc of the 2002 International Symposium on Symbolic and Algebraic Computation. New York: ACM Press, 2002, 63–74

    Chapter  Google Scholar 

  5. Kaporin I. The aggregation and cancellation techniques as a practical tool for faster matrix multiplication. Theor Comput Sci, 315(2–3): 469–510 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  6. Pan V Y. How can we speed up matrix multiplication. SIAM Rev, 26(3): 393–415 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  7. Bini D, Capovani M, Lotti G, et al. O(n 2.7799) complexity for matrix multiplication. Inform Proce Lett, 8: 234–235 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  8. Bürgisser P, Clausen M, Shokrollahi M A. Algebraic Complexity Theory. Berlin: Springer, 1997, 371–449

    MATH  Google Scholar 

  9. Coppersmith D. Rectangular matrix multiplication revisited. J Complexity, 13: 42–49 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  10. Schönhage A. Partial and total multiplication. SIAM J Comput, 10: 434–455 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  11. Pan V Y. Computation scheme for a product of matrices and for the inverse matrix(in Russian). Uspekhi Mat Nauk, 27(5): 249–250 (1972)

    MATH  Google Scholar 

  12. Salem R, Spencer D C. On sets of integers which contain no three terms in arithmetical progression. Proc Nat Acad Sci USA, 28(12): 561–563 (1942)

    Article  MATH  MathSciNet  Google Scholar 

  13. Kaltofen E, Shoup V. Subquadratic-time factoring of polynomials over finite fields. Math Comput, 67(223):1179–1197 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  14. Gathen J von zur, Shoup V. Computing frobenius maps and factoring polynomials. Comput Complexity, 2: 187–224 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  15. Eppstein D, Galil Z. Parallel algorithmic techniques for combinatorial computation. Annual Rev Comput Sci, 3: 233–283 (1988)

    Article  MathSciNet  Google Scholar 

  16. Karp R, Ramachandran V. A survey of parallel algorithms for shared memory machines. In: Leeuwen J van, ed. Handbook of Theoretical Computer Science. North-Holland: Elsevier Science, 1990, 869–941

    Google Scholar 

  17. Galil Z, Pan V Y. Parallel evaluation of the determinant and of the inverse of a matrix. Infor Proc Lett, 30: 41–45 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  18. Beling P A, Megiddo N. Using fast matrix multiplication to find basic solutions. Theoret Comput Sci, 205(1): 307–316 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  19. Coppersmith D. Rapid multiplication of rectangular matrices. SIAM J Comput, 11(3): 467–471 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  20. Coppersmith D, Winograd S. On the asymptotic complexity of matrix multiplication. SIAM J Comput, 11(3): 472–492 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  21. Pan V Y. Strassen’s algorithm is not optimal: Trilinear technique of aggregating, uniting and canceling for constructing fast algorithms for matrix multiplication. In: Proc of 19th Annual Symposium on the Foundations of Computer Science. Ann Arbor: IEEE Computer Society Press, 1978, 166–176

    Google Scholar 

  22. Kaltofen E, Shoup V. Fast polynomial factorization over high algebraic extensions of finite fields. In: Wolfgang W K, eds. In: Proc 1997 Int Symp Symb Algeb Comp ISSAC’97. Maui HI: ACM Press, 1997, 184–188

    Chapter  Google Scholar 

  23. Gathen J von zur, Gerhard J. Modern Computer Algebra. Cambridge: Cambridge University Press, 1999

    MATH  Google Scholar 

  24. Gathen J von zur, Panario D. Factoring polynomials over finite fields: a survey. J Symb Comput, 31: 3–17 (2001)

    Article  MATH  Google Scholar 

  25. Niederreiter H. Factorization of polynomials and some linear algebra problems over finite fields. Linear Algebr Appl, 192: 301–328 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  26. Niederreiter H, Göttfert R. On a new factorization algorithm for polynomials over finite fields. Math Comput, 64: 347–353 (1995)

    Article  MATH  Google Scholar 

  27. Strassen V. Algebra and complexity. In: Proceedings of the first European Congress of Mathematics. Paris: Birkhüser Verlag, 1994, 429–446

    Google Scholar 

  28. Naudin P, Quitté C. Univariate polynomial factorization over finite fields. Theor Comp Sci, 191: 1–36 (1998)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Applied Mathematics, Institute of Information Engineering, Information Engineering University, Zhengzhou, 450002, China

    Ke ShanXue, Zeng BenSheng & Han WenBao

  2. Department of Mathematics and Computer Science, Lehman College, City University of New York, Bronx, New York, 10468, USA

    Victor Y. Pan

Authors
  1. Ke ShanXue
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zeng BenSheng
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Han WenBao
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Victor Y. Pan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ke ShanXue.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ke, S., Zeng, B., Han, W. et al. Fast rectangular matrix multiplication and some applications. Sci. China Ser. A-Math. 51, 389–406 (2008). https://doi.org/10.1007/s11425-007-0169-2

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11425-007-0169-2

Keywords

MSC(2000)

Search

Navigation