Solving some special linear system

Assuming we have some matrix $A\in \mathbb C^{m\times m}$ with $n\leq m$ of full rank and there are some vectors $q,b\in \mathbb C^m$. We are now trying to solve the following system $$\left(\begin{array}{c|c|c|c|c|c} q&Aq&A^2q&\dots&A^{n-1}q \end{array}\right) \begin{pmatrix} x_1\\\vdots \\x_n \end{pmatrix}=\begin{pmatrix} b_1\\\vdots \\b_m \end{pmatrix},$$ while we assume that this problem is solvable. The left part looks strongly related to Krylov-subspace methods like the Arnoldi-iteration or GMRES. But this methods, as far as I understand, find the eigenvectors of $A$ or solve the system $Ax=b$ respectively. So, those methods give me information about $A$ and not about $(q|Aq|\dots|A^{n-1}q)$. Is there some method which can solve the given equation above numerically in a stable way? I would be grateful about some tips or keywords which I can search?

Solution 1:

In general, this linear system is so ill-conditioned that you will not be able to trust the computed result. This is particularly clear in the case where $A$ has dominant eigenvalue. In this case the computed values $\hat{y}_j$ of the vectors $y_j=A^j q$ will tend to point in the direction of a dominant eigenvector even when $q$ does not contain any component in this direction. This ensures that the matrix is very ill-conditioned. It is possible to obtain the orthogonal factor of the QR factorization of the Krylov matrix in question see this answer, but it is not clear to me that we can get the triangular factor in a reliable manner.