Without computing A^k, solve for x in (A^k)*x=b.
A) Sequentially? (Pseudocode)
Is the above process correct?
B) LU factorizaion?
How is this accompished?
No products are associated with this question.
http://www.mathworks.com/help/techdoc/ref/lu.html for LU factorization.
However, I would suggest that LU will not help much. See instead http://www.maths.lse.ac.uk/Personal/martin/fme4a.pdf
Contrary to what Walter says, LU Decomposition is a great help in this problem. See my solution notes to Lab Exercise 6 --- LU Decomposition and Matrix Powers
Here is the Golub-Van Loan Algorithm for solving (A^k)*x = b
[L,U,P] = lu(A); for m = 1:k y = L\(P*b); x = U\y; b = x; end
Matlab's backslash operator "\" is clever enough to figure out that y = L\(P*b) is forward substitution, while x = U\y is back substitution, each of which requires O(n^2) work.
Total amount of work is: O(n^3) + k*O(n^2) = O(n^3 + k*n^2)
If k << n then this total is effectively O(n^3).