5
$\begingroup$

I have a linear system $$Ax=b$$ which I'm solving approximately, and I need to take the frechet derivative of x with respect to z. Were I solving the problem exactly (either analytically or to machine 0) I'd simply say $$\frac{dx}{dz}\vec{v} = \frac{d A^{-1}b}{dz}\vec{v} = \left(\frac{dA}{dz}A^{-1}\frac{dA}{dz}b + A^{-1}\frac{db}{dz}\right)\vec{v}$$ Since I am not solving the system exactly (2 orders of accuracy say), I thought the best way to get the sensitivity, would be a complex perturbation to the linear system. I.e, solve the linear system, but where it is: $$A(z+i\epsilon {v})x = b(z+i\epsilon\vec{v})$$ And I could then take the imaginary part of x. Will this work the way I want it to? Then if I wanted the adjoint differentiation, of the linear solve, would I give a complex perturbation to the matrix and transpose it?

This is related to my previous question posted here: Derivatives of Approximate Matrix inverses

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ It would be useful to have more detail on how you are actually solving the system. The value of the derivative will surely depend on that. $\endgroup$ – Federico Poloni Jul 4 '19 at 9:31
  • $\begingroup$ Also, have you tried automatic differentiation? $\endgroup$ – Federico Poloni Jul 4 '19 at 9:31
  • $\begingroup$ I'm solving it approximately with a point block Jacobi iteration. AD is impractical, and not what I need, as I just need the derivative of the linear system unknown multiplied by a vector. Which is why I suggested the vector perturbation to the linear system solve. $\endgroup$ – EMP Jul 4 '19 at 20:50
1
$\begingroup$

It does indeed work to linearize the forward mode this way, and will correspond to machine precision. The reverse or adjoint mode doesn't work this way despite my wishes to the contrary. The derivation I posted doesn't correspond exactly to machine precision, but the numerical tests I did showed that the magnitude of the error depends on the linear tolerance of the approximate linear solve and the magnitude of the right hand side.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Missed this question the first time around, but this would seem to be related to the method described here: blogs.mathworks.com/cleve/2013/10/14/… $\endgroup$ – rchilton1980 Dec 5 '19 at 20:37
  • $\begingroup$ Yea it's exactly complex differentiation but of a process rather than an analytic function and I wasn't sure how it would work with state dependent convergence criteria and the like. Turns out it works well, and more interestingly to me you can use complex differentiation with the derivation I posted to get a decent estimate. Thanks for the reference! I'm only familiar with the Martins paper, didn't realize it came from Moler. $\endgroup$ – EMP Dec 5 '19 at 21:03

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.