Consider an arbitrary matrix ${\bf M} \in \mathbb{R}^{n \times n}$ such that $\|{\bf M}\| < 1$, and let ${\bf I}$ be the $n \times n$ identity matrix. I have access to any matrix factorization of ${\bf I} - {\bf M}$ (notice that ${\bf I} - \alpha {\bf M}$ is invertible for $|\alpha|\leq 1$), and I want to compute $\left({{\bf I} - \alpha {\bf M}}\right)^{-1}{\bf x}$ for some ${\bf x} \in \mathbb{R}^n$ and scalar $0 < \alpha < 1$. Is it possible to use the available factorization of ${\bf I} - {\bf M}$ to compute $\left({{\bf I} - \alpha {\bf M}}\right)^{-1}{\bf x}$ in quadratic time complexity?
Thanks in advance.
EDIT: An exact solution is welcome, but I'm also interested in approximate solutions. The main concern is that the solution, whether exact or approximate, should be computable in quadratic time complexity.
You can compute the inverse (and hence the action on a vector) in quadratic time starting with the LU decomposition.