# Solve ill-posed linear system without transposing matrices?

I am attempting to use an iterative solver to solve $$p$$ in

$$Jp = -r$$

where $$J$$ is an $$m\times m$$ matrix ($$m$$ is in the order of $$10^5$$ and never explicitly stored). $$J$$ is a dense matrix representing a Jacobian for a certain function, and, in general, is not symmetric.

Unfortunately, this is an ill-posed problem and possibly infinite versions of $$p$$ exist.

I cannot compute the least-squares version

$$J^TJp=J^Tr$$

because I only can access the product of $$Jp$$ and not $$J^Tp$$ (a limitation of an automatic differentiation approach I am taking).

• Is there a way I can compute $$p$$ in $$Jp = -r$$ according to some criterion (e.g. least-squares solution) without transposing $$J$$?
• If I use an iterative solver (e.g. GMRES, BiCGStab, etc...) with an initial guess of $$p=0$$, what solution will the solver converge to? The minimum-norm?
• is $J$ sparse? if so, are you familiar with the MINRES family of solvers? if you're looking for the min-length solution, then MINRES-QLP may be a good option for your problem. – GoHokies Sep 19 '17 at 19:52
• as a side-comment, why is automatic differentiation limiting your options when it comes to $J^T$? If $J$ is the Jacobian of some $m$-variable (and at least locally smooth) function $f$, then reverse-mode AD gives you $J^T p$ for any direction $p$. – GoHokies Sep 19 '17 at 20:30
• Independently of the question of what solver to use, it is important to ask whether $r$ is in the image space of $J$? Because, if it is not, then whatever solver you use will not converge to a solution of $Jp=-r$ because the equation does not have a solution. – Wolfgang Bangerth Sep 19 '17 at 23:06
• The MINRES methods require $A$ to be symmetric (in which case all methods are effectively transpose free...) – Brian Borchers Sep 20 '17 at 2:27
• @GoHokies Reverse-mode AD requires excessive memory in my application. Beyond the point of being reasonably used. – bfletch Sep 20 '17 at 16:33