The current version is 0.2.3 and has Newton-like scalar equation solvers and solvers for systems with direct methods for the linear algebra. The methods include mixed-precision solvers and pseudo-transient continuation as well as the usual suspects.
Newton-Krylov methods, Anderson acceleration, and Broyden’s method are coming sometime in 2021.
Very cool, thanks for contributing this! I love this “one book = one julia package” thing
Newton-Krylov methods, Anderson acceleration, and Broyden’s method are coming sometime in 2021.
Looking forward to trying this out! In particular we have an anderson solver and some variants coded up that I’d love to benchmark seriously against other methods sometimes, so that’ll be a good opportunity.
Anderson will happen in the first half of 2021. I plan on putting plain vanilla in the package. EDIIS and CDIIS are not general purpose and EDIIS is really tricky to implement well. I have a paper on EDISS and the computations could not use the usual suspects for the backend.
I’m hoping to implement Anderson the way it’s done in Trilinos. One of my students did that and I’m planning to use his thesis work.
Since you’re interested in the many Anderson variants (I knew about the paper on the analysis of EDIIS, didn’t connect it was you :-)), the other one that I know of is the very fun CROP (https://github.com/JuliaMolSim/DFTK.jl/blob/master/src/scf/scf_solvers.jl#L105), which I took from an extremely nice paper that nobody read (and which we’re currently analyzing and trying out with @mfh).
I knew that NLSolvers had Anderson in the works. I have not played with it. Anderson is really a pretty simple algorithm and may people have implemented it. The implementations in some, but not all, of the physics code use the normal equations for the least squares problem and still get good results. That’s another thing I want to understand.
I’m interested in CROP. That and CDIIS are on my life list to figure out. If you make progress, please send me a link to the paper.
The Anderson in nlsolve is pretty careful (I did the first basic implementation a few years ago, then @devmotion added incremental updating of the QR factorization).
CROP is essentially a nonlinear MINRES. The troubling part for me is that CROP/MINRES seems to work quite well even on non-hermitian systems, which is what we’re trying to understand.
Regarding CDIIS, I think the general idea is that for projection methods, the expansion subspace is much more important than the test subspace (unless your problem is horribly ill-conditioned, in which case you don’t want to be doing anderson anyway). So whether you use the energy gradient (in CDIIS) or the fixed-point residual (in anderson) for your error criterion doesn’t matter too much.
Regarding implementations, it does seem that Anderson is much more robust than it has any right to be; for instance, even a very naive implementation that routinely inverts extremely ill-conditioned subspace matrices is still usually OK. My guess is that, again for relatively nice problems, what really matters is not screwing up on the latest iterates, on which the matrix is much better conditioned. That’s also an interesting thing to look at, but I spent a year of my life trying to prove things about the behavior of Anderson and promised myself I would never go back there again
Anyway, I didn’t want to hijack the discussion about the package…
Cool. Thanks for starting (and communicating) this project, directly providing code examples and documentation. It will be good to have a goto reference of algorithms and test problems at hand for future research.
Regarding our work in quantum chemistry indeed many algorithms (all the DIISes) are empirically motivated and historically very much driven by “what works” and not so much by design. Coming from that angle I’m curious how you will present the material in a uniform mathematical framework. It’s not at all easy to find a good, comprehensive and consistent overview about these methods in the literature. I’m looking forward to seeing your material develop!
It’ll be plain vanilla, as I said to @antoine-levitt. My research papers do more than that, but getting into the weeds is a different book (one I’d happily buy!).
We have worked years ago in rigorous methods for solving the HF equations. I think we provided some insights into classical methods in this work.
But we never had the possibility to implement those in state of the art computational chemistry packages. Maybe these methods are interesting in this context.
If I remember correctly the work of Cances and Le Bris also brought some rigour to these heuristics. If I am not mistaken their method became implemented in Gaussian.
If I remember correctly the work of Cances and Le Bris also brought some rigour to these heuristics. If I am not mistaken their method became implemented in Gaussian.
Yeah I know, I’m in the same lab as them I also worked on this topic. Nice to see that Julia is becoming a magnet for people interested in this kind of things!
From your name I suspected that. We do not work on that anymore, neither I nor my father (J. M. Martinez) were specialist in quantum chemistry, it was a fortunate collaboration. We met Cances at Rouen in 2007 (I was a postdoc at the Institute Pasteur then). Today I mentioned this book of @ctkelley to my father, and he happened to know him from scientific meetings as well, he mentioned his other great book using Matlab algorithms. It is a small world.
I’ve finished v0.3.3 of SIAMFANLEquations.jl. This is a suite of nonlinear solvers, test problems, and examples. Newton-Krylov solvers are the new stuff since v0.2.3
This package supports my book project
Solving Nonlinear Equations with Iterative Methods: Solvers and Examples in Julia
which will be published by SIAM in 2022.
The solvers are documented with Documenter.jl on the github repo and
with a collection of IJulia notebooks at
This version includes the draft of Chapter 3: Newton-Krylov solvers.
Anderson acceleration and Broyden’s method are coming sometime in 2021.
I’m glad to see this package, which has an implementation of Newton-Krylov method. scipy has the Newton-Krylov method and it is efficient for large scale problems. As far as I know, this is the first package in julia which contains this method.
Sorry I should not have missed your package.
The reason it did not come to my head is that this package focus on bifurcation problems.
Could you please add an simple example about how to solve a nonlinear equation F(\mathbf{x})=0?
Maybe this is very basic, but it’s valuable for beginners like me.
Thanks for clarifying!