21
$\begingroup$

To calculate $y = ABx$ where $A$ and $B$ are two $N\times N$ matrices and $x$ is an vector in $N$-dimensional space. there are two methods. One is to first calculate $z=Bx$, and then $y = Az$. This way takes roughly $2N^2$ multiplications. The other is to first calculate $C = AB$, and then $y=Cx$. This way, however, takes $N^3+N^2$ multiplications!

Am I correct on this? I do not understand why change of the order of the calculation introduces so much difference in the computation complexity.

$\endgroup$
  • 1
    $\begingroup$ I hope there is a good answer to this question, but I'll comment that the phenomenon has been studied pretty well, in some sense. See this Wikipedia page. $\endgroup$ – pjs36 Oct 18 '15 at 15:48
  • $\begingroup$ You could also use this formula, but it's $2N^3$ multiplications! $$y_i = \sum_{jk} A_{ij} B_{jk} x_k $$ $\endgroup$ – Hurkyl Oct 18 '15 at 20:59
  • 1
    $\begingroup$ “$x$ is a $N\times 1$ vector...” please avoid saying things like that. $x$ is a vector in an $N$-dimensional space $V$, that. It so happens that such vectors can be represented by $N\times 1$ matrices, but it's good to make a conceptual distinction. (Basically, the matrix version describes a function $\mathbb{R}\to V$, not just a vector in $V$.) $\endgroup$ – leftaroundabout Oct 19 '15 at 7:30
  • $\begingroup$ @leftaroundabout: Sure. Thank you for correction. $\endgroup$ – Nan Oct 19 '15 at 14:13
33
$\begingroup$

I like this question. I've seen the solution to efficiently calculating a chain of matrix multiplications in an algorithms class, but it's not very enlightening. I've always meant to think more about the problem because associativity is interesting. So, let me try my hand at an explanation.

When you have an $N$ by $N$ matrix, it's a shorthand for describing a linear transformation from an $N$-dimensional vector space to itself. It does that by keeping track of where $N$ basis vectors get sent (these are the columns of your matrix).

Now, I'll just speak heuristically and it won't be very precise. I'll say that to write down a matrix, you just need to keep track of where $N$ linearly independent vectors get sent, not necessarily a basis. This is true, but all sorts of actual computational things depend on the exact basis (like actually writing down a vector, or doing standard calculations like $Bx$).

When you compute $AB$, you're keeping track of where $N$ linearly independent vectors get sent. But when you go on and use your freshly-computed $AB$ to compute $(AB)x$, you just care about where $1$ vector gets sent -- even though you went through all the trouble of keeping track of what $AB$ does to $N - 1$ other vectors!

Computing $A(Bx)$ is great, because at each step, it only pays attention to what's happening to the vectors you care about; it has no idea what happens to the other $N - 1$ linearly independent vectors, and so it only takes about one $N$th as much work as computing $(AB)x$.

While not exactly precise, I'd like to believe this is the idea behind why computing $A(Bx)$ is more efficient than $(AB)x$, which is what I think you are after.

$\endgroup$
  • 3
    $\begingroup$ This is exactly what I was looking for. Thank you for your clear explanation. $\endgroup$ – Nan Oct 18 '15 at 20:31
4
$\begingroup$

Yes you are correct, this is used a lot in engineering. Two popular cases:

  1. Knowing $AB$ and trying to find $A$ and $B$ which individually contain larger percent 0s than $AB$ multiplied together does. Usually called factoring or "fast transforms". If we lose enough non-zero numbers we can save calculations in this way.
  2. Precomputing $AB$ if we have individual $A$ and $B$ and want to calculate $ABv$ for lots of $v$:s. This should be done if $AB$ is simpler than $A$, $B$ separately.
$\endgroup$
2
$\begingroup$

This is because the step $C = AB$ takes more multiplications as we are multiplying two matrices, the first method you mention does not do this.

Each step $z=Bx$ and $y = Az$ contributes $N^2$ multiplications only, as it is a vector multiplied by a matrix and not a matrix multiplied by a matrix.

$\endgroup$

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.