[petsc-dev] MATLMVM

[Dener, Alp]

Sure. Symmetric Broyden is defined as the convex linear combination of BFGS and DFP updates such that SymBrdn = (1-phi)BFGS + phi*DFP with phi in range of [0, 1]. It is possible, mathematically, to produce both BFGS and DFP applications out of the single Symmetric Broyden object. However, in the two extreme cases where phi = 0 and phi = 1, the pure BFGS and pure DFP updates can be implemented much more efficiently than the Symmetric Broyden formula. Specifically, the BFGS inverse action and the DFP forward action can be unrolled into a two-loop algorithm that significantly reduces dot products and and AXPBY operations compared to the Symmetric Broyden formula with the matching phi scalar. Furthermore, BFGS and DFP implementations require about 25% fewer storage vectors than Symmetric Broyden because they don’t need to carry around the extra information required for the other extreme. Similar benefits apply to the SR-1 method, which is actually also part of the Symmetric Broyden family, except with a dynamically calculated phi value (based on dot products with update vectors) that lie outside the range of [0, 1]. Implementing it on its own allows for explicitly cancelling out some terms in the update, reducing it to a rank-1 formula instead of the rank-2 formula in Symmetric Broyden, and apply it far more efficiently.

It’s possible for all of these to be offered inside Symmetric Broyden with checks on a subtype or the phi value that direct the operations into the correct special case, but that doesn’t reduce the amount of code that needs to be written to maintain the efficiency. And if you wanted to really have minimal code that does everything out of the Symmetric Broyden update formula just to have minimal amount of code, then the special cases would be performing a lot of unnecessary operations that could (and should) have been eliminated.

Does that explain it better?
——
Alp Dener
Argonne National Laboratory
http://www.mcs.anl.gov/person/alp-dener










On Sep 11, 2018, at 2:21 PM, Jed Brown <jed at jedbrown.org<mailto:jed at jedbrown.org>> wrote:

"Dener, Alp" <adener at anl.gov<mailto:adener at anl.gov>> writes:

The two basic Broyden methods can indeed bet combined into one object
easily, but that’s not as true for other subtypes. Mathematical
formulations differ significantly between BFGS, DFP, symmetric Broyden
and SR1 methods. They can be combined on paper, because they’re all
symmetric Broyden-class of updates. However, doing so causes BFGS, DFP
and SR1 to have inflated memory footprints and additional algebra
operations that they don’t actually need.

Can you explain further or give a reference?

Eliminating those in a single object requires either a lot of ugly
conditionals/switches, or playing with function pointers. Doing the
latter basically gets us 99% of the way to separating them into
different objects though, which is what the current implementation
does.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20180911/c451024f/attachment.html>