Matrix Algebra
The following complexity figures assume that arithmetic with individual elements has complexity O(1), as is the case with fixed-precision floating-point arithmetic.
| Operation | Input | Output | Algorithm | Complexity |
|---|---|---|---|---|
| Matrix multiplication | Two n×n matrices | One n×n matrix | Schoolbook matrix multiplication | O(n3) |
| Strassen algorithm | O(n2.807) | |||
| Coppersmith–Winograd algorithm | O(n2.376) | |||
| Williams algorithm | O(n2.373) | |||
| Matrix multiplication | One n×m matrix &
one m×p matrix |
One n×p matrix | Schoolbook matrix multiplication | O(nmp) |
| Matrix inversion* | One n×n matrix | One n×n matrix | Gauss–Jordan elimination | O(n3) |
| Strassen algorithm | O(n2.807) | |||
| Coppersmith–Winograd algorithm | O(n2.376) | |||
| Williams algorithm | O(n2.373) | |||
| Determinant | One n×n matrix | One number | Laplace expansion | O(n!) |
| LU decomposition | O(n3) | |||
| Bareiss algorithm | O(n3) | |||
| Fast matrix multiplication | O(n2.373) | |||
| Back Substitution | Triangular matrix | n solutions | Back substitution | O(n2) |
In 2005, Henry Cohn, Robert Kleinberg, Balázs Szegedy and Christopher Umans showed that either of two different conjectures would imply that the exponent of matrix multiplication is 2. It has also been conjectured that no fastest algorithm for matrix multiplication exists, in light of the nearly 20 successive improvements leading to the Williams algorithm.
^* Because of the possibility to blockwise invert a matrix, where an inversion of an n×n matrix requires inversion of two half-sized matrices and 6 multiplications between two half-sized matrices, and since matrix multiplication has a lower bound of Ω(n2 log n) operations, it can be shown that a divide and conquer algorithm that uses blockwise inversion to invert a matrix runs with the same time complexity as the matrix multiplication algorithm that is used internally.
Read more about this topic: Computational Complexity Of Mathematical Operations
Famous quotes containing the words matrix and/or algebra:
“As all historians know, the past is a great darkness, and filled with echoes. Voices may reach us from it; but what they say to us is imbued with the obscurity of the matrix out of which they come; and try as we may, we cannot always decipher them precisely in the clearer light of our day.”
—Margaret Atwood (b. 1939)
“Poetry has become the higher algebra of metaphors.”
—José Ortega Y Gasset (1883–1955)