One is required to find power (positive integer) of matrix of real numbers. There are lots of efficient matrix multiplication algorithms (e.g. some parallel algorithms are Cannon's, DNS) but are there algorithms that are intended exactly for finding power of matrix and that are more efficient than sequential execution of matrix multiplication? I am particularly interested in parallel algorithms.
$\begingroup$
$\endgroup$
7
-
1$\begingroup$ What have you tried? Where did you get stuck? What research have you done? Besides the title, where is the question? For the decision version of your problem (from title), the answer is "yes", but you already know it, right? $\endgroup$– EvilCommented Aug 16, 2016 at 20:26
-
2$\begingroup$ @TomR This question probably is of interest to you $\endgroup$– adrianNCommented Aug 17, 2016 at 7:31
-
1$\begingroup$ Maybe something like this? Or you are looking for something else? What are sizes and powers in your application? $\endgroup$– EvilCommented Aug 18, 2016 at 4:20
-
1$\begingroup$ You can compute the nth power with fewer than n-1 multiplications when n ≥ 4. For large matrices, it would usually be worthwhile to find the smallest possible number of multiplications (for example, there's a simple method to calculate n^15 with 6 multiplications, but it can be done with 5). You can then apply the same principle to find the smallest number of sequential multiplications, which will be harder. $\endgroup$– gnasher729Commented Aug 18, 2016 at 8:26
-
1$\begingroup$ You should also consider the amount of parallelism available to you. "Parallelism" is about exploiting resources that would otherwise be unused. If an implementation of matrix multiplication can already use all the resources available efficiently, then there is nothing else to exploit for calculating powers of matrices. $\endgroup$– gnasher729Commented Aug 19, 2016 at 8:22
|
Show 2 more comments
3 Answers
$\begingroup$
$\endgroup$
If you have multiple processors that can work in parallel, then you can calculate any power up to the power (2^k) in k steps. For example: To calculate $M^{15}$, you calculate:
Stage 1: Calculate $M^2$
Stage 2: Calculate $M^3 = M^2 * M$ and $M^4 = M^2 * M^2$
Stage 3: Calculate $M^7 = M^4 * M^3$ and $M^8 = M^4 * M^4$
Stage 4: Calculate $M^{15} = M^8 * M^7$
This is one multiplication more than calculating $M^5$ in three multiplications and raising $M^5$ to the third power in another two multiplications, but should be faster if you have two processors. For arbitrary high powers, you will need more processors.
If you use a brute force algorithm for the multiplication, multiplying row by column, you may save some time by calculating one row of a product, then immediately using that row for the next product. This would help in the calculation of $M^3$ where we can start calculating $M^3$ as soon as the first row of $M^2$ has been calculated; it wouldn't be that helpful with $M^4$ since we need both rows and columns of $M^2$. For large powers, you could probably arrange which powers to calculate.
And after posting this it becomes obvious that you can use multiple processors very easily: You start by calculating the first row of $M^2 = M * M$. When you have that row, you have all the information you need to calculate the first row of $M^3 = M^2 * M$, so you calculate the second row of $M^2$ and the first row of $M^3$ in parallel. Then you can calculate the third row of $M^2$, the second row of $M^3$, and the first row of $M^4$ in parallel and so on.
This will do a lot more operations than necessary (for example, 14 matrix multiplications for $M^{15}$ instead of the minimal 5 or the 6 of the four-stage method). If the power is not large compared to the number of processors this will still be faster. But calculating $M^{1000}$ with four processors using this method will be inefficient; doing this in an optimal way would be an interesting problem.
Combining approaches: Using four processors for example, you can calculate AB, ABC, ABCD and ABCDE almost in parallel by calculating each product one row at a time. This allows calculate all four of $M^2$ to $M^5$ using four processors in about the same time as one product with one processor.
Given these four results and the original M, you can calculate four of the matrices $M^6$ to $M^{25}$ in the same time again, provided the matrices are at most five powers apart from each other. So each power up to $M^{25}$ can be calculated in about twice the time of a single processor matrix product.
With these matrices calculated, all matrices up to $M^{108}$ and some more up to $M^{125}$ can be calculated in three times the time of a single matrix product if four processors are available. With k processors this should go up to at least the power $k (k+1)^2$.
$\begingroup$
$\endgroup$
There's two levels you can analyze parallel speedups with matrix exponentiation: The "macro-algorithmic" level that decides which matrices to multiply, and the "micro-algorithmic" level where you can speed up the multiplications themselves with parallelism.
For the latter, Wikipedia suggests that for multiplying an $n$ by $n$ matrix, we can achieve a complexity of $O(\log^2(n))$ theoretically with an unbounded number of processors, or $O(n)$ with a more realistic parallel algorithm.
(Note: the wikipedia page is for general matrix computation. I'm not sure if that can be parallelized even further using the information that we are squaring a matrix.)
For the former, the question turns into how many rounds of matrix multiplication are necessary to compute $A^m$ for some matrix $A$? (I say rounds, because all the multiplications in a given round may be done in parallel).
The sequential algorithm to beat, as noted in other answers, is Exponentiation by squaring. This allows you to compute $A^k$ in $O(\log(k))$ multiplications.
The question is: can we beat this with parallelism? I claim the answer is no.
The simple reason is that exponentiation by squaring is essentially a dynamic programming algorithm; it lets you skip all the work by reusing subresults, but this in turn creates a data dependency that disallows parallelism. If we get rid of the data dependency, but we also vastly increase the amount of work we have to do.
To better illustrate this, let's look at how you would parallelize matrix multiplication if we were not doing exponentiation. Suppose you were looking to parallelize multiplying $k$ separate square matrices:
$$A_1 A_2 A_3 A_4 A_5 ... A_k$$
The natural way to parallelize this is obvious, you should abuse associativity to perform $\frac{k}{2}$ multiplications in the first round:
$$(A_1 A_2)(A_3 A_4)(A_5 A_6) ... (A_{k-1}A_k)$$
From this, we can clearly multiply our $k$ matrices in $O(\log(k))$ rounds of multiplication because we reduce our problem size by half each round.
However, if we were to perform exponentiation this way, it would look like this:
$$(A A)(A A)(A A)...(A A)$$
In other words, all our parallelism is gaining us is recomputing the same matrix product to calculate $A^2$! Thus,if we use a memoized algorithm such as Exponentiation by squaring, we can do the same thing as the parallel algorithm at each round of multiplication.
Putting all this together, if we want to calculate $A^k$ for $n$ by $n$ matrix $A$, the parallel complexity is $O(\log^2(n)\log(k))$ for the optimistic parallel algorithm, or $O(n\log(k))$ for the realistic one.
$\begingroup$
$\endgroup$
0
If by sequential you mean multiplying $m$ times, the $\log m$ solution of initially only calculating the relevant powers of $2$ (a.k.a Exponentiation by squaring) is clearly better for large $m$.
Improving on that may be specific to certain types of matrices. For instance, if your matrix is diagonalizable, $$A = S \Lambda S^{-1} \rightarrow A^m = S \Lambda^m S^{-1}$$ Thus, calculating the $m$th power is $O(1)$ in $m$.
