Solve $A^k x = b$ where $k$ is a positive integer

Question

I have to solve this system $$ A^k x = b $$ using gaussian elimination with complete pivoting in matlab. How can I implement that in an efficient way?

Answer 1

Step 1: Calculate $B = A^k$.

Step 2: Solve $Bx = b$ in whatever way you deem fit.

Answer 2

You can solve a sequence of linear systems. If you call $y_1 = A^{k-1} x$, your system is equivalent to $A y_1 = b$, which you can solve for $y_1$. Once you have $y_1$, $x$ would be recovered from the relation $A^{k-1} x = y_1$. If $k-1 > 1$ you repeat the process calling $y_2 = A^{k-2} x$ and solving the system $A y_2 = y_1$. And so on... This is more efficient than it looks because all systems have the same matrix, which only needs to be factorized once.

Obviously, you could also just compute $A^k$ and solve a single system.