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

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.

13 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

Thank you for the great packages. I needed to solve a PDE a few year ago but at that time I couldn’t find these packages. The NLsolve.jl did not work on my large problem. I’m glad to see there is more than one package now which can provide Newton-Krylov method. This is big progress.

I’ve just tagged v0.4.3 of SIAMFANLEquations.jl. This is a suite of nonlinear solvers, test problems, and examples. Chapter 4 is Anderson acceleration, which is the new material since v0.3.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

The notebooks are a faithful reproduction of the entire book.

This version includes the draft of Chapter 4: Fixed Point Problems and Anderson Acceleration

I have decided to take my own advice from the middle of the discussion in

and leave Broyden’s method out. So, the solvers are done.

The last chapter will be Chapter 5: Case Studies.

8 Likes

I’ve just tagged v0.5.3 of SIAMFANLEquations.jl.

This is a suite of nonlinear solvers, test problems, and examples. Chapter 5 is Case Studies, which is the new material since v0.4.3. Chapter 5 is the last chapter.

The case studies are more elaborate examples than those in the rest of the
text.

  1. Conductive-Radiative heat transfer is a multiphysics coupling problem.

  2. Pseudo-arclength continuation for the H-equation

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 (I hope).

The solvers are documented with Documenter.jl on the github repo and with a collection of IJulia notebooks

The notebooks are a more-or-less faithful reproduction of the entire book.

This version includes Chapter 5: Case Studies

I will not be announcing new versions on Discourse until 1.0 unless I find a significant bug.

Future versions will focus on updating the written material for publication, fixing bugs, and improving the internal documentation for the codes.

0.6.0: announcement to NA-Digest
0.7.0: print book to publisher for copy editing
0.8.0: fix problems the copy editor finds. Print book is done at this point.
0.9.x: last shot at getting the notebooks and codes where I want them
1.0: Fin

9 Likes