标题： 算法MGB用于在$\tilde{O}(n)$中求解高度非线性椭圆偏微分方程的FLOPS 显示英文标题

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

摘要： 我们引入了算法MGB（多网格屏障）来求解高度非线性的凸欧拉-拉格朗日方程。 这类问题包括许多高度非线性的偏微分方程，例如$p$-拉普拉斯算子。 我们证明，如果满足某些正则性假设，则我们的算法在$\tilde{O}(1)$次阻尼牛顿迭代中收敛，或在$\tilde{O}(n)$次浮点运算中收敛，其中波浪号表示我们忽略了某些多项对数项。 这是第一个运行时间在大-$\tilde{O}$意义下被证明最优的算法。 以前针对$p$-拉普拉斯算子的算法需要$\tilde{O}(\sqrt{n})$次阻尼牛顿迭代或更多。 显示英文摘要

摘要： 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 $\tilde{O}(1)$ damped Newton iterations, or $\tilde{O}(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-$\tilde{O}$ sense. Previous algorithms for the $p$-Laplacian required $\tilde{O}(\sqrt{n})$ damped Newton iterations or more.