Polynomial Meshes and Discrete Extremal Sets

(1)

3^rdDolomites Workshop on Constructive Approximation and Applications (DWCAA12) Alba di Canazei (Trento, Italy), Sept. 9-14 2012

Polynomial Meshes and Discrete Extremal Sets

L. B

^OS^a

, S. D

^E

M

^ARCHI^b

, A. S

^OMMARIVA^b ^AND

M. V

^IANELLO^b

aDepartment of Computer Science, University of Verona, Italy ^bDepartment of Mathematics, University of Padua, Italy

Abstract

Polynomial MeshesandDiscrete Extremal Sets(computed by basic numerical linear algebra) give new tools formultivari- atepolynomial least squaresand interpolationonmultidi- mensional compact sets.

Fekete Points

K⊂ R^d(or C^d)compactset or manifold

p={pj}1≤j≤N, N = dim(P^dn(K))polynomial basis ξ={ξ1, . . . , ξN} ⊂ Kinterpolation points

V (ξ, p) = [pj(ξi)]Vandermonde matrix, det(V ) 6= 0 Πnf (x) =PN

j=1f (ξj) ℓj(x)determinantal Lagrange formula ℓj(x) = det(V (ξ1, . . . , ξj−1, x, ξj+1, . . . , ξN))

det(V (ξ1, . . . , ξj−1, ξj, ξj+1, . . . , ξN)) , ℓj(ξi) = δij

Fekete points: |det(V (ξ1, . . . , ξN))| ismaxin K^N

=⇒Lebesgue constant= Λn= max

x∈K N

X

j=1

|ℓj(x)| ≤ N

Fekete points(and Lebesgue constants) are independentof the choice of the basis

Fekete pointsare analytically known only in afew cases:

interval: Gauss-Lobatto points, Λn=O(log n) complex circle: equispaced points, Λn=O(log n) cube: for tensor-product polynomials, Λn=O(log^dn) recent important result[1]:

Fekete pointsare asymptoticallyequidistributedwith respect to the pluripotentialequilibrium measureof K

• open problem: efficient computation, even in the uni- variate complex case (large scale optimization problem in N× d variables[6])

• idea: extract Fekete points from a discretization of K:

but which could be asuitable mesh?

Polynomial Meshes

Weakly Admissible Mesh (WAM)[7]: sequence of discrete subsets An⊂ K with thepolynomial inequality

kpkK≤ C(An)kpkAn, ∀p ∈ P^dn(K)

where card(An)≥ N and C(An)grow polinomiallywith n when C(An)≡ C we have anAdmissible Mesh (AM) Properties:

• C(An) isinvariant under affine mapping

• unisolvent interpolation setswith polinomially growing Lebesgue constant are WAMs with C(An) = Λn

• WAMs with card(An) = N are unisolvent interpolation set with Lebesgue constant Λn= C(An)

• finite unions and productsof (W)AMs are (W)AMs

• Markov compacts: k∇pkK≤ Mn^rkpkK ∀p ∈ P^d_n(K) have an AM with O(n^rd) points [7]

• small perturbations and smooth transformations of (W)AMs are (W)AMs on Markov compacts [11, 12]

• low cardinality meshes with O(n^d) or O((n log n)^d) points on: polygons and polyhedra, subanalytic sets, convex and starlike domains [4, 10, 11, 12]

• near optimalityof polynomialLeast Squareson a WAM kf − LAnfkK≈ C(An)pcard(An) En(f ; K) , f∈ C(K)

• Fekete pointsextracted from a WAM have a Lebesgue constant Λn≤ NC(An) (but often much smaller!)

Discrete Extremal Sets

extractingFekete points from WAMs, An= a ={a1, . . . , aM} m

discrete optimization problem:

extracting amaximum determinantN× N submatrix from the M × N Vandermonde matrix V = V (a, p) = [pj(ai)]

this isNP-hard: then we look for anapproximate solution;

surprisingly, this can be obtained by basic numerical linear algebra!

we compute two kinds of suchDiscrete Extremal Sets:

•Approximate Fekete Points

•Discrete Leja Points

Key asymptotic result(cf. [2, 3]): Discrete Extremal Setsex- tracted from a WAM by the greedy algorithms below have thesame asymptotic behaviorof the true Fekete points

1 N

N

X

j=1

f (ξj)−−−→^{N →∞}

Z

K

f (x) dµK, ∀f ∈ C(K)

where µKis theequilibrium measureof K

Approximate Fekete Points

algorithm greedy 1 (AFP, Approximate Fekete Points)

• V = V (a, p); ind = [ ];

• for k = 1 : N

“select ik: vol V ([ind, ik] , 1 : N) is max”; ind = [ind, ik];

end

• ξ = a(i1, . . . , iN)

method:greedy maximization of submatrix volumes

iteration core: subtractfrom each row itsorthogonal projec- tiononto thelargest normone (preserves volumes like with parallelograms)

implementation: QR factorization with column pivoting (Businger and Golub, 1965) applied to V^t

feature: AFP areindependentof theorderof the basis Matlab script:

w= V^′\ones(1 : N) ; ind = find(w 6= 0); ξ = a(ind)

Discrete Leja Points

algorithm greedy 2 (DLP, Discrete Leja Points)

• V = V (a, p); ind = [ ];

• for k = 1 : N

“select ik: |det V ([ind, ik] , 1 : k)| is max”; ind = [ind, ik];

end

• ξ = a(i1, . . . , iN)

method:greedy maximization of nested subdeterminants iteration core: one column step of Gaussian elimination withrow pivoting(preserves the relevant subdeterminants) implementation:LU factorization with row pivoting

feature: DLP depend on the order of the basis and form asequence

in one variable DLP correspond to the usual notion:

ξk= argmax_z∈An

Qk

j=1|z − ξj| , k = 2, . . . , N

Matlab script:

[L, U, σ] = LU(V, “vector”); ind = σ(1 : N); ξ = a(ind)

Multivariate examples

•Polygon WAMs: bytriangulation/quadrangulation

=⇒ M = card(An) =O(n²) and C(An) =O(log²n) FIGURE1.Left:N = 45 AFP (◦) and DLP (∗) of an hexagon for n = 8 from the WAM (dots) obtained bybilinear transformationof a 9 × 9 product Chebyshev grid on two convex quadrangle elements (M = 153 pts);

Right:N = 136 AFP (◦) and DLP (∗) for degree n = 15 in a hand shaped polygon with 37 sides and a 23 element quadrangulation (M ≈ 5500).

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

TABLE 1. Hexagon: interpolation and Least Squares operator norm (Lebesgue const.) andapproximation errorsfor the Franke test function.

n = 5 n = 10 n = 15 n = 20 n = 25 n = 30 intp AFP 8.1 14.5 35.7 56.0 97.7 87.0 intp DLP 8.0 32.0 48.5 92.8 107.4 198.7

LS WAM 3.4 4.5 5.3 6.0 6.6 7.3

intp AFP 2E-01 2E-02 6E-03 6E-04 4E-05 1E-06 intp DLP 2E-01 6E-02 6E-03 5E-04 1E-04 4E-06 LS WAM 7E-01 2E-01 3E-02 4E-03 3E-04 1E-05

Developments and Applications

•algebraic cubature[9]

•transformation and perturbation of (W)AMs[2, 11, 12]

•computing ”true” Fekete and Lebesgue points[6, 13]

•numerical PDEs: spectral elements [13], collocation [14]

•surface/solid (W)AMs: polyhedra, cones, spherical and toroidal sections, ...

Highlight[5, 8]: the 2n + 1 angles θj = 2 arcsin (tjsin (ω/2)), T2n+1(tj) = 0, arenear optimalfortrigonometric interpolation in [−ω, ω] ⊆ [−π, π] (and have positive quadrature weights!)

=⇒subarc-based product WAMson sections of disk, sphere, ball, torus, such as circularsectorsandlenses, sphericalcaps andquadrangles,lunes,slices, ..., with card(An) =O(n^k) and C(An) =O(log^kn) (k = 2 for surfaces and k = 3 for solids) FIGURE2. Left: WAM of a sector (ω = 2π/3) for n = 5 (blue, M = 61) and N = 21 AFP (red); Right: WAM of a solid torus section (ω = 2π/3) for n = 5 (union of 11 disk WAMs, blue, M = 396) and N = 56 AFP (red).

References

[1] R. BERMAN, S. BOUCKSOM ANDD. WITTNYSTROM¨ , Fekete points and convergence to- wards equilibrium measures on complex manifolds, Acta Math. 207 (2011).

[2] L. BOS, J.-P. CALVI, N. LEVENBERG, A. SOMMARIVA ANDM. VIANELLO, Geometric Weakly Admissible Meshes, Discrete Least Squares Approximation and Approximate Fekete Points, Math. Comp. 80 (2011).

[3] L. BOS, S. DEMARCHI, A. SOMMARIVA ANDM. VIANELLO, Computing multivariate Fekete and Leja points by numerical linear algebra, SIAM J. Numer. Anal. 48 (2010).

[4] L. BOS ANDM. VIANELLO, Low cardinality admissible meshes on quadrangles, triangles and disks, Math. Inequal. Appl. 15 (2012).

[5] L. BOS ANDM. VIANELLO, Subperiodic trigonometric interpolation and quadrature, Appl.

Math. Comput. 218 (2012).

[6] M. BRIANI, A. SOMMARIVA ANDM. VIANELLO, Computing Fekete and Lebesgue points:

simplex, square, disk, J. Comput. Appl. Math. 236 (2012).

[7] J.P. CALVI ANDN. LEVENBERG, Uniform approximation by discrete least squares polynomials, J. Approx. Theory 152 (2008).

[8] G. DAFIES ANDM. VIANELLO, On the Lebesgue constant of subperiodic trigonometric interpolation, 2012, submitted.

[9] M. GENTILE, A. SOMMARIVA ANDM. VIANELLO, Polynomial interpolation and cubature over polygons, J. Comput. Appl. Math. 235 (2011).

[10] A. KROO´, On optimal polynomial meshes, J. Approx. Theory 163 (2011).

[11] F. PIAZZON ANDM. VIANELLO, Small perturbations of polynomial meshes, Appl. Anal., published online 18 January 2012.

[12] W. PLESNIAK´ , Nearly optimal meshes in subanalytic sets, Numer. Algorithms 60 (2012).

[13] F. RAPETTI, A. SOMMARIVA ANDM. VIANELLO, On the generation of symmetric Lebesgue- like points in the triangle, J. Comput. Appl. Math. 236 (2012).

[14] P. ZITNAN, The collocation solution of Poisson problems based on approximate Fekete points, Eng. Anal. Bound. Elem. 35 (2011).