Solve for x in (A^k)*x=b (sequentially, LU factorization)

22 views (last 30 days)
Mark on 24 Nov 2011
Commented: Sheraline Lawles on 22 Feb 2021
Without computing A^k, solve for x in (A^k)*x=b.
A) Sequentially? (Pseudocode)
for n=1:k
Is the above process correct?
B) LU factorizaion?
How is this accompished?

Accepted Answer

Walter Roberson
Walter Roberson on 24 Nov 2011
However, I would suggest that LU will not help much. See instead
  1 Comment
Nicholas Lamm
Nicholas Lamm on 9 Jul 2018
A) Linking to the documentation is about the least helpful thing you can do and B) youre not even right, LU decomposition is great for solving matrices and is even cheaper in certain situations.

Sign in to comment.

More Answers (1)

Derek O'Connor
Derek O'Connor on 28 Nov 2011
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
Additional Information
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;
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).
Sheraline Lawles
Sheraline Lawles on 22 Feb 2021
Just a note... sadly, the above link to Derek O'Connor's webpage is no longer active.

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!