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:
“In all cultures, the family imprints its members with selfhood. Human experience of identity has two elements; a sense of belonging and a sense of being separate. The laboratory in which these ingredients are mixed and dispensed is the family, the matrix of identity.”
—Salvador Minuchin (20th century)
“Poetry has become the higher algebra of metaphors.”
—José Ortega Y Gasset (1883–1955)