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:
““The matrix is God?”
“In a manner of speaking, although it would be more accurate ... to say that the matrix has a God, since this being’s omniscience and omnipotence are assumed to be limited to the matrix.”
“If it has limits, it isn’t omnipotent.”
“Exactly.... Cyberspace exists, insofar as it can be said to exist, by virtue of human agency.””
—William Gibson (b. 1948)
“Poetry has become the higher algebra of metaphors.”
—José Ortega Y Gasset (1883–1955)