Naive matrix multiplication - Revision history

Vipul: /* Variants given special structure to the matrices */

2014-04-29T02:41:32Z

Variants given special structure to the matrices

← Older revision		Revision as of 02:41, 29 April 2014
Line 42:		Line 42:

	{\| class="sortable" border="1"		{\| class="sortable" border="1"
	! Type of matrices !! Number of multiplications under naive matrix multiplication, not accounting for structure !! Number of additions under naive matrix multiplication, not accounting for structure !! Number of multiplications under naive matrix multiplication, accounting for structure !! Number of additions under naive matrix multiplication, accounting for structure		! Type of matrices !! Number of multiplications under naive matrix multiplication, not accounting for structure !! Number of additions under naive matrix multiplication, not accounting for structure !! Number of multiplications under naive matrix multiplication, accounting for structure !! Number of additions under naive matrix multiplication, accounting for structure !! Big-Oh saving?
	\|-		\|-
	\| Both are <math>n \times n</math> [[diagonal matrix\|diagonal matrices]] \|\| <math>n^3</math> \|\| <math>n^2(n - 1)</math> \|\| <math>n</math> \|\| 0		\| Both are <math>n \times n</math> [[diagonal matrix\|diagonal matrices]] \|\| <math>n^3</math> \|\| <math>n^2(n - 1)</math> \|\| <math>n</math> \|\| 0 \|\| Yes
	\|-		\|-
	\| <math>A</math> is <math>n \times n</math> diagonal, <math>B</math> is arbitrary <math>n \times p</math> \|\| <math>n^2p</math> \|\| <math>n(n - 1)p</math> \|\| <math>np</math> \|\| 0		\| <math>A</math> is <math>n \times n</math> diagonal, <math>B</math> is arbitrary <math>n \times p</math> \|\| <math>n^2p</math> \|\| <math>n(n - 1)p</math> \|\| <math>np</math> \|\| 0 \|\| Yes
	\|-		\|-
	\| Both are <math>n \times n</math> [[upper triangular matrix\|upper triangular matrices]] \|\| <math>n^3</math> \|\| <math>n^2(n - 1)</math> \|\| <math>\binom{n+2}{3} = \frac{n(n+1)(n+2)}{6}</math> \|\| <math>\binom{n+1}{3} =\frac{n(n+1)(n-1)}{6}</math>		\| Both are <math>n \times n</math> [[upper triangular matrix\|upper triangular matrices]] \|\| <math>n^3</math> \|\| <math>n^2(n - 1)</math> \|\| <math>\binom{n+2}{3} = \frac{n(n+1)(n+2)}{6}</math> \|\| <math>\binom{n+1}{3} =\frac{n(n+1)(n-1)}{6}</math> \|\| No
	\|}		\|}

Vipul: /* Variants given special structure to the matrices */

2014-04-29T02:35:20Z

Variants given special structure to the matrices

← Older revision		Revision as of 02:35, 29 April 2014
Line 48:		Line 48:
	\| <math>A</math> is <math>n \times n</math> diagonal, <math>B</math> is arbitrary <math>n \times p</math> \|\| <math>n^2p</math> \|\| <math>n(n - 1)p</math> \|\| <math>np</math> \|\| 0		\| <math>A</math> is <math>n \times n</math> diagonal, <math>B</math> is arbitrary <math>n \times p</math> \|\| <math>n^2p</math> \|\| <math>n(n - 1)p</math> \|\| <math>np</math> \|\| 0
	\|-		\|-
	\| Both are <math>n \times n</math> [[upper triangular matrix\|upper triangular matrices]] \|\| <math>n^3</math> \|\| <math>n^2(n - 1)</math> \|\| <math>\binom{n}{3} = \frac{n(n-1)(n-2)}{6}</math> \|\| <math>\binom{n}{3~~} - \binom{n}{2~~} = \frac{n(n-1)(n-5)}{6}</math>		\| Both are <math>n \times n</math> [[upper triangular matrix\|upper triangular matrices]] \|\| <math>n^3</math> \|\| <math>n^2(n - 1)</math> \|\| <math>\binom{n+2}{3} = \frac{n(n+1)(n+2)}{6}</math> \|\| <math>\binom{n+1}{3} =\frac{n(n+1)(n-1)}{6}</math>
	\|}		\|}

Vipul: /* Variants given special structure to the matrices */

2014-04-29T02:32:17Z

Variants given special structure to the matrices

← Older revision		Revision as of 02:32, 29 April 2014
Line 46:		Line 46:
	\| Both are <math>n \times n</math> [[diagonal matrix\|diagonal matrices]] \|\| <math>n^3</math> \|\| <math>n^2(n - 1)</math> \|\| <math>n</math> \|\| 0		\| Both are <math>n \times n</math> [[diagonal matrix\|diagonal matrices]] \|\| <math>n^3</math> \|\| <math>n^2(n - 1)</math> \|\| <math>n</math> \|\| 0
	\|-		\|-
	\| <math>A</math> is <math>n \times n<math> diagonal, <math>B</math> is arbitrary <math>n \times p</math> \|\| <math>n^2p</math> \|\| <math>n(n - 1)p</math> \|\| <math>np</math> \|\| 0		\| <math>A</math> is <math>n \times n</math> diagonal, <math>B</math> is arbitrary <math>n \times p</math> \|\| <math>n^2p</math> \|\| <math>n(n - 1)p</math> \|\| <math>np</math> \|\| 0
	\|-		\|-
	\| Both are <math>n \times n</math> [[upper triangular matrix\|upper triangular matrices]] \|\| <math>n^3</math> \|\| <math>n^2(n - 1)</math> \|\| <math>\binom{n}{3} = \frac{n(n-1)(n-2)}{6}</math> \|\| <math>\binom{n}{3} - \binom{n}{2} = \frac{n(n-1)(n-5)}{6}</math>		\| Both are <math>n \times n</math> [[upper triangular matrix\|upper triangular matrices]] \|\| <math>n^3</math> \|\| <math>n^2(n - 1)</math> \|\| <math>\binom{n}{3} = \frac{n(n-1)(n-2)}{6}</math> \|\| <math>\binom{n}{3} - \binom{n}{2} = \frac{n(n-1)(n-5)}{6}</math>
	\|}		\|}

Vipul: /* Variants given special structure to the matrices */

2014-04-29T02:32:00Z

Variants given special structure to the matrices

← Older revision		Revision as of 02:32, 29 April 2014
Line 42:		Line 42:

	{\| class="sortable" border="1"		{\| class="sortable" border="1"
	! Type of matrices !! ~~What~~ naive matrix multiplication ~~would give~~ for ~~number of additions if we do not take matrix~~ structure ~~into account~~!! ~~What~~ naive matrix multiplication ~~would give~~ for ~~number of multiplications if we do not take matrix~~ structure ~~into account~~!! ~~What~~ naive matrix multiplication ~~would give~~ for ~~number of additions if we take matrix~~ structure ~~into account~~ !! ~~What~~ naive matrix multiplication ~~would give~~ for ~~number of multiplications if we take matrix~~ structure ~~into account~~		! Type of matrices !! Number of multiplications under naive matrix multiplication, not accounting for structure !! Number of additions under naive matrix multiplication, not accounting for structure !! Number of multiplications under naive matrix multiplication, accounting for structure !! Number of additions under naive matrix multiplication, accounting for structure
	\|-		\|-
	\| Both are <math>n \times n</math> [[diagonal matrix\|diagonal matrices]] \|\| <math>n^~~2(n - 1)~~</math> \|\| <math>n^3</math> ~~\|\| 0~~ \|\| <math>n</math>		\| Both are <math>n \times n</math> [[diagonal matrix\|diagonal matrices]] \|\| <math>n^3</math> \|\| <math>n^2(n - 1)</math> \|\| <math>n</math> \|\| 0
	\|-		\|-
	\| <math>A</math> is <math>n \times n<math> diagonal, <math>B</math> is arbitrary <math>n \times p</math> \|\| <math>n~~(n - 1)p~~</math> \|\| <math>n~~^2p~~</math> ~~\|\| 0~~ \|\| <math>np</math>		\| <math>A</math> is <math>n \times n<math> diagonal, <math>B</math> is arbitrary <math>n \times p</math> \|\| <math>n^2p</math> \|\| <math>n(n - 1)p</math> \|\| <math>np</math> \|\| 0
	\|-		\|-
	\| Both are <math>n \times n</math> [[upper triangular matrix\|upper triangular matrices]] \|\| <math>n^~~2(n - 1)~~</math> \|\| <math>n^3</math> \|\| <math>\binom{n}{3~~} - \binom{n}{2~~} = \frac{n(n-1)(n-5)}{6}</math> \|\| <math>\binom{n}{3} = \frac{n(n-1)(n-2)}{6}</math>		\| Both are <math>n \times n</math> [[upper triangular matrix\|upper triangular matrices]] \|\| <math>n^3</math> \|\| <math>n^2(n - 1)</math> \|\| <math>\binom{n}{3} = \frac{n(n-1)(n-2)}{6}</math> \|\| <math>\binom{n}{3} - \binom{n}{2} = \frac{n(n-1)(n-5)}{6}</math>
	\|}		\|}

Vipul: /* Arithmetic complexity */

2014-04-29T02:29:44Z

Arithmetic complexity

← Older revision		Revision as of 02:29, 29 April 2014
Line 17:		Line 17:

	{\| class="sortable" border="1"		{\| class="sortable" border="1"
	! Case !! Arithmetic description !! Number of ~~additions~~ needed !! Number of ~~multiplications~~ needed		! Case !! Arithmetic description !! Number of multiplications needed !! Number of additions needed
	\|-		\|-
	\| Both matrices are square matrices of the same size \|\| <math>m = n = p</math>; we will use <math>n</math> for these equal numbers \|\| <math>n^2(n - 1) = n^3 - n^2~~</math> \|\| <math>n^3~~</math>		\| Both matrices are square matrices of the same size \|\| <math>m = n = p</math>; we will use <math>n</math> for these equal numbers \|\| <math>n^3</math> \|\| <math>n^2(n - 1) = n^3 - n^2</math>
	\|-		\|-
	\| The first matrix is a row matrix and the second matrix is a column matrix, so the product is a <math>1 \times 1</math> matrix and the product is a [[dot product]] \|\| <math>m = p = 1</math>, <math>n</math> can be arbitrary \|\| <math>n ~~- 1~~</math> \|\| <math>n</math>		\| The first matrix is a row matrix and the second matrix is a column matrix, so the product is a <math>1 \times 1</math> matrix and the product is a [[dot product]] \|\| <math>m = p = 1</math>, <math>n</math> can be arbitrary \|\| <math>n</math> \|\| <math>n - 1</math>
	\|-		\|-
	\| The first matrix is a column matrix, the second matrix is a row matrix, so the product is a [[Hadamard product]] (outer product) \|\| <math>n = 1</math>; the values <math>m,p</math> can be arbitrary ~~\|\| 0~~ \|\| <math>mp</math>		\| The first matrix is a column matrix, the second matrix is a row matrix, so the product is a [[Hadamard product]] (outer product) \|\| <math>n = 1</math>; the values <math>m,p</math> can be arbitrary \|\| <math>mp</math> \|\| 0
	\|-		\|-
	\| The product matrix is a square matrix \|\| <math>m = p</math> (we will denote this equal value as <math>m</math>); <math>n</math> can be arbitrary \|\| <math>m^~~2(n - 1)~~</math> \|\| <math>m^2n</math>		\| The product matrix is a square matrix \|\| <math>m = p</math> (we will denote this equal value as <math>m</math>); <math>n</math> can be arbitrary \|\| <math>m^2n</math> \|\| <math>m^2(n - 1)</math>
	\|}		\|}
	===Complexity allowing for parallelization===		===Complexity allowing for parallelization===

Vipul: /* Variants given special structure to the matrices */

2014-04-29T02:28:35Z

Variants given special structure to the matrices

← Older revision		Revision as of 02:28, 29 April 2014
Line 40:		Line 40:

	If we are given prior guarantees that the matrix has a particular structure, and preferably an encoding of the matrix that exploits the structure, then even the "naive" matrix multiplication algorithm may be improvable. In particular, if we know a specific subset of the entries is guaranteed to be zero, we can save on the effort of computing the summands that are products of those terms.		If we are given prior guarantees that the matrix has a particular structure, and preferably an encoding of the matrix that exploits the structure, then even the "naive" matrix multiplication algorithm may be improvable. In particular, if we know a specific subset of the entries is guaranteed to be zero, we can save on the effort of computing the summands that are products of those terms.

			{\| class="sortable" border="1"
			! Type of matrices !! What naive matrix multiplication would give for number of additions if we do not take matrix structure into account!! What naive matrix multiplication would give for number of multiplications if we do not take matrix structure into account!! What naive matrix multiplication would give for number of additions if we take matrix structure into account !! What naive matrix multiplication would give for number of multiplications if we take matrix structure into account
			\|-
			\| Both are <math>n \times n</math> [[diagonal matrix\|diagonal matrices]] \|\| <math>n^2(n - 1)</math> \|\| <math>n^3</math> \|\| 0 \|\| <math>n</math>
			\|-
			\| <math>A</math> is <math>n \times n<math> diagonal, <math>B</math> is arbitrary <math>n \times p</math> \|\| <math>n(n - 1)p</math> \|\| <math>n^2p</math> \|\| 0 \|\| <math>np</math>
			\|-
			\| Both are <math>n \times n</math> [[upper triangular matrix\|upper triangular matrices]] \|\| <math>n^2(n - 1)</math> \|\| <math>n^3</math> \|\| <math>\binom{n}{3} - \binom{n}{2} = \frac{n(n-1)(n-5)}{6}</math> \|\| <math>\binom{n}{3} = \frac{n(n-1)(n-2)}{6}</math>
			\|}

Vipul at 02:18, 29 April 2014

2014-04-29T02:18:13Z

@@ Line 16: / Line 16: @@
 * Under the assumption that our algorithm allows only for the addition of numbers two at a time, the total number of additions required is <math>m(n - 1)p</math>: To compute each entry, we need to add <math>n</math> products. This requires <math>n - 1</math> additions (we add the first two, then the third to the sum, and so on). There are <math>mp</math> entries in total, so we get a total addition count of <math>m(n - 1)p</math>.
 ===Complexity allowing for parallelization===
@@ Line 25: / Line 36: @@
 In practice, no matrix multiplication algorithm would be that fast, because of communication complexity issues: it is unrealistic to expect that all the parallel processors will be able to read and write the main data at zero cost.

Vipul: Created page with "==Definition== '''Naive matrix multiplication''' refers to the naive algorithm for executing matrix multiplication: we calculate each entry as the sum of products. Expli..."

2014-04-29T02:09:49Z

Created page with "==Definition== '''Naive matrix multiplication''' refers to the naive algorithm for executing matrix multiplication: we calculate each entry as the sum of products. Expli..."

New page

==Definition==

'''Naive matrix multiplication''' refers to the naive algorithm for executing [[matrix multiplication]]: we calculate each entry as the sum of products.

Explicitly, suppose <math>A = (a_{ij})_{1 \le i \le m, 1 \le j \le n}</math> is a <math>m \times n</math> matrix and <math>B = (b_{jk})_{1 \le j \le n, 1 \le k \le p}</math> is a <math>n \times p</math> matrix, and denote by <math>C = (c_{ik})_{1 \le i \le m, 1 \le k \le p}</math> the product of the matrices. We then have the following formula:

<math>c_{ik} = \sum_{j=1}^n a_{ij}b_{jk}</math>

In other words, each entry of the product is computed as a sum of <math>n</math> pairwise products.

==Arithmetic complexity==

===Complexity for the serial algorithm without parallelization===

* The total number of multiplications is <math>mnp</math>: there are <math>n</math> multiplications required to calculate each entry, and there are <math>mp</math> entries to be calculated.
* Under the assumption that our algorithm allows only for the addition of numbers two at a time, the total number of additions required is <math>m(n - 1)p</math>: To compute each entry, we need to add <math>n</math> products. This requires <math>n - 1</math> additions (we add the first two, then the third to the sum, and so on). There are <math>mp</math> entries in total, so we get a total addition count of <math>m(n - 1)p</math>.

===Complexity allowing for parallelization===

The ''arithmetic'' complexity allowing parallelization (ignoring communication complexity issues entirely) is <math>\lceil \log_2n \rceil</math>. The reasoning is as follows:

* The computations of all the matrix entries can be done in parallel, because the computations for the entries do not depend on each other.
* For computing a given entry, all the computations of the products being added can be done in parallel. Combined with the preceding observation, we obtain that all the <math>mnp</math> multiplications can be performed in parallel.
* The only thing that cannot be completely parallelized is the addition step. However, this too can be partly parallelized. We can divide the list of terms to be added into two halves, sum them up, and combine. By iterating this process of dividing in halves and adding, we can encode the parallelized addition using a binary tree. The arithmetic time complexity is then given by the depth of the tree, which is <math>\lceil \log_2n \rceil</math>.

In practice, no matrix multiplication algorithm would be that fast, because of communication complexity issues: it is unrealistic to expect that all the parallel processors will be able to read and write the main data at zero cost.