For a vector $b \in \mathbb{R}^n$ and $A \in \mathbb{R}^{n \times n}$ the Krylov subspace is the subspace $\mathcal{K}_k(A,b) = \operatorname{span}\{b,Ab,\dots ,A^kb\}$.
I am currently working with the Matrix $Y = [b | Ab |\dots |A^kb]$ in a numeric application, but for sufficiently large $k$ it's condition converges to zero, since the $A^kb$ converge to an eigenvector and thus the columns become nearly linearly dependent. I am looking for a way to improve the condition while keeping the same column space. This can obviously be improved by orthogonalization, but that is too expensive in my case, as it requires $k^2$ summations and inner products. Is there another way to improve the condition of $Y$?
To be precise, I am working with the vectorization of tensors given in a specific format, so the vectors above can have very many entries; basic operations like addition and scalar products are easily executable; procedures like householder transformations are therefore not feasible.