Coppersmith–Winograd algorithm


Coppersmith–Winograd algorithm

In the mathematical discipline of linear algebra, the Coppersmith–Winograd algorithm, named after Don Coppersmith and Shmuel Winograd, is the asymptotically fastest known algorithm for square matrix multiplication as of 2008. It can multiply two n \times n matrices in O(n2.376) time (see Big O notation). This is an improvement over the trivial O(n3) time algorithm and the O(n2.807) time Strassen algorithm. It might be possible to improve the exponent further; however, the exponent must be at least 2 (because an n \times n matrix has n2 values, and all of them have to be read at least once to calculate the exact result).

The Coppersmith–Winograd algorithm is frequently used as a building block in other algorithms to prove theoretical time bounds. However, unlike the Strassen algorithm, it is not used in practice because it only provides an advantage for matrices so large that they cannot be processed by modern hardware.[1]

Henry Cohn, Robert Kleinberg, Balázs Szegedy and Christopher Umans have rederived the Coppersmith–Winograd algorithm using a group-theoretic construction. They also show that either of two different conjectures would imply that the optimal exponent of matrix multiplication is 2, as has long been suspected. [2]

References

  1. ^ Robinson, Sara (2005), "Toward an Optimal Algorithm for Matrix Multiplication", SIAM News 38 (9), http://www.siam.org/pdf/news/174.pdf 
  2. ^ Cohn, H.; Kleinberg, R.; Szegedy, B.; Umans, C. (2005). "Group-theoretic Algorithms for Matrix Multiplication". 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05). pp. 379. doi:10.1109/SFCS.2005.39. ISBN 0-7695-2468-0.  edit

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Winograd — is a surname and may refer to: * Arthur Winograd, the original cello player for the Juilliard String Quartet * Shmuel Winograd, known for the Coppersmith–Winograd algorithm * Terry Winograd, computer scientist * Eliyahu Winograd, chairman of the… …   Wikipedia

  • Strassen algorithm — In the mathematical discipline of linear algebra, the Strassen algorithm, named after Volker Strassen, is an algorithm used for matrix multiplication. It is asymptotically faster than the standard matrix multiplication algorithm, but slower than… …   Wikipedia

  • CYK algorithm — The Cocke–Younger–Kasami (CYK) algorithm (alternatively called CKY) is a parsing algorithm for context free grammars. It employs bottom up parsing and dynamic programming. The standard version of CYK operates only on context free grammars given… …   Wikipedia

  • Shmuel Winograd — is a computer scientist, noted for his work on fast algorithms for arithmetic, and in particular for the algorithm known as the Coppersmith Winograd algorithm and for his FFT algorithm. From 1970 1974 and 1980 1994 he was the director of the… …   Wikipedia

  • Don Coppersmith — is a cryptographer and mathematician. He was involved in the design of the Data Encryption Standard block cipher at IBM, particularly the design of the S boxes, strengthening them against differential cryptanalysis.[1] He has also worked on… …   Wikipedia

  • Freivald's algorithm — is a randomized algorithm used to verify matrix multiplication. Given three n x n matrices A , B , and C , a general problem is to verify whether A x B = C . A naïve algorithm would compute the product A x B explicitly and compare term by term… …   Wikipedia

  • Matrix multiplication — In mathematics, matrix multiplication is a binary operation that takes a pair of matrices, and produces another matrix. If A is an n by m matrix and B is an m by p matrix, the result AB of their multiplication is an n by p matrix defined only if… …   Wikipedia

  • Computational complexity of mathematical operations — The following tables list the running time of various algorithms for common mathematical operations. Here, complexity refers to the time complexity of performing computations on a multitape Turing machine.[1] See big O notation for an explanation …   Wikipedia

  • Strassen-Algorithmus — Der Strassen Algorithmus (benannt nach dem deutschen Mathematiker Volker Strassen) ist ein Algorithmus aus der Linearen Algebra und wird zur Matrizenmultiplikation verwendet. Der Strassen Algorithmus realisiert die Matrizenmultiplikation… …   Deutsch Wikipedia

  • List of computer scientists — Expand list|date=August 2008This is a list of well known computer scientists, people who do work in computer science, in particular researchers and authors.Some persons notable as programmers are included here because they work in research as… …   Wikipedia


We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.