Algorithm MGB to solve highly nonlinear elliptic PDEs in \tilde{O}(n) FLOPS

arXiv2306.10183MaRDI QIDQ6440591FDOQ6440591

Authors: Sébastien Loisel 

Publication date: 16 June 2023

Abstract: We introduce Algorithm MGB (Multi Grid Barrier) for solving highly nonlinear convex Euler-Lagrange equations. This class of problems includes many highly nonlinear partial differential equations, such as $p$-Laplacians. We prove that, if certain regularity hypotheses are satisfied, then our algorithm converges in $ildeO(1)$ damped Newton iterations, or $ildeO(n)$ FLOPS, where the tilde indicates that we neglect some polylogarithmic terms. This the first algorithm whose running time is proven optimal in the big-$ildeO$ sense. Previous algorithms for the $p$-Laplacian required $ildeO(sqrtn)$ damped Newton iterations or more.

This page was built for publication: Algorithm MGB to solve highly nonlinear elliptic PDEs in $\tilde{O}(n)$ FLOPS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6440591)