[ANN] SIAMFANLEquations.jl: Nonlinear solvers and book project

I just registered GitHub - ctkelley/SIAMFANLEquations.jl: This is a Julia package for a book project.

This is a suite of nonlinear solvers, test problems, and examples.

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: GitHub - ctkelley/NotebookSIAMFANL: Notebook for my new solver book

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.

22 Likes

Very cool, thanks for contributing this! I love this “one book = one julia package” thing :slight_smile:

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.

4 Likes

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.

1 Like

I assume you know about https://github.com/JuliaNLSolvers/NLsolve.jl/blob/master/src/solvers/anderson.jl?

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).

1 Like

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.

1 Like

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 :slight_smile:

Anyway, I didn’t want to hijack the discussion about the package…

2 Likes

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!

3 Likes

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!).

The bib in the book will be pretty decent.

3 Likes

Ah sorry, I overread that half sentence in your answer :smile: Thanks for clarifying!

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.

2 Likes

Yup. That’s the plan. I will probably do a chain-saw implementation first to get the chapter done and then do it right as the last thing.

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 :slight_smile: I also worked on this topic. Nice to see that Julia is becoming a magnet for people interested in this kind of things!

3 Likes

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.

3 Likes

I was wondering if the J. M. Martinez was the one I know. Small world indeed! Tell him hello for me.

3 Likes

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.

12 Likes

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.

Thank you!

Well, shameless plug: BifurcationKit.jl. It has perhaps less newton functionalities but it surely works in high dimensions on GPUs for example

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.

Try working through the first two chapters in my notebooks at

There are examples showing you how to use my codes.

There are also some simple examples in the docstrings for all the solvers. Try typing

? nsol

at the REPL prompt. You’ll need to have SIAMFANLEquations.jl installed, of course.

1 Like

No worries :relaxed:

Actually, there are several different newton solvers in BifurcationKit.jl

  • a “basic” newton Krylov one
  • a deflated newton Krylov one (to find many zeros and not just one)
  • a Gauss-newton Krylov one (soon to be pushed)

This is the simplest example, at the end, you have a preconditioned GMRES example.

You have an example on GPU with Matrix-Free pre-condtioned GMRES and FFTs.

You have a 3d PDE example with preconditioned GMRES solver

There are also more elaborated examples for computing periodic orbits with Matrix-Free methods, you can find them in the tutorials.

The largest example I have used this for my research is 1e7 unknowns on GPU.

You have also the juliacon video

4 Likes