1
$\begingroup$

Binary exponentiation is a well-known method for evaluating positive integer powers of a matrix, $A^p, \; A\in\mathbb C^{n\times n},\,p\in\mathbb Z^+$.

However, I am not seeing an obvious way to adapt this algorithm to the problem of computing its action on a vector, $A^pv,\; v\in\mathbb C^n$. For a reasonably-sized matrix, I could certainly form $A^p$ first before multiplying it with $v$, but what I actually have is a matrix that is too huge to be formed explicitly (in fact, all I have is a black-box routine for evaluating the product $Av$).

How can I adapt binary exponentiation to compute the action of an integer-order matrix power on a vector? Alternatively, are there other methods to compute this if binary exponentiation isn't feasible?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ You can't. As far as I know, everyone does the products one after the other ($v_{k+1}=Av_k$), in practice. This is a very common operation (e.g., Arnoldi method, power iteration...), so it would be very strange if someone came up with a better method all of a sudden. $\endgroup$
    – Federico Poloni
    Commented May 15, 2017 at 10:30
  • $\begingroup$ You cannot adapt this technique. But another common technique is to perform a singular decomposition $A=B^T\Lambda B$ where $\Lambda$ is diagonal. If such a diagonalization presents special structure, then you can probably hope that you do not need to write all steps down. $\endgroup$
    – Henry.L
    Commented May 15, 2017 at 10:36
  • 1
    $\begingroup$ @Henry, that doesn't look like an SVD to me, and I'm also missing on how one might use SVD to efficiently evaluate a matrix function, much less the action form. If you intended to present the eigendecomposition, then you of course know that not all matrices are diagonalizable. $\endgroup$
    – J. M. isn't a mathematician
    Commented May 15, 2017 at 12:48
  • $\begingroup$ @J.M.isn'tamathematician I used singular/eigenvalue decomposition for the same thing, you can tell from my notations....they are all diagonalizable since the order is finite and they are on $\mathbb{C}$ which is algebraically closed...If you read OP carefully, you will see the only obstacle is that the matrix is too big... $\endgroup$
    – Henry.L
    Commented May 15, 2017 at 13:42
  • 1
    $\begingroup$ @Henry, $\begin{pmatrix}1 & 1 & 0 \\0 & 1 & 1 \\0 & 0 & 1\end{pmatrix}$ and larger versions of it were what I had in mind for "not diagonalizable" (i.e. defective). $\endgroup$
    – J. M. isn't a mathematician
    Commented May 15, 2017 at 13:48

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .