7
$\begingroup$

Although I have already learned something about the asymptotic runtimes of matrix multiplication algorithms (Strassen's algorithm and similar things), I have never found any explicit and satisfactory reference to a model of computation, which is used to measure this complexity. In fact, I have found three possible answers, neither of which seems to me as absolutely satisfactory:

  • Wikipedia says that the model used here is the Multitape Turing Machine. This does not seem to make much sense to me, since in the analysis of matrix multiplication, scalar multiplication is supposed to have a constant time complexity. This is not the case on Turing Machines.
  • Some texts describe the complexity only vaguely as the number of arithmetic operations used. However, what exactly are arithmetic operations in this context? I suppose that addition, multiplication, and probably subtraction. But what about division, integer division, remainder, etc.? And what about bitwise operations - how do they fit into this setting?
  • Finally, I have recently discovered an article, which uses the BSS machine as the model of computation. However, this also seems little bit strange to me, since for, e.g., integer matrices, it does not make much sense to me to disallow operations such as, e.g., integer division.

I would be grateful to anyone, who could help me to sort these things out.

$\endgroup$
  • $\begingroup$ For complexity, we care only about one measure: steps of a TM. In algorithm analysis, you are unlikely to get something more precise than "number of basic operations", which roughly correspond to elementary ALU/memory access operations in processors. I think you are asking for algorithm analysis, not problem complexity? $\endgroup$ – Raphael Feb 3 '14 at 9:51
  • $\begingroup$ @Raphael "For complexity, we care only about one measure: steps of a TM." Sorry but that's completely false. First off, there are plenty of models of computation that are not Turing machines: circuits, for example. Then you get things like geometric and descriptive complexity. Even within the realms of Turing machines, space is as important a measure as time. And what kind of Turing machine? Deterministic, nondeterministic, alternating and probabilistic machines all have different resource requirements. Random access is significant if you want finer classifications than "polynomial time". $\endgroup$ – David Richerby Feb 3 '14 at 9:59
  • $\begingroup$ @DavidRicherby: All true. Our statements are compatible; I should have made my scope clearer. "For time complexity as considered in classic classes like P, NP etc, we care...". $\endgroup$ – Raphael Feb 3 '14 at 10:02
  • $\begingroup$ @Raphael But this isn't a question about P, NP, etc. It's a question about a specific problem. Upper bounds for any problem are going to involve algorithm analysis so I don't think it's really possible to split the two. Having said that, yes, it does seem that the complexity of Strassen and so on is expressed in terms of "arithmetic operations", rather than on any standard model of computation. $\endgroup$ – David Richerby Feb 3 '14 at 10:34
  • $\begingroup$ Regarding your second approach (counting arithmetic operations): You could simply count the number of each operation (multiplication, addition, bitwise operations, etc) separately. You can find an example where that is done e.g. in Sedgewick & Flajolet: Introduction to the Analysis of Algorithms (there they analyze Quicksort quite precisely). With matrix multiplication I believe that the number of multiplications involved dominates the rest, so essentially you're counting that. $\endgroup$ – john_leo Feb 3 '14 at 10:45
7
$\begingroup$

Matrix multiplication algorithms are analyzed in terms of arithmetic complexity. The computation model is straight-line programs with instructions of the form $a \gets b \circ c$, where $\circ \in \{ +,-,\times,\div \}$, $a$ is a variable, and $b,c$ could be either variables, inputs or constants. Additionally, certain variables are distinguished as outputs. For example, here is how to multiply two $2\times 2$ matrices using the usual algorithm, with input matrices $a_{ij},b_{ij}$ and output matrix $c_{ij}$:

$$ \begin{align*} x_{11} &\gets a_{11} \times b_{11} & y_{11} &\gets a_{12} \times b_{21} & c_{11} &\gets x_{11} + y_{11} \\ x_{12} &\gets a_{11} \times b_{12} & y_{12} &\gets a_{12} \times b_{22} & c_{12} &\gets x_{12} + y_{12} \\ x_{21} &\gets a_{21} \times b_{11} & y_{21} &\gets a_{22} \times b_{21} & c_{21} &\gets x_{21} + y_{21} \\ x_{22} &\gets a_{21} \times b_{12} & y_{22} &\gets a_{22} \times b_{22} & c_{22} &\gets x_{22} + y_{22} \end{align*} $$ The complexity measure is the number of lines in the program.

For matrix multiplication, one can prove a normal form for all algorithms. Every algorithm can be converted into an algorithm of the following form, at the cost of only a constant multiplicative increase in complexity:

  1. Certain linear combinations $\alpha_i$ of the input matrix $a_{jk}$ are calculated.
  2. Certain linear combinations $\beta_i$ of the input matrix $b_{jk}$ are calculated.
  3. $\gamma_i \to \alpha_i \times \beta_i$.
  4. Each entry in the output matrix is a linear combination of $\gamma_i$s.

This is known as bilinear normal form. In the matrix multiplication algorithm shown above, $x_{jk},y_{jk}$ function as the $\gamma_i$, but in Strassen's algorithm the linear combinations are more interesting; they are the $M_i$'s in Wikipedia's description.

Using a tensoring approach (i.e. recursively applying the same algorithm), similar to the asymptotic analysis of Strassen's algorithm, one can show that given such an algorithm for multiplying $n\times n$ matrix with $r$ products (i.e. $r$ variables $\gamma_i$), then arbitrary $N\times N$ matrices can be multiplied in complexity $O(N^{\log_n r})$; thus only the number of products matters asymptotically. In Strassen's algorithm, $n = 2$ and $r = 7$, and so the bound is $O(N^{\log_2 7})$.

The problem of finding the minimal number of products needed to compute matrix multiplication can be phrased as finding the rank of a third-order tensor (a "matrix" with three indices rather than two), and this forms the connection to algebraic complexity theory. You can find more information in this book or these lecture notes (continued here).


The reason this model is used is twofold: first, it is very simple and amenable to analysis; second, it is closely related to the more common RAM model.

Straight-line programs can be implemented in the RAM model, and the complexity in both models is strongly related: arithmetic operations have unit cost in several variants of the model (for example, the RAM model with real numbers), and are otherwise related polynomially to the size of the numbers. In the case of modular matrix multiplication, therefore, arithmetic complexity provides an upper bound on complexity in the RAM model. In the case of integer or rational matrix multiplication, one can show that for bilinear algorithms resulting from tensorization, the size of the numbers doesn't grow too much, and so arithmetic complexity provides an upper bound for the RAM model, up to logarithmic factors.

It could a priori be the case that a RAM machine can pull some tricks that the arithmetic model is oblivious to. But often we want matrix multiplication algorithms to work for matrices over arbitrary fields (or even rings), and in that case uniform algorithm should only use the arithmetic operations specified by the model. So this model is a formalization of "field-independent" algorithms.

$\endgroup$
  • $\begingroup$ Is there a Turing machine model? $\endgroup$ – T.... Oct 2 '16 at 8:43
  • $\begingroup$ It turns out you don't need one. Usually one introduces the Turing machine to introduce uniformity – one piece of code that works for all $n$. While the model I have described is non-uniform, it turns out that you can approach the optimal exponent $\omega$ even uniformly, by brute-forcing a good algorithm on some matrix size much smaller than $n$. $\endgroup$ – Yuval Filmus Oct 2 '16 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.