Efficient algorithms for solving the p-Laplacian in polynomial time
Sébastien Loisel
Abstract
Abstract The p -Laplacian is a nonlinear partial differential equation, parametrized by $$p \in [1,\infty ]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>[</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mi>∞</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> . We provide new numerical algorithms, based on the barrier method, for solving the p -Laplacian numerically in $$O(\sqrt{n}\log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msqrt> <mml:mi>n</mml:mi> </mml:msqrt> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> Newton iterations for all $$p \in [1,\infty ]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>[</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mi>∞</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> , where n is the number of grid points. We confirm our estimates with numerical experiments.