A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Because matrix multiplication is such a central operation in many numerical algorithms, much work has been invested in making matrix multiplication algorithms efficient. Applications of matrix multiplication in computational problems are found in many fields including scientific computing and pattern recognition and in seemingly unrelated problems such as counting the paths through a graph.[1] Many different algorithms have been designed for multiplying matrices on different types of hardware, including parallel and distributed systems, where the computational work is spread over multiple processors (perhaps over a network).
Directly applying the mathematical definition of matrix multiplication gives an algorithm that takes time on the order of n3 field operations to multiply two n × n matrices over that field (Θ(n3) in big O notation). Better asymptotic bounds on the time required to multiply matrices have been known since the Strassen's algorithm in the 1960s, but the optimal time (that is, the computational complexity of matrix multiplication) remains unknown. As of April 2024[update], the best announced bound on the asymptotic complexity of a matrix multiplication algorithm is O(n2.371552) time, given by Williams, Xu, Xu, and Zhou.[2] [3] This improves on the bound of O(n2.3728596) time, given by Alman and Williams.[4][5] However, this algorithm is a galactic algorithm because of the large constants and cannot be realized practically.
Iterative algorithm
The definition of matrix multiplication is that if C = AB for an n × m matrix A and an m × p matrix B, then C is an n × p matrix with entries
From this, a simple algorithm can be constructed which loops over the indices i from 1 through n and j from 1 through p, computing the above using a nested loop:
- Input: matrices A and B
- Let C be a new matrix of the appropriate size
- For i from 1 to n:
- For j from 1 to p:
- Let sum = 0
- For k from 1 to m:
- Set sum ← sum + Aik × Bkj
- Set Cij ← sum
- For j from 1 to p:
- Return C
This algorithm takes time Θ(nmp) (in asymptotic notation).[1] A common simplification for the purpose of algorithm analysis is to assume that the inputs are all square matrices of size n × n, in which case the running time is Θ(n3), i.e., cubic in the size of the dimension.[6]
Cache behavior
The three loops in iterative matrix multiplication can be arbitrarily swapped with each other without an effect on correctness or asymptotic running time. However, the order can have a considerable impact on practical performance due to the memory access patterns and cache use of the algorithm;[1] which order is best also depends on whether the matrices are stored in row-major order, column-major order, or a mix of both.
In particular, in the idealized case of a fully associative cache consisting of M bytes and b bytes per cache line (i.e. M/b cache lines), the above algorithm is sub-optimal for A and B stored in row-major order. When n > M/b, every iteration of the inner loop (a simultaneous sweep through a row of A and a column of B) incurs a cache miss when accessing an element of B. This means that the algorithm incurs Θ(n3) cache misses in the worst case. As of 2010[update], the speed of memories compared to that of processors is such that the cache misses, rather than the actual calculations, dominate the running time for sizable matrices.[7]
The optimal variant of the iterative algorithm for A and B in row-major layout is a tiled version, where the matrix is implicitly divided into square tiles of size √M by √M:[7][8]
- Input: matrices A and B
- Let C be a new matrix of the appropriate size
- Pick a tile size T = Θ(√M)
- For I from 1 to n in steps of T:
- For J from 1 to p in steps of T:
- For K from 1 to m in steps of T:
- Multiply AI:I+T, K:K+T and BK:K+T, J:J+T into CI:I+T, J:J+T, that is:
- For i from I to min(I + T, n):
- For j from J to min(J + T, p):
- Let sum = 0
- For k from K to min(K + T, m):
- Set sum ← sum + Aik × Bkj
- Set Cij ← Cij + sum
- For j from J to min(J + T, p):
- For K from 1 to m in steps of T:
- For J from 1 to p in steps of T:
- Return C
In the idealized cache model, this algorithm incurs only Θ(n3/b √M) cache misses; the divisor b √M amounts to several orders of magnitude on modern machines, so that the actual calculations dominate the running time, rather than the cache misses.[7]
Divide-and-conquer algorithm
An alternative to the iterative algorithm is the divide-and-conquer algorithm for matrix multiplication. This relies on the block partitioning
which works for all square matrices whose dimensions are powers of two, i.e., the shapes are 2n × 2n for some n. The matrix product is now
which consists of eight multiplications of pairs of submatrices, followed by an addition step. The divide-and-conquer algorithm computes the smaller multiplications recursively, using the scalar multiplication c11 = a11b11 as its base case.
The complexity of this algorithm as a function of n is given by the recurrence[6]
accounting for the eight recursive calls on matrices of size n/2 and Θ(n2) to sum the four pairs of resulting matrices element-wise. Application of the master theorem for divide-and-conquer recurrences shows this recursion to have the solution Θ(n3), the same as the iterative algorithm.[6]
Non-square matrices
A variant of this algorithm that works for matrices of arbitrary shapes and is faster in practice[7] splits matrices in two instead of four submatrices, as follows.[9] Splitting a matrix now means dividing it into two parts of equal size, or as close to equal sizes as possible in the case of odd dimensions.
- Inputs: matrices A of size n × m, B of size m × p.
- Base case: if max(n, m, p) is below some threshold, use an unrolled version of the iterative algorithm.
- Recursive cases:
- If max(n, m, p) = n, split A horizontally:
- Else, if max(n, m, p) = p, split B vertically:
- Otherwise, max(n, m, p) = m. Split A vertically and B horizontally:
Antropológia
Aplikované vedy
Bibliometria
Dejiny vedy
Encyklopédie
Filozofia vedy
Forenzné vedy
Humanitné vedy
Knižničná veda
Kryogenika
Kryptológia
Kulturológia
Literárna veda
Medzidisciplinárne oblasti
Metódy kvantitatívnej analýzy
Metavedy
Metodika
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk