Finding a single row of Matrix after exponentiation
Suppose I have a matrix $M$ of $N \times N$ and I only want a single row of this matrix after raising it to power $K$ ie. some row of $M ^ K$.
This can be done in $O(N^3 \log K)$ at best (or better using advanced matrix multiplication techniques) if we find the entire matrix. However, I am only interested in finding one row of this resultant matrix.
Would it be possible to find one particular row more efficiently than finding the entire matrix?
1 answer
While there are no doubt even more clever things you can do, the most straightforward approach, which will likely make a significant improvement, is to move from matrix-matrix multiplication to matrix-vector multiplication.
Let $e_k$ be a (column) vector with all $0$s except the $k$-th entry is $1$. To get the $k$-th row of a matrix, you just multiply it on the right by $e_k^T$, i.e. $e_k^T M$. Then, instead of computing $e_k^T (M^K)$, you compute $(\cdots((e_k^T M)M)\cdots M)$. You won't be able to exploit repeated squaring, but this takes $O(KN^2)$ time, so if $K < N$ this is faster than doing even a single matrix-matrix multiplication. If $K > N$, you can square $M$ to halve $K$ and quickly get $K < N$. You can do some simple algebra to figure out how many squarings are worthwhile. However, when $K$ is much greater than $N$, you may be better off doing diagonalization-based techniques. If your matrix is diagonalizable (e.g. if it is positive definite), then there are algorithms to diagonalize in $O(N^3)$ time. Once you have the diagonalized form, exponentiation is just exponentiating the components of the diagonal matrix. You would then have something like $O(N^3 + N\log K)$. There are very many techniques to do better at this problem if your matrix has some known special structure.
0 comment threads
0 comment threads