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?
  • 5
    $\begingroup$ 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. $\endgroup$
    – GoHokies
    Sep 19, 2017 at 19:52
  • 2
    $\begingroup$ 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$. $\endgroup$
    – GoHokies
    Sep 19, 2017 at 20:30
  • $\begingroup$ 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. $\endgroup$ Sep 19, 2017 at 23:06
  • 4
    $\begingroup$ The MINRES methods require $A$ to be symmetric (in which case all methods are effectively transpose free...) $\endgroup$ Sep 20, 2017 at 2:27
  • 1
    $\begingroup$ @GoHokies Reverse-mode AD requires excessive memory in my application. Beyond the point of being reasonably used. $\endgroup$
    – bfletch
    Sep 20, 2017 at 16:33


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.