Collaborators
Projects
Theory of Robust Solution for Nonlinear Problems
ProblemDiscretization of continuum physics problems, and related optimization problems, generates large, sparse nonlinear systems of algebraic equations. The solution of these systems can be very challenging, and few rules-of-thumb exist for designing robust solvers, in sharp distinction to the linear case.
ApproachThe theory of non-discrete induction (NDI) offers the possibility of predicting short-time (non-asymptotic) convergence behavior for complex, multi-solver nonlinear iterations. We will apply this theory to the composition of nonlinear solvers, termed nonlinear preconditioning in our SIAM Review article, and create simple rules for assembling robust nonlinear solvers by composition, in analogy with the quite successful practice in the linear case.
ImpactAn effective theory for composition of nonlinear solvers would be a powerful step toward automation of predictive modeling and simulation in modern engineering. Integrated into modeling platforms such as Fluent and ABAQUS, in which PETSc already resides, it could automatically solve models far in the nonlinear regime, currently inaccessible to users, which would be a necessity for future systems such as fusion power.
PlanIn the PETSc libraries, we have already implemented a flexible system allowing composition of nonlinear iterations, enabling easy construction of optimal multilevel solvers for real-world physical systems. We have preliminary results using NDI to predict convergence rates, verified in one dimension. We will extend our theory to Banach spaces, and obtain empirical results from simple multiphysics systems, such as Stokes flow and viscoplastic extensions.
- Understand what Rolf Krause (USI) and Hans De Sterck (Monash) are doing
- Understand Nesterov Acceleration This explains how optimizers think of steepest descent. It does not match the numerical analysis treatment, so first we have to translate. This explains the speedup you get with Nesterov. I think it is just NPC.
- Robust Nonlinear Solvers
Why do nonlinear solvers diverge? In general, this is obviously a very difficult question to answer. However, let us restrict consideration to a nonlinear PDE with two different discretizations of resolution \(H\) and \(h\). Suppose we can find the solution \(u_H\) to the coarse equation using some method. We then project this solution up to the fine grid, \(P u_H\), and two questions are apparent. How large can the residual \(F(P u_H)\) be, or equivalently how far can coarsening move the solution? Could a perfect projection give us the solution on the fine grid?
The second question suggests looking for a homotopy from the coarse equations to the fine equations. If the prologation followed this homotopy, we would indeed have the solution automatically. Perhaps we can approximate a homotopy well enough such that we can guarantee Newton convergence after the prolongation.
Since we know that for FAS at convergence, \(u_H = u_h\) on the coarse points, we could look at the change in the norm of \(\tau\) to judge how close we are to convergence.
Jed has objected that there are many effects that may not show up on the coarse grid at all, such as buckling or turbulence and thus how can we expect this kind of a method to work. I would like to concentrate on plasticity since I think I understand that better, and I believe buckling is similar (I know nothing about turbulence). Plasticity use a maximum stress condition, so that if I do not reach the threshold stress there is no failure. Since higher energies are available on the fine grid, a condition like this could fail to be met on the coarse grid but be satisifed on the fine grid. This, to me, is the analogue of the renormalization approach in that each grid has a certain energy resolution. These effect would be local, so my coarse solution is still accurate for coarse scales, but behavior like this could threaten a homotopy between the solutions on coarse and fine scales.
During the run, I thought we could do a two scale decomposition of some nice nonlinear problem. We need to know the cnostants defining the convergence region for both scales (we can stick with the guaranteed ball ratehr than actual convergence), and then the effect of prolongation of the coarse solution. I think there is a prayer of showing in a simple case that you can get convergence of FAS. Go over the papers I got, especially the 2014 one.
- Why does FAS converge?
This is connected to the Nash-Moser iteration. It has been explained in the note by Terrence Tao as an interplay between norms encompassing different frequencies.
In Nash-Moser, we think of the Newton step as introducing high frequencies due to the loss of smoothness. We then have to smooth these frequencies away to maintain the Newton convergence. Suppose that we decompose a problem in spatial frequencies for FAS. We solve on the coarse grid, and then interpolate up. This introduces high frequencies. Can we prove Newton convergence by smoothing and using a Nash-Moser framework?
I have introduced a SNESCLS, but it does not work at all. There is theory about inexact solves, but the tolerance must decrease exponentially (I think). Would that mean that one iterate is done per grid? More fundamentally, if Newton converges superlinearly, it will outstrip the decrease in discretization error unless the grid refinement ratio also grows.
- Multilevel Optimization and How do LCM problem converge?
The paper by Potra gives a Kantorovich proof for LCM, which shows how Newton works.
We still need to understand what multiple levels would give us. This is connected to the first question in that superlinear convergence seems incompatible with a fixed grid refinement ratio.
I see two potential avenues for improvement. The first is using FAS, since the coarse operator becomes more accurate. Second, the use of nonlinear prolongation which can preserve properties of the iteration, such as distance to the central path. I see the convergence proof here as similar to the Nash-Moser theorem, in that they needed to prove that smoothing did not destroy Newton convergence, while we need to prove that nonlinear prolongation does not destroy multigrid convergence, which I think needs and energy estimate and a perturbation bound on the coarse solution.
- Explanation of left/right divide between Anderson and NGMRES
- Implement efficient NGS and try out on magma
- Compare NGMRES+FAS/LGS vs FAS/NGS for p=5 p-Lap
- HOLO algorithms like the one's presented by Ryuoske and Luis Chacon do not reduce work, but rather take advantage of the structure of mode coupling to produce a method with all the desirable characteristics (stability, exact conservation) which runs in lower memory. I think memory reduction will be a key aspect going forward.