Efficient algorithms for solving the $p$-Laplacian in polynomial time

Abstract

The $p$-Laplacian is a nonlinear partial differential equation, parametrized by $p\in [1,\infty ]$. We provide new numerical algorithms, based on the barrier method, for solving the $p$-Laplacian numerically in $O(\sqrt{n}\log n)$ Newton iterations for all $p\in [1,\infty ]$, where $n$ is the number of grid points. We confirm our estimates with numerical experiments.

28 pages, 3 figures