Re: help with vectorization of update rule

[Moo]

On Fri, Oct 22, 2010 at 2:56 AM, grg <address@hidden> wrote:

However, I've just realized that yesterday I missed an important thing.
In my problem A is a *matrix*, not a scalar as in the examples.

That was indeed my initial question.  How to compute efficiently (i.e.,
without a loop) A.^t, when size(A)=[s s], and size(t)=[1 T].

Thanks again for your previous input.
Giorgio

 

Generally speaking, you can vectorize something from a for loop if there is a closed-form version of the iterative process.  In this case, the only closed-form solution (as far as I know) to the iterative process:

x(i+1) = A*x(i) , where x(i) are vectors, A is a matrix,

is x(k) = (A^k)*x(0),

like you guys said.  The problem is that this (in general) awful to compute numerically.  Matrix-matrix multiplication on a n-by-n matrix costs O(n^3), and doing this k times (to compute A^k) is O(k*n^3).  Doing this iteratively for x(k) needs to do k matrix-vector multiplications, which will cost O(k*n^2) instead.  Even if your matrix has a special structure, matrix-vector multiplication will always win out over matrix-matrix multiplication.

Short answer is, if there _is_ any vectorized version to do this, it will never directly compute A^k, and instead do the iterative process.