Can the following linear system be solved in quadratic time? 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.
 A: I'm not sure from reading your question whether you have some matrix factorization of $\mathbf{I}-\mathbf{M}$ or any matrix factorization of your choice. If I interpret your question in the second sense, an exact answer can indeed by achieved in quadratic time.
Let $\mathbf{I} - \mathbf{M} = \mathbf{QTQ}^\top$ by a Schur decomposition; this simplifies to an eigenvalue decomposition if $M$ is symmetric. Then
$$
\mathbf{I} - \alpha \mathbf{M} = (1-\alpha)\mathbf{I} + \alpha(\mathbf{I}-\mathbf{M}) = \mathbf{Q}((1-\alpha)\mathbf{I} + \alpha\mathbf{T})\mathbf{Q}^\top.
$$
The inverse of $\mathbf{I} - \alpha \mathbf{M}$ can be applied to a vector in $\mathcal{O}(n^2)$ operations by the formula
$$
(\mathbf{I} - \alpha \mathbf{M})^{-1}\mathbf{x} = \mathbf{Q}\big[((1-\alpha)\mathbf{I} + \alpha\mathbf{T})^{-1}(\mathbf{Q}^\top\mathbf{x})\big].
$$
Linear solves with $(1-\alpha)\mathbf{I} + \alpha\mathbf{T}$ can be computed in $\mathcal{O}(n^2)$ time since it is triangular.
A: You can compute the inverse (and hence the action on a vector) in quadratic time starting with the LU decomposition.
