Efficient algorithms for solving the p -Laplacian in polynomial time
- PDF / 1,962,085 Bytes
- 32 Pages / 439.37 x 666.142 pts Page_size
- 102 Downloads / 234 Views
Numerische Mathematik https://doi.org/10.1007/s00211-020-01141-z
Efficient algorithms for solving the p-Laplacian in polynomial time Sébastien Loisel1 Received: 15 August 2018 / Revised: 19 March 2020 © The Author(s) 2020
Abstract The p-Laplacian is a nonlinear partial differential equation, parametrized by p ∈ [1, ∞]. We provide new numerical algorithms, based on the barrier method, for solv√ ing the p-Laplacian numerically in O( n log n) Newton iterations for all p ∈ [1, ∞], where n is the number of grid points. We confirm our estimates with numerical experiments. Mathematics Subject Classification 65H20 · 65N22 · 90C25
1 Introduction Let ⊂ Rd . For 1 ≤ p < ∞, the p−Laplace equation is p−2
∇ · (∇v2
∇v) = f in and v = g on ∂,
(1)
1/2 d 2 where w2 = is the usual 2−norm on Rd . Prolonging g from ∂ j=1 |w j | to the interior and setting u = v − g, the variational form is 1, p
Find u ∈ W0 () such that J (u) =
1 p
p
∇(u + g)2 −
f u is minimized. (2)
A similar definition can be made in the case p = ∞ and will be discussed in Sect. 3.1. For p = 1, the p-Laplacian is also known as Mean Curvature, and a solution with f = 0 is known as a minimal surface [31]. The 1-Laplacian is related to a certain “pusher-chooser” game [19] and compressed sensing [7]. The general p-Laplacian is
B 1
Sébastien Loisel [email protected] Department of Mathematics, Heriot-Watt University, Riccarton EH14 4AS, UK
123
S. Loisel
used for nonlinear Darcy flow [11], modelling sandpiles [2] and image processing [8]. We also mention the standard text of Heinonen et al. [16]; as well as the lecture notes of Lindqvist [21]. One may discretize the variational form (2) using finite elements; we briefly outline this procedure in Sect. 2.1 and refer to Barrett and Liu [3] for details. One chooses piecewise linear basis functions {φ j (x)} on and we let u h (x) = j u j φ j (x). The energy J (u h ) can be approximated by quadrature; the quadrature is exact if the elements are piecewise linear. This leads to a finite-dimensional energy functional Find u ∈ Rn such that J (u) = c T u ⎛ ⎞p 2 m d 1 ( j) ( j) 2 ⎠ ⎝ ωi (D u + b )i is minimized, + p i=1
(3)
j=1
where D ( j) is a numerical partial derivative, b( j) = D ( j) g comes from the boundary conditions g and c comes from the forcing term f . Several algorithms have been proposed to minimize the convex functional J (u). Huang et al. [18] proposed a steepest descent algorithm on a regularized functional Jh, (u) which works well when p > 2. Tai and Xu [36] proposed a subspace correction algorithm which works best when p is close to 2 but whose convergence deteriorates when p → 1 or p → ∞. Algorithms based on a multigrid approach (e.g. Huang et al. [9]) suffer from the same problems when p approaches 1 or ∞. The algorithm of Oberman [30] also works for p ≥ 2, although the convergence factor deteriorates after several iterations so it is difficult to reach high accuracy with this method. The problem of minimizing J (u) has much in common with the problem of
Data Loading...
