Oslo,2April2009 StefanoDeMarchi Paduapoints:theory,computationandapplications

(1)

Motivations and aims From Dubiner metric to Padua points Padua points and their properties Interpolation Cubature Numerical results

Padua points: theory, computation and applications ^∗

Stefano De Marchi

Department of Computer Science, University of Verona

Oslo, 2 April 2009

∗Joint work with L. Bos (Calgary), M. Caliari (Verona), A. Sommariva and M. Vianello (Padua), Y. Xu (Eugene)

(2)

Outline

1

Motivations and aims

2

From Dubiner metric to Padua points

3

Padua points and their properties

4

Interpolation

5

Cubature

6

Numerical results

(3)

Motivations and aims

Well-distributed nodes: there exist various nodal sets for polynomial interpolation of even degree n in the square Ω = [−1, 1]

²

(

^C.DeM.V.,

AMC04

), which turned out to be equidistributed w.r.t. Dubiner metric (

^{D., JAM95}

) and which show optimal Lebesgue constant growth.

Efficient interpolant evaluation: the interpolant should be constructed without solving the Vandermonde system whose complexity is O(N

³

), N =

ⁿ⁺²₂

for each pointwise evaluation. We look for compact formulae.

Efficient cubature: in particular computation of cubature weights for

non-tensorial cubature formulae.

(4)

The Dubiner metric

The Dubiner metric in the 1D:

µ

[−1,1]

(x, y ) = | arccos(x) − arccos(y)|, ∀x, y ∈ [−1, 1] . By using the Van der Corput-Schaake inequality (1935) for trig. polys.

µ

[−1,1]

(x, y ) := sup

kPk∞,[−1,1]≤1

1 deg(P) | arccos(P(x)) − arccos(P(y))| , with P ∈ P

ⁿ

([−1, 1]).

This metric generalizes to compact sets Ω ⊂ R

^d

, d > 1:

µ

_Ω

(x, y) := sup

kPk∞,Ω≤1

1 (deg(P)) | arccos(P(x)) − arccos(P(y))| .

(5)

The Dubiner metric

Conjecture(C.DeM.V.AMC04):

Nearly optimal interpolation points on a compact Ω are asymptotically equidistributed w.r.t. the Dubiner metric on Ω.

Once we know the Dubiner metric on a compact Ω, we have at least a method for producing ”good” points. Letting x = (x

1

, x

2

), y = (y

1

, y

2

)

Dubiner metric on the square:

max{| arccos(x

¹

) − arccos(y

¹

)|, | arccos(x

²

) − arccos(y

²

)|} ; Dubiner metric on the disk:

arccos

x

1

y

1

+ x

2

y

2

+ q

1 − x

1²

− x

2²

q

1 − y

1²

− y

2²

;

(6)

Dubiner points and Lebesgue constant

496 Dubiner nodes (i.e. degree n=30) and the comparison of Lebesgue constants for Random (RND), Euclidean (EUC) and Dubiner (DUB) points.

−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1

−1

−0.8

−0.6

−0.4

−0.2 0 0.2 0.4 0.6 0.8 1

0 2 4 6 8 10 12 14 16 18 20 22 24 26 28

degree n 1

1e+05 1e+10 1e+15

Lebesgue constants

RND 106.4·(2.3)ⁿ EUC 4.0·(2.3)ⁿ DUB 0.4·n³

Euclidean pts, areLeja-likepoints: max x∈Ωmin

y∈Xnkx − yk2.

(7)

Morrow-Patterson points

Let n be a positive even integer. The Morrow-Patterson points (MP) (cf. M.P. SIAM JNA 78) are the points

x

m

= cos

mπ n + 2

, y

k

=



 



 



cos 2kπ n + 3

if m odd cos (2k − 1)π

n + 3

if m even

1 ≤ m ≤ n + 1, 1 ≤ k ≤ n/2 + 1. Note: they are N = n + 2 2

.

(8)

Extended Morrow-Patterson points

The Extended Morrow-Patterson points (EMP) (C.DeM.V. AMC 05) are the points

x

_m^EMP

= 1

α

_n

x

_m^MP

, y

_k^EMP

= 1 β

_n

y

_k^MP

α

_n

= cos(π/(n + 2)), β

_n

= cos(π/(n + 3)).

Note: the MP and the EMP points are equally distributed w.r.t.

Dubiner metric on the square [−1, 1]

²

and unisolvent for

polynomial interpolation of degree n on the square.

(9)

Padua points

The Padua points (PD) can be defined as follows (C.DeM.V. AMC 05):

x

_m^PD

= cos (m − 1)π n

, y

_k^PD

=



 



 



cos (2k − 1)π n + 1

if m odd cos 2(k − 1)π

n + 1

if m even

1 ≤ m ≤ n + 1, 1 ≤ k ≤ n/2 + 1, N = n + 2 2

.

The PD points are equispaced w.r.t. Dubiner metric on [−1, 1]

²

. They are modified Morrow-Patterson points discovered in Padua in 2003 by B.DeM.V.&W.

There are 4 families of PD pts: take rotations of 90 degrees,

clockwise for even degrees and counterclockwise for odd degrees.

(10)

Graphs of MP, EMP, PD pts and their Lebesgue constants

−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1

−1

−0.8

−0.6

−0.4

−0.2 0 0.2 0.4 0.6 0.8

1 MP

EMP PD

0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60

degree n 10

100 1000

Lebesgue constants

MP (0.7·n+1.0)² EMP (0.4·n+0.9)² PD (2/π·log(n+1)+1.1)²

Left: the graphs of MP, EMP, PD for n = 8.Right: the growth of the corresponding Lebesgue constants.

(11)

Bivariate interpolation problem and Padua Pts

Let P

²_n

be the space of bivariate polynomials of total degree ≤ n.

Question: is there a set Ξ ⊂ [−1, 1]

²

of points such that:

card(Ξ) = dim(P

²_n

) =

^(n+1)(n+2)₂

;

the problem of finding the interpolation polynomial on Ξ of degree n is unisolvent;

the Lebesgue constant Λ

_n

behaves like log

²

n for n → ∞.

Answer: yes, it is the set Ξ = Pad

_n

of Padua points.

(12)

Padua points

Let us consider n + 1 Chebyshev–Lobatto points on [−1, 1]

C

_n+1

=

z

_jⁿ

= cos (j − 1)π n

, j = 1, . . . , n + 1

and the two subsets of points with odd or even indexes C

_n+1^O

= z

_jⁿ

, j = 1, . . . , n + 1, j odd C

_n+1^E

= z

_jⁿ

, j = 1, . . . , n + 1, j even Then, the Padua points are the set

Pad

_n

= C

_n+1^O

× C

n+2^E

∪ C

_n+1^E

× C

n+2^O

⊂ C

ⁿ⁺¹

× C

ⁿ⁺²

(13)

The generating curve

There exists an alternative representation as self-intersections and boundary contacts of the (parametric and periodic) generating curve:

γ(t) = (− cos((n + 1)t), − cos(nt)), t ∈ [0, π]

(14)

The generating curve γ(t) (n = 4)

-1 -0.5 0 0.5 1

t = 0

(15)

The generating curve γ(t) (n = 4)

-1 -0.5 0 0.5 1

t ∈ h

0,

_(n(n+1))^4π

i

(16)

The generating curve γ(t) (n = 4)

-1 -0.5 0 0.5 1

t ∈ h

4π

(n(n+1))

,

_(n(n+1))^5π

i

(17)

The generating curve γ(t) (n = 4)

-1 -0.5 0 0.5 1

t ∈ h

5π

(n(n+1))

,

_(n(n+1))^8π

i

(18)

The generating curve γ(t) (n = 4)

-1 -0.5 0 0.5 1

t ∈ h

8π

(n(n+1))

,

_(n(n+1))^9π

i

(19)

The generating curve γ(t) (n = 4)

-1 -0.5 0 0.5 1

t ∈ h

9π

(n(n+1))

,

_(n(n+1))^10π

i

(20)

The generating curve γ(t) (n = 4)

-1 -0.5 0 0.5 1

t ∈ h

10π

(n(n+1))

,

_(n(n+1))^12π

i

(21)

The generating curve γ(t) (n = 4)

-1 -0.5 0 0.5 1

t ∈ h

12π

(n(n+1))

,

_(n(n+1))^13π

i

(22)

The generating curve γ(t) (n = 4)

-1 -0.5 0 0.5 1

t ∈ h

13π

(n(n+1))

,

_(n(n+1))^14π

i

(23)

The generating curve γ(t) (n = 4)

-1 -0.5 0 0.5 1

t ∈ h

14π

(n(n+1))

,

_(n(n+1))^15π

i

(24)

The generating curve γ(t) (n = 4)

-1 -0.5 0 0.5 1

t ∈ h

15π

(n(n+1))

,

_(n(n+1))^16π

i

(25)

The generating curve γ(t) (n = 4)

-1 -0.5 0 0.5 1

t ∈ h

16π

(n(n+1))

,

_(n(n+1))^17π

i

(26)

The generating curve γ(t) (n = 4)

-1 -0.5 0 0.5 1

t ∈ h

17π

(n(n+1))

,

_(n(n+1))^18π

i

(27)

The generating curve γ(t) (n = 4)

-1 -0.5 0 0.5 1

t ∈ h

18π

(n(n+1))

,

_(n(n+1))^19π

i

(28)

The generating curve γ(t) (n = 4)

-1 -0.5 0 0.5 1

t ∈ h

19π

(n(n+1))

,

_(n(n+1))^20π

i

(29)

The generating curve γ(t) (n = 4)

-1 -0.5 0 0.5 1

C

_n+1^odd

× C

n+2^even

(30)

The generating curve γ(t) (n = 4), is a Lissajous curve

-1 -0.5 0 0.5 1

Pad

_n

= C

_n+1^O

× C

n+2^E

∪ C

_n+1^E

× C

n+2^O

⊂ C

n+1

× C

n+2

(31)

Lagrange polynomials

The fundamental Lagrange polynomials of the Padua points are

L

ξ

(x) = w

ξ

(K

n

(ξ, x) − T

n

(ξ

1

)T

n

(x

1

)) , L

ξ

(η) = δ

ξη

, ξ , η ∈ Pad

n

(1) where

w

_ξ

= 1 n(n + 1) ·



 



 

 1

2 if ξ is a vertex point 1 if ξ is an edge point 2 if ξ is an interior point

{w

ξ

} are weights of cubature formula for the prod. Cheb. measure, exact

”on almost” P

ⁿ_2n

([−1, 1]

²

), i.e. pol. orthogonal to T

2n

(x

2

)

(32)

Reproducing kernel

K

n

(x, y) =

n

X

k=0 k

X

j=0

T ˆ

j

(x

1

) ˆ T

k−j

(x

2

) ˆ T

j

(y

1

) ˆ T

k−j

(y

2

) , T ˆ

j

= √

2T

j

, j ≥ 1 (2) is the reproducing kernel of P

²_n

([−1, 1]

²

) equipped with the inner product

hf , gi = Z

[−1,1]²

f (x

1

, x

2

)g (x

1

, x

2

) dx

₁

π p1 − x

1²

dx

₂

π p1 − x

2²

, with reproduction property

Z

[−1,1]²

K

n

(x, y)p

n

(y)w (y)dy = p

n

(x), ∀p

ⁿ

∈ P

²n

w(x) = w (x

1

, x

2

) = 1 π p1 − x

1²

1 π p1 − x

2²

(33)

Lebesgue constant

The Lebesgue constant Λ

_n

= max

x∈[−1,1]²

λ

_n

(x), λ

_n

(x) = X

ξ∈Padn

|L

^ξ

(x)|

is bounded by (cf. BCDeMVX, Numer. Math. 2006)

Λ

n

≤ C log

²

n (3)

(optimal order of growth on a square).

(34)

Interpolant

From the representations (1) (Lagrange poly.) and (2) (reproducing kernel) the interpolant of a function f : [−1, 1]

²

→ R is

L

n

f (x) = X

ξ∈Padn

f (ξ)L

ξ

(x) = X

ξ∈Padn

f (ξ) [w

ξ

(K

n

(ξ, x) − T

n

(ξ

1

)T

n

(x

1

))] =

=

n

X

k=0 k

X

j=0

c

j,k−j

T ˆ

j

(x

1

) ˆ T

k−j

(x

2

) − c

n,0

2 T ˆ

n

(x

1

) ˆ T

0

(x

2

) , where the coefficients

c

j,k−j

= X

ξ∈Padn

f (ξ)w

ξ

T ˆ

j

(ξ

1

) ˆ T

k−j

(ξ

2

), 0 ≤ j ≤ k ≤ n

can be computed once and for all.

(35)

Coefficient matrix

Let us define the coefficient matrix

C

₀

=







c

_0,0

c

_0,1

. . . . . . c

_0,n

c

_1,0

c

_1,1

. . . c

_1,n−1

0 .. . .. . . . .

. . . .. . c

_n−1,0

c

_n−1,1

0 . . . 0

cn,0

2

0 . . . 0 0







and for a vector S = (s

₁

, . . . , s

_m

), S ∈ [−1, 1]

^m

, the (n + 1) × m Chebyshev collocation matrix

T (S) =







T ˆ

₀

(s

1

) . . . T ˆ

₀

(s

m

) .. . . . . .. . T ˆ

_n

(s

₁

) . . . T ˆ

_n

(s

_m

)







(36)

Coefficient matrix factorization

Letting C

_n+1

the vector of the Chebyshev-Lobatto pts C

_n+1

= z

₁ⁿ

, . . . , z

_n+1ⁿ

we construct the (n + 1) × (n + 2) matrix G (f ) = (g

r ,s

) =

( w

ξ

f (z

_rⁿ

, z

_sⁿ⁺¹

) if ξ = (z

_rⁿ

, z

_sⁿ⁺¹

) ∈ Pad

n

0 if ξ = (z

_rⁿ

, z

_sⁿ⁺¹

) ∈ (C

n+1

× C

n+2

) \ Pad

n

.

Then C

0

is essentially the upper-left triangular part of C (f ) = P

₁

G (f )P

^T₂

P

₁

= T(C

_n+1

) ∈ R

(n+1)×(n+1)

and P

₂

= T(C

_n+2

) ∈ R

(n+1)×(n+2)

.

(37)

Coefficient matrix factorization

Exploiting the fact that the Padua points are union of two Chebyshev subgrids, we may define the two matrices

G

₁

(f ) = w

ξ

f (ξ) , ξ = (z

_rⁿ

, z

_sⁿ⁺¹

) ∈ C

_n+1^E

× C

n+2^O

G

₂

(f ) = w

ξ

f (ξ) , ξ = (z

_rⁿ

, z

_sⁿ⁺¹

) ∈ C

_n+1^O

× C

n+2^E

then we can compute the coefficient matrix as

C (f ) = T(C

_n+1^E

) G

1

(f ) (T(C

_n+2^O

))

^t

+ T(C

_n+1^O

) G

2

(f ) (T(C

_n+2^E

))

^t

We term this approach as MM, Matrix-Multiplication.

(38)

Coefficient matrix factorization by FFT

c

j,l

= X

ξ∈Padn

f (ξ)w

ξ

T ˆ

j

(ξ

1

) ˆ T

l

(ξ

2

) =

n

X

r =0 n+1

X

s=0

g

r ,s

T ˆ

j

(z

_rⁿ

) ˆ T

l

(z

_sⁿ⁺¹

)

= β

j,l n

X

r =0 n+1

X

s=0

g

r ,s

cos jrπ

n cos lsπ n + 1 = β

j,l

M−1

X

s=0 N−1

X

r =0

g

_{r ,s}⁰

cos 2jr π N

!

cos 2lsπ M where N = 2n, M = 2(n + 1) and

β

j,l

=



 

 

1 j = l = 0 2 j 6= 0, l 6= 0

√ 2 otherwise

g

_{r ,s}⁰

=

( g

r ,s

0 ≤ r ≤ n and 0 ≤ s ≤ n + 1

0 r > n or s > n + 1

(39)

Coefficient matrix factorization by FFT

The coefficients c

j,l

can be computed by a double Discrete Fourier Transform.

ˆ

g

j,s

= REAL

N−1

X

r =0

g

_{r ,s}⁰

e

^{−2πijr /N}

!

, 0 ≤ j ≤ n, 0 ≤ s ≤ M − 1

c

j,l

β

j,l

= ˆ g ˆ

j,l

= REAL

M−1

X

s=0

ˆ

g

j,s

e

^−2πils/M

!

, 0 ≤ j ≤ n, 0 ≤ l ≤ n − j

(4)

(40)

Matlab

^R

code for the FFT approach

Input: G ↔ G(f )

Gfhat = real(fft(G,2*n));

Gfhat = Gfhat(1:n+1,:);

Gfhathat =real(fft(Gfhat,2*(n+1),2));

C0f = Gfhathat(:,1:n+1);

C0f =2*C0f; C0f(1,:) = C0f(1,:)/sqrt(2);

C0f(:,1) = C0f(:,1)/sqrt(2);

C0f = fliplr(triu(fliplr(C0f)));

C0f(n+1,1) = C0f(n+1,1)/2;

Output: C0 ↔ C

⁰

(41)

Linear algebra approach vs FFT approach

The construction of the coefficients is performed by a matrix-matrix product.

It has been easily and efficiently implemented in Fortran77 (by, eventually optimized, BLAS) (cf. CDeMV, TOMS 2008) and in Matlab

^R

(based on optimized BLAS).

The coefficients are approximated Fourier–Chebyshev

coefficients, hence they can be computed by FFT techniques.

FFT is competitive and more stable than the MM approach at

high degrees of interpolation (see later).

(42)

Evaluating the interpolant (in Matlab)

Given a point x = (x

1

, x

2

) and the coefficient matrix C

0

, the polynomial interpolation formula can be evaluated by a double matrix-vector product

L

ⁿ

f (x) = T(x

1

)

^T

C

₀

(f )T(x

2

)

If X = (X

1

, X

2

) (X

1,2

column vectors) is a set of target points, then L

ⁿ

f (X) = diag (T(X

1

))

^t

C

₀

(f ) T(X

2

)

(5) The result L

n

f (X) is a (column) vector.

If X = X

1

× X

²

is a Cartesian grid then

L

ⁿ

f (X) = (T(X

1

))

^t

C

₀

(f ) T(X

2

)

^t

(6)

The result L

n

f (X) is a matrix whose i-th row and j-th column

contains the evaluation of the interpolant as the built-in function

meshgrid of Matlab

^R

.

(43)

Beyond the square

The interpolation formula can be extended to other domains Ω ⊂ R

²

, by means of a suitable mapping of the square. Given

σ : [−1,1]

²

→ Ω t 7→ x = σ(t)

it is possible to construct the (in general nonpolynomial) interpolation formula

L

n

f (x) = T(σ

₁^←

(x))

^T

C

₀

(f ◦ σ)T(σ

2^←

(x))

(44)

Cubature

Integration of the interpolant at the Padua points gives a

nontensorial Clenshaw–Curtis cubature formula (cf. SVZ, Numer.

Algorithms 2008) Z

[−1,1]²

f (x)dx ≈ Z

[−1,1]²

L

n

f (x)dx =

n

X

k=0 k

X

j=0

c

_j,k−j^′

m

_j,k−j

=

n

X

j=0 n

X

l=0

c

_j,l^′

m

_j,l

=

n

X

j even n

X

l even

c

_j,l^′

m

_j,l

(45)

Cubature

Where the moments m

_j,l

are m

_j,l

=

Z

₁

−1

T ˆ

_j

(t)dt Z

₁

−1

T ˆ

_l

(t)dt

Since

Z

1

−1

T ˆ

_j

(t)dt =



 

 

 

 

2 j = 0

0 j odd

2 √ 2

1 − j

²

j even

(46)

The Matlab

^R

code for the cubature

Input: C0f↔ C

0

(f ) j = [0:2:n];

mom = 2*sqrt(2)./(1-j.^2);

mom(1) = 2;

[M1,M2]=meshgrid(mom);

M = M1.*M2;

C0fM = C0f(1:2:n+1,1:2:n+1).*M;

Int = sum(sum(C0fM));

Output: Int↔ I

n

(f )

(47)

Cubature

It is often desiderable having a cubature formula involving the function values at the nodes and the corresponding cubature weights. Using the formula for the coefficients c

j,l

, we can write

I

n

(f ) = X

ξ∈Padn

λ

ξ

f (ξ)

= X

ξ∈C_n+1^E ×C_n+2^O

λ

ξ

f (ξ) + X

ξ∈C_n+1^O ×C_n+2^E

λ

ξ

f (ξ)

where

λ

ξ

= w

ξ n

X

j even n

X

l even

m

^′_j,l

T ˆ

j

(ξ

1

) ˆ T

l

(ξ

2

) (7)

(48)

Cubature

Defining the Chebyshev matrix corresponding to even degrees

T

^E

(S) =







T ˆ

0

(s

1

) · · · T ˆ

0

(s

m

) T ˆ

2

(s

1

) · · · T ˆ

2

(s

m

)

.. . · · · .. . T ˆ

pn

(s

1

) · · · T ˆ

pn

(s

m

)







∈ R

^([ⁿ²^]+1)×m

and the matrices of weights on the subgrids, W

₁

= w

ξ

, ξ ∈ C

_n+1^E

× C

n+2^O

t

, W

2

= w

ξ

, ξ ∈ C

_n+1^O

× C

n+2^E

t

, then the cubature weights {λ

ξ

} can be computed in the matrix form

L

₁

= λ

ξ

, ξ ∈ C

_n+1^E

× C

n+2^O

t

= W

1

. T

^E

(C

_n+1^E

))

^t

M

₀

T

^E

(C

_n+2^O

)

t

L

₂

= λ

ξ

, ξ ∈ C

_n+1^O

× C

n+2^E

t

= W

2

. T

^E

(C

_n+1^O

))

^t

M

₀

T

^E

(C

_n+2^E

)

t

where M

0

= m

^′_j,l

(moment matrix) and the dot means that the final

product is made componentwise.

(49)

Cubature

1

An FFT-based implementation is then feasible, in analogy to what happens in the univariate case with the Clenshaw-Curtis formula (cf.

Waldvogel, BIT06). The algorithm is quite similar the one for interpolation.

2

The cubature weights are not all positive, but the negative ones are few and of small size and

n→∞

lim X

ξ∈Padn

|λ

ξ

| = 4

i.e. stability and convergence.

(50)

Numerical results

Language: Matlab

^R

7.6.0 Processor: Intel Core2 Duo 2.2GHz.

n 20 40 60 80 100 200 300 400 500

FFT 0.002 0.002 0.002 0.002 0.006 0.029 0.055 0.088 0.137

MM 0.003 0.001 0.003 0.004 0.006 0.022 0.065 0.142 0.206

Table: CPU time (in seconds) for the computation of the interpolation coefficients at a sequence of degrees.

n 20 40 60 80 100 200 300 400 500

FFT 0.005 0.001 0.003 0.003 0.005 0.025 0.048 0.090 0.142

MM 0.004 0.000 0.001 0.002 0.003 0.010 0.025 0.043 0.071

Table: CPU time (in seconds) for the computation of the cubature

weights at a sequence of degrees.

(51)

Numerical results

1e-14 1e-12 1e-10 1e-08 1e-06 0.0001 0.01 1

0 20 40 60 80 100

Relativeinterpolationerror

degreen

MM

FFT

1e-16 1e-14 1e-12 1e-10 1e-08 1e-06 0.0001 0.01 1

0 20 40 60 80 100

Relative ubatureerror

degreen

MM

FFT

Figure: Relative errors of interpolation (left) and cubature (right) versus

the interpolation degree for the Franke test function in [0, 1]

²

, by the

Matrix Multiplication (MM) and the FFT-based algorithms.

(52)

Numerical results

1e-16 1e-14 1e-12 1e-10 1e-08 1e-06 0.0001 0.01 1

0 100 200 300 400 500

Numberofpoints Tens.CL

Paduapts.

1e-05 0.0001 0.001 0.01 0.1

0 100 200 300 400 500

Numberofpoints Tens.CL

Paduapts.

Figure: Relative interpolation errors versus the number of interpolation

points for the Gaussian f (x) = exp (−|x|

²

) (left) and the C

²

function

f (x) = |x|

³

(right) in [−1, 1]

²

; Tens. CL = Tensorial Chebyshev-Lobatto

interpolation.

(53)

Numerical results

1e-16 1e-14 1e-12 1e-10 1e-08 1e-06 0.0001

0 100 200 300 400 500

Numberofpoints Tens.CCpts.

Nontens.CCPaduapts.

Tens.GLLpts.

OSpts.

1e-09 1e-08 1e-07 1e-06 1e-05 0.0001 0.001 0.01

0 100 200 300 400 500

Numberofpoints Tens.CCpts.

Nontens.CCPaduapts.

Tens.GLLpts.

OSpts.

Figure: Relative cubature errors versus the number of cubature points (CC = Clenshaw-Curtis, GLL = Gauss-Legendre-Lobatto, OS =

Omelyan-Solovyan) for the Gaussian f (x) = exp (−|x|

²

) (left) and the C

²

function f (x) = |x|

³

(right); the integration domain is [−1, 1]

²

, the

integrals up to machine precision are, respectively: 2.230985141404135

and 2.508723139534059.

(54)

Conclusions

We studied different families of point sets for polynomial interpolation on the square.

The most promising, from theoretical purposes and computational cost both of the interpolant and Lebesgue constant growth are the Padua points.

More on Padua points (papers, software, links) at the CAA research group:

http://www.math.unipd.it/∼marcov/CAA.html

http://en.wikipedia.org/wiki/Padua points.

(55)

Main references

1 M. Caliari, S. De Marchi, A. Sommariva and M. Vianello: Padua2DM: fast interpolation and cubature at Padua points in Matlab/Octave, Submitted (2009).

2 M. Caliari, S. De Marchi and M. Vianello: Bivariate polynomial interpolation on the square at new nodal sets, Applied Math. Comput. vol. 165/2, pp. 261-274 (2005)

3 L. Bos, M. Caliari, S. De Marchi and M. Vianello: A numerical study of the Xu polynomial interpolation formula in two variables, Computing 76(3-4)(2006), 311–324 .

4 L. Bos, S. De Marchi and M. Vianello: On the Lebesgue constant for the Xu interpolation formula J.

Approx. Theory 141 (2006), 134–141.

5 L. Bos, M. Caliari, S. De Marchi and M. Vianello: Bivariate interpolation at Xu points: results, extensions and applications, Electron. Trans. Numer. Anal. 25 (2006), 1–16.

6 L. Bos, S. De Marchi, M. Caliari, M. Vianello and Y. Xu: Bivariate Lagrange interpolation at the Padua points: the generating curve approach, J. Approx. Theory 143 (2006), 15–25.

7 L. Bos, S. De Marchi, M. Vianello and Y. Xu: Bivariate Lagrange interpolation at the Padua points: the ideal theory approach, Numer. Math., 108(1) (2007), 43-57.

8 M. Caliari, S. De Marchi, and M. Vianello: Bivariate Lagrange interpolation at the Padua points:

computational aspects, J. Comput. Appl. Math., Vol. 221 (2008), 284-292.

9 M. Caliari, S. De Marchi and M. Vianello: Algorithm 886: Padua2D: Lagrange Interpolation at Padua Points on Bivariate Domains, ACM Trans. Math. Software, Vol. 35(3), Article 21, 11 pages, 2008.

10 Sommariva, A., Vianello, M., Zanovello, R.: Nontensorial Clenshaw-Curtis cubature. Numer. Algorithms 49, 409–427 (2008).

(56)

Second DOLOMITES WORKSHOP ON

CONSTRUCTIVE APPROXIMATION AND APPLICATIONS Alba di Canazei, Trento (Italy), September 4-9, 2009

http://www.math.unipd.it/∼dwcaa09/

Oslo,2April2009 StefanoDeMarchi Paduapoints:theory,computationandapplications

Padua points: theory, computation and applications ∗

Stefano De Marchi

Oslo, 2 April 2009

Outline

Motivations and aims

From Dubiner metric to Padua points

Padua points and their properties

Interpolation

Cubature

Numerical results

Motivations and aims

Well-distributed nodes: there exist various nodal sets for polynomial interpolation of even degree n in the square Ω = [−1, 1]

(

), which turned out to be equidistributed w.r.t. Dubiner metric (

) and which show optimal Lebesgue constant growth.

Efficient interpolant evaluation: the interpolant should be constructed without solving the Vandermonde system whose complexity is O(N

), N =

for each pointwise evaluation. We look for compact formulae.

Efficient cubature: in particular computation of cubature weights for

non-tensorial cubature formulae.

The Dubiner metric

The Dubiner metric in the 1D:

µ

(x, y ) = | arccos(x) − arccos(y)|, ∀x, y ∈ [−1, 1] . By using the Van der Corput-Schaake inequality (1935) for trig. polys.

µ

(x, y ) := sup

1

deg(P) | arccos(P(x)) − arccos(P(y))| , with P ∈ P

([−1, 1]).

This metric generalizes to compact sets Ω ⊂ R

, d > 1:

µ

(x, y) := sup

1

(deg(P)) | arccos(P(x)) − arccos(P(y))| .

The Dubiner metric

Conjecture(C.DeM.V.AMC04):

Nearly optimal interpolation points on a compact Ω are asymptotically equidistributed w.r.t. the Dubiner metric on Ω.

Once we know the Dubiner metric on a compact Ω, we have at least a method for producing ”good” points. Letting x = (x

, x

), y = (y

, y

)

Dubiner metric on the square:

max{| arccos(x

) − arccos(y

)|, | arccos(x

) − arccos(y

)|} ; Dubiner metric on the disk:

arccos



x

y

+ x

y

+ q

1 − x

− x

q

1 − y

− y



;

Dubiner points and Lebesgue constant

Morrow-Patterson points

Let n be a positive even integer. The Morrow-Patterson points (MP) (cf. M.P. SIAM JNA 78) are the points

x

= cos

 mπ n + 2



, y

=



 



 



cos  2kπ n + 3



Padua points: theory, computation and applications ^∗

mπ n + 2

cos 2kπ n + 3

if m odd cos (2k − 1)π

1 ≤ m ≤ n + 1, 1 ≤ k ≤ n/2 + 1. Note: they are N = n + 2 2

= cos (m − 1)π n

cos (2k − 1)π n + 1

if m odd cos 2(k − 1)π

1 ≤ m ≤ n + 1, 1 ≤ k ≤ n/2 + 1, N = n + 2 2

.