I have matrices $A$ and $G$. $A$ is sparse and is $n\times n$ with $n$ very large (can be on the order of several million.) $G$ is an $n\times m$ tall matrix with $m$ rather small ($1 \lt m \lt 1000$) and each column can only have a single $1$ entry with the rest being $0$'s, such that $G^TG = I$. $A$ is huge, so it is really tough to invert, and I can solve a linear system such as $Ax = b$ iteratively using a Krylov subspace method such as $\mathrm{BiCGStab}(l)$, but I do not have $A^{-1}$ explicitly.I want to solve a system of the form: $(G^TA^{-1}G)x = b$, where $x$ and $b$ are $m$ length vectors. One way to do it is to use an iterative algorithm within an iterative algorithm to solve for $A^{-1}$ for each iteration of the outer iterative algorithm. This would be extremely computationally expensive, however. I was wondering if there is a computationally easier way to go about solving this problem.
Solving $(G^TA^{-1}G)x = b$ without inverting $A$
linear algebra;numerics;linear solver;sparse;krylov method
Introduce the vector $y:=-A^{-1}Gx$ and solve the large coupled system $Ay+Gx=0$, $G^Ty=-b$ for $(y,x)$ simultaneously, using an iterative method. If $A$ is symmetric (as seems likely though you don't state it explicitly) then the system is symmetric (but indefinite, though quasidefinite if $A$ is positive definite), which might help you to choose an appropriate method. (relevant keywords: KKT matrix, quasidefinite matrix).Edit: As $A$ is complex symmetric, so is the augmented matrix, but there is no quasidefiniteness. You can however use the $Ax$ routine to compute $A^*x=\overline{A\overline x}$; therefore you could adapt a method such as QMR ftp://ftp.math.ucla.edu/pub/camreport/cam92-19.pdf (designed for real systems, but you can easily rewrite it for complex systems, using the adjoint in place of the transpose) to solve your problem.Edit2: Actually, the (0,1)-structure of $G$ means that you can eliminate $x$ amd the components of $G^Ty$ symbolically, thus ending up with a smaller system to solve. This means messing with the structure of $A$, and pays only when $A$ is given explicitly in sparse format rather than as a linear operator.