Adaptive bivariate Chebyshev approximation and efficient evaluation of integral operators

(1)

Adaptive bivariate Chebyshev approximation and efficient evaluation of integral operators

Alberto Mardegan, Alvise Sommariva

¹

, Marco Vianello

¹

, and Renato Zanovello

¹

1

Dept. of Pure and Applied Mathematics, University of Padova, Via Belzoni 7- 35131, Padova (Italy)

Received ???, revised ???, accepted ???

We propose an adaptive algorithm which extends Chebyshev series approximation to bivariate functions on domains which are smooth transformations of a square. We apply the method for evaluating efficiently the action of linear and nonlinear bivariate integral operators.

Chebyshev series expansion

"!#$!&%

('

)+*-,

. , !

/

!021

43#5 687:9;

(1)

,

<>=

,

. ,

@?

/

! 1 3A

, is a useful and popular tool for the approximation of sufficiently regular univariate functions. In fact, its partial sums provide an asymptotically optimal polynomial approximation, which can be constructed in a very efficient way by resorting to the FFT algorithm; see, e.g., the classical book [11], and e.g. the various algorithms in the Netlib and Cernlib repositories for the practical imple- mentations. Concerning its extension to bivariate functions only some spread results, restricted to the case of rectangular domains (see, e.g., [10]), seem to have appeared in the literature. In particular, an adaptive algorithm for bivariate Chebyshev approximation, taking into account the different behaviors of the under- lying function in different parts of the domain, and working also on a wide class of domain geometries, does not seem to be yet available.

Let us begin by the simplest case, that is a function

BDCE

defined on the square

F"!AG!G%

1

, the adap- tation to rectangular domains being straightforward. The basic idea is simple: suppose that

BHC4

can be expanded in Chebyshev series in

C

(uniformly in

), then we get

BHC4IKJ

L

C4

. Moreover, suppose that we can expand each coefficient

L

in Chebyshev series (uniformly in

^M

), i.e.

L

N J

O

L O O

. It is not difficult to show that both expansions take place for example when

PRQ#S TB

osc

UWV$!?XTBZY[9

as

T\Y^]

, osc

_WVG!?XTBa`b+cedXfBgh

.i gj

,DkDlnmEo

Up>Wq_r>

o

4p@rstF"!AG!G%

1u

. The latter is indeed the natural bivariate extension of the well-known Dini-Lipschitz condition for Cheby- shev univariate approximation (see [11]), and is verified for example by any globally H¨older-continuous function. Under this assumption, we obtain indeed that, for every fixed tolerance

^v

7w9

, there exist an index

^M ^v

, and a sequence

^x ^M ⁿ ^x ^M ^V ^v

, such that the following bivariate polynomial approximation

of

yHC4

with degree

^cedXf ^L

m

M8z{x

M u

holds (see the forthcoming paper [12] for a proof)

|

e~}

| cedXf

GE

. ,

,

o

BDCE8}WBDC4

o

v

~}yBHC4

L

H

L

O L

O W

L O O

L

C4

(2)

As in the univariate case, the smoother the function

, the smaller the approximation degree at the same tolerance. Observe that all the information necessary to reconstruct the function

on the square is now

Corresponding author: e-mail:marcov@math.unipd.it. This work has been partially supported by the University of Padova, in particular by the project CPDA028291 “Efficient approximation methods for nonlocal discrete transforms”, and by the 2003 project “Innovative methods for structured problems in stationary and evolutive models” of the GNCS-INdAM.

c

2003 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim

(2)

compressed in the coefficients matrix

m L O u

, which is in general not full, but has a “reversed nonincreasing histogram” shape.

The practical implementation of the method works as follows. First, one chooses a good univariate code for Chebyshev series approximation: we selected the robust Fortran code [7] in the Cernlib, and translated it in the C language with some minor adaptations in view of the bivariate embedding, the most remarkable being that of allowing discrete values of the function at the Chebyshev nodes as inputs (indeed, the original code requires an analytic definition), and of introducing an additional stopping criterion based on a possible

“stalling” of convergence. The “regular” exit is based on a classical criterion [3], looking for the first triple of consecutive coefficients whose absolute values sum is below a given tolerance, while the output error estimate uses for safety the complete tail of the last computed coefficients. Other important features of the code [7] are that it doubles iteratively the computed coefficients minimizing the computational effort via a clever use of the FFT, and moreover that it minimizes a posteriori the final number of output Chebyshev coefficients, by eliminating those below a suitable threshold.

For the construction of the bivariate polynomial

}WyHC4

in (2), we take

^T

“cuts” on the square, corre- sponding to the first

^T

Chebyshev-Lobatto nodes

^Q ⁾ ^?ET ^-!H

,

⁹ G!#$ RRHT5 !

. The func-

tion

BHC4

is approximated by a truncated Chebyshev series

BDC4 J L

HD

L

C4

at each cut

~

, by the univariate code up to a fraction

of the global tolerance (say

⁹⁴

); this step provides the values

m L u

of the coefficient functions

L

,

^M s94G!AGR R

M v

nN` cedXf

M V

v

, at the Cheby- shev

-nodes

m u

. Then, these values are passed to the univariate code, which produces the Chebyshev approximation

L

Z J l . ,

O

L O O

, and checks whether

|

L L |

H! v

?E! z M

Xv

H

for every

^M ⁹ G!AGR R

M Xv

. In fact, we can consider the error estimate

|

0a}

| |

Z

| z |

a}

|

cedXf

|

b

y

| z J L

HD

L

|

L L |

v z

H!

z-M

Xv

Hcedf

L |

L L |

. If the stop- ping criterion is not satisfied (the approximation in the

-direction is not satisfactory), then the number

T

of Chebyshev cuts is doubled and the procedure repeated. It is worth noting the full adaptivity of this algo- rithm, which is even improved by some implementation tricks. For example, as usual the global tolerance is taken as a combination of a relative and an absolute one,

^v ^v

| |

z\v

, where the estimate of the

maximum norm of the function is dinamically updated when new cuts are added. Moreover, whenever a stalling of convergence occurs, for example during the Chebyshev approximation along a cut, the absolute tolerance

^v

is automatically modified and set to a value close to the estimated size of the error at stalling, in order to avoid overprecision (and thus saving computational work) on other cuts, or in the

-direction.

The error stalling is detected by the univariate code, simply by comparing two consecutive error estimates, and is typical of low regularity of the function, for example in the presence of noise, or in the application to discrete integral operators with weakly-singular kernels, as we shall see below.

We can now face more general situations. Consider a function

defined on a bivariate compact domain

, that corresponds to the square

F"!AG!G%

1

through the smooth surjective transformation

"!#$!&%

1

Y

,

5;! Y W"5#;&HC" D

. Then, we can construct by the method described above the Chebyshev- like polynomial approximation

}y"N

%$

"N;` y5;DC5NH

on the square

"!#$!&%

1'&

5;

, and finally obtain an approximation like

BHC4

)(

BDC4 t}W"\BDCE& BDCED

L

FD

L

O L

O W

L O O

"\BDCED

L

* yHC4H0

(3)

BHC45+

, which is in general no more polynomial. In (3),

\yHC4# yHC4H

denotes the “inverse”

transformation

:Y[ "!#$!&%

1

, which is allowed to be undefined only in a finite number of points. Observe that, from the theoretical point of view, when the function

is globally H¨older-continuous in

, then a H¨older-continuous transformation suffices to ensure convergence of the Chebyshev-like approximation method. However, a key point in order to avoid loss of smoothness in this process and thus an artificial slowing down of convergence, is to choose a transformation as smooth as possible, and in any case with at least the same degree of regularity of the function

. This role of the transformation will be clarified by

(3)

the example in Table 1 below. Now we are ready to describe two important classes of domain geometries, with corresponding transformations.

-regular domains in Cartesian coordinates: the domain

is defined by

,

C

1

,

and

¹

being suitable functions (these are the typical domains where double integrals can be splitted). Here the transformation is

y5; y

ez

"

z ! G

D?

'

,

C"5#

,

z

*

z

!&

1

,

H@?

'

, and its inverse

\yHC4N%\NK"!

z '

5

D?4

,

8yHC4t"!

z '

C5

,

H@?E

1

,

H

; the latter is not defined at the possible points

y C

where

, I

1

, but this is not a real problem, since in such cases the Chebyshev se- ries on the corresponding

-cut is constant, and our algorithm manages the situation computing

}W"\& y CD J O

O

O O

"\ D

, cf. (3). The regularity of the transformation is clearly given by the regularity of the functions

,

and

¹

.

-regular domains in polar coordinates: these are defined by

, 1

,

, 1

, and the transformation is the composition of one analogous to that described above with the change from Cartesian to polar coordinates, with inverse

\yHC4Z "!

z ' ,

@?E

1 ,

,

8yHC4Z

"!

z ' ,

H@?E

1

,

H

, with

BDCEn 21

z

CE1

,

BDC4n d @daC ?

. The special case of the origin is managed by choosing

94@9Aa 9

, while the angles where

, 1

are

treated as above. Again, the regularity of the transformation is determined by the functions

,

and

¹

. The simplest case is that of a circle centered at the origin, i.e.

9 ' )

,

9

(notice that the transformation is analytic in this case, while that corresponding to the circle represented directly in Cartesian coordinates is not even

,

, since we have

,

> / 1

1

,

¹

>

/ 1

1

, which have singular derivatives at

8

).

A remarkable subclass of

-regular is given by star domains, i.e.

, 1

%W 94

' ) %

,

9

(up to a translation). Here a different transformation can be defined, which allows to avoid unnecessary clustering of sampling nodes at the origin [9, 12]. For the sake of brevity, we omit a third type of domain, the triangle, whose importance stems from the possibility of triangulating efficiently domains with complex geometries:

also in this case different transformations can be used, which lead to quite different performances of the approximation method; see again [9, 12], where domain splitting techniques are also discussed in order to manage possible singularities of the function

. The following table illustrates the importance of the choice of the transformation.

Table 1 Adaptive Chebyshev approximation of

"!#$&%(')#*+,#-.

on the unit circle in Cartesian and polar coordinates; the absolute and relative tolerances have been set to

/"0)2134,5

,

/"67213498

.

number of coeffs number of nodes relative error Cartesian

^: ^' ^;#;< ⁹⁼ ^; ^A!$9 ^.>

polar

!?=@ <@

'

A!$9

.A

Notice that, while the function is extremely smooth, the choice of representing the unit circle as an

- regular domain leads to computational failure, since the singularity of the transformation entails very slow convergence (the relative error in

| |

is computed by comparison with the exact values on a suitable control grid). The overall number of function evaluations at the sampling Chebyshev nodes is higher than the number of output Chebyshev coefficients, since as already observed the code is able to discard unsignificant coefficients.

At this point, we could summarize by observing that bivariate Chebyshev approximation is particularly

useful when the domain is a smooth transformation of a square, and the function exhibits the following

features: it is sufficiently regular to guarantee a satisfactory convergence rate; it can be evaluated at any

point of the domain; the evaluation is costly (indeed, after the approximation process all the information,

(4)

up to the tolerance, is compressed in the Chebyshev coefficients array). All these features are usually shown by functions coming from the action of bivariate integral operators, or of their discrete versions,

Up>

*I*

p@reUr>DE3 r

p>

, ,

p r

(4)

where

^p BHC4&@r t%

,

^`! ^Y

,

^`! ^Y

is a pentavariate

kernel function,

m u

and

m r u

are suitable cubature weights and nodes, respectively, and

^Ur

. Observe that computing the bivariate functions

or

in (4) at a large number of “target” points is a very costly process, since each evaluation corresponds to the computation of a double integral. For example, if the discrete integral transform

has to be evaluated at all the

cubature points

m r u

, as it is usual in the numerical solution of integral equations within iterative solvers of the corresponding discrete systems, a quadratic complexity like

1 1

arises. Starting from the basic work of Rokhlin and Greengard in the ’80s on the fast multipole method [6], which represented the turning point in the simulation of large scale linear integral models, several fast methods have been proposed, all sharing the task of accelerating the evaluation of dense discrete linear operators: we may quote, e.g., wavelet-based methods [2], and more recently

-matrix methods [8]. Roughly summarizing, these fast methods act on the kernel of the linear operator by approximation theory techniques, and are able to obtain impressive speed-ups in evaluating the target vector at a specified precision, reducing the complexity even from quadratic to linear. On the other hand, they are usually taylored on the specific structure of the kernel, and are conceived for linear operators.

In some recent papers [4, 5, 13], a different approach has been explored in the framework of univariate integral operators, that is of accelerating the evaluation by approximating directly the action of the op- erator (i.e. the output function) via Chebyshev series or polynomial interpolation at Leja nodes. In the present paper we apply the same idea to bivariate integral operators, by means of our adaptive Chebyshev approximation algorithm described above. It is worth emphasizing some features of this approach (ap- proximating the action instead of the kernel of the operator): we compress the functions

or

in (4) into the array of the

^!

Chebyshev coefficients

m L O u

,

^!

J L

FD

L

!

z{x

M

H

, and reduce consequently the cost of evaluation of the discrete operator from

1 1

to

D

! z"

,

^! z#"%$&

(where

" " v

denotes the overall number of sampling Chebyshev nodes used by the adaptive algorithm along the cuts); we exploit the smoothing effect of integration, a fact that has been often overlooked concerning the construction of fast methods; we are able to treat linear as well as nonlinear problems, because we operate after integration; even in linear instances,

^p rI('{p r>)

, we work in lower dimension, since we face a bivariate approximation problem while the kernel

^'

is quadrivariate. It is worth recalling here that the idea of approximating directly the action of the operator (the potential), has already appeared in the framework of computational methods of potential theory, cf. e.g. [1].

In order to illustrate the effectiveness of our approach, we present some examples, collected in Tables 2- 4 below. The computations have been performed on a AMD K6-III 400 Mhz processor; in all the examples the absolute and relative tolerances in the Chebyshev approximation code have been set to

^v ^! ⁹ ^.+*

,

v

!$9

.>

. For the adaptive cubatures we have used the C++ package CubPack++, while the discrete operators have been obtained by a simple trapezoidal-like cubature formula on a

uniform grid in the square

F"!AG!&%

1

, via a suitable change of variables by the transformations described above.

Table 2 concerns the adaptive Chebyshev approximation and consequent compression of a logarithmic potential with a constant density,

p@re P QAS op qr

o

)

,

^W_r> ^!

, and of a nonlinear transform

with kernel

yHCA ,>C-

z o o z

D?4 ! z

and argument

o

,>/.10

z o o

2

z ! D

o

, the domain being the unit circle. As known, logarithmic potentials are solutions of the Poisson equation

3

-

' )

, cf. [14]. The relative error of Chebyshev approximation has been computed in

| |

on a suitable control grid. Notice in particular that all the information necessary to reconstruct the logarithmic potential up to a relative error of the order of

!$9

.A

, is completely contained in only

!

output Chebyshev

(5)

coefficients (and has required the computation of

^<

double integrals). Here we have adopted a high- precision adaptive cubature method, and this corresponds to approximate directly the function

in (4).

On the contrary, in Tables 3 and 4 we approximate the action of operators that have been discretized by a cubature formula on a fixed

grid

m r u

(which is also the target grid), and this corresponds to work with the function

in (4). The transforms in Table 3 have respectively

BDCA\

f> C

,

n

, "/H

z !

if

and

a

,

>2 !

if

, and

BHC A

f>/

, "

z

z C z

HD?

,

Z . 0

if

1 z 1 !

and

W/ Z

, >

z '

if

1 z 1

s!

. The domain, defined by

' '

,

, "

'

' C

, "

z '

, is treated as a

-regular one.

Observe that due to the discontinuity of the operator arguments

the cubature is not very precise, but the smoothness of the kernels entails that the bivariate Chebyshev approximation works satisfacto- rily, with errors very close to the required tolerance and good speed-ups w.r.t. direct evaluation. The speed-up is defined as (direct time)/(construction time + evaluation time), “direct” denoting the machine- time for computing

m _r

u

, “construction” that for computing the Chebyshev coefficients

m L O u

of the approximating function

⁽ ^BDC4 AyHC4

(cf. (3)), and “evaluation” the machine-time for evalu- ating the output vector

m (

#_r

u

. As for the relative errors, they are measured in the maximum norm,

cedXf

o

AUr

W

(

Ur

o

?WcedXf

o

AUr

o

. Notice that the evaluation time is a small fraction of the construction time, since the bulk of the algorithm is given by computation of

. Indeed, the observed speed-ups are not far from the rough speed-up estimate

1

/(number of nodes): this means that taking for example a

^#9#9 ^'#9#9

grid, we could expect an increase of the speed-up by a factor

^'

.

Finally, it is worth to comment the examples in Table 4, where two discrete logarithmic potentials have been computed on a

^9A9 ^9A9

grid in polar coordinates on the unit circle. The first row in the table corresponds to a constant density, while the second to a

,

density which has partial second derivatives discontinuous on the Cartesian axes,

1

is equal to

.10

z

in the first quadrant,

! z z

in the second,

! z

y 1

in the third, and

. 0W 1

in the fourth. Here, we have a weakly-singular kernel, and the Chebyshev approximation error is not able to reach the required tolerance (a stalling phenomenon appears:

the Chebyshev error stagnates at the size of the cubature error). This fact has already been observed in univariate instances, cf. [4, 5, 13] where it is analyzed and qualitatively explained; the key point is that in weakly-singular instances the discrete transform

-

is singular at the cubature points, while

can be regular. Observe that the stalling phenomenon does not represent a real disadvantage, since one usually is not interested in approximating beyond the underlying discretization error.

Table 2 Adaptive Chebyshev compression on the unit circle of a Urysohn-type nonlinear transform with smooth kernel and of a logarithmic potential, pointwise evaluated by adaptive cubature with tolerance

¹ ³ ⁴

.

number of coeffs number of nodes relative error log potential

! < '

#! 9

.A

Urysohn

^=#= ^' ^;= ^< ^#! ⁹ ^.+*

Table 3 Adaptive Chebyshev approximation of a linear discrete and of a Urysohn-type nonlinear discrete transform with smooth kernels and discontinuous arguments, on a

-regular domain (

^13?3 ¹ ³ ³

grid).

coeffs nodes rel. err. cub. err. constr. eval. direct speed-up linear

^;4! ^! ^' ⁼ ^< ^#! ⁹ ^. ^A ^#!$9 ^. ^<

sec

^!#^'

sec

^!?=

sec

^@^'

Urysohn

< !?; !$9

: #!$9

. > :

#!$9

.

sec

94(@

sec

;<

sec

!$94=

(6)

Table 4 Adaptive Chebyshev approximation of two discrete logarithmic potentials on the unit circle (

^?3 ³ ^?3 ³

polar grid):

,

¹

,

-

has discontinuous second partial derivatives.

coeffs nodes rel. err. cub. err. constr. eval. direct speed-up

8 , ' @ @ !A!$9

.

!#! 9 . '

,@

sec

! '

sec

4!

hours

@ <

8 1

' ; ' ! A!$9

. ! #! 9 . @ #;

sec

^@

sec

^: ^!

hours

^' ^=<

References

[1] G. Allasia, Approximating potential integrals by cardinal basis interpolants on multivariate scattered data in:

“Radial basis functions and partial differential equations”, Comput. Math. Appl. 43 (2002), 275-287.

[2] B. Alpert, G. Beylkin, R. Coifman and V. Rokhlin, Wavelet-like bases for the fast solution of second-kind integral equations, SIAM J. Sci. Comput. 14 (1993), 159-184.

[3] C.W. Clenshaw and A.R. Curtis, A method for numerical integration on an automatic computer, Numer. Math. 2 (1960), 197-205.

[4] S. De Marchi and M. Vianello, Approximating the approximant: a numerical code for polynomial compression of discrete integral operators, Numer. Algorithms 28 (2001), 101-116.

[5] S. De Marchi and M. Vianello, Fast evaluation of discrete integral transforms by Chebyshev and Leja polynomial approximation, in: “Constructive Functions Theory” (Varna 2002), B. Bojanov Ed., DARBA, Sofia, 2003, pp.

347-353.

[6] L. Greengard, Fast algorithms for classical physics, Science 265 (1994), 909-914.

[7] T. H˚avie, Chebyshev series coefficients of a function, CERN Program Library, algorithm E406, 1986 (http://wwwinfo.cern.ch/asd/cernlib/mathlib.html).

[8] W. Hackbusch and B.N. Khoromskij, Towards

-matrix approximation of the linear complexity, in: Operator Theory: Advances and Applications, vol. 121, Birkh¨auser, 2001, pp. 194-220.

[9] A. Mardegan, “Bivariate Chebyshev series and approximation of integral operators”, Laurea Thesis in Mathe- matics (Italian), University of Padova, 2002 (advisors M. Vianello and A. Sommariva).

[10] L. Reichel, Fast solution methods for Fredholm integral equations of the second kind, Numer. Math. 57 (1990), 719-736.

[11] T. J. Rivlin, “The Chebyshev polynomials”. Pure and Applied Mathematics. Wiley-Interscience, New York- London-Sydney, 1974.

[12] A. Sommariva, M. Vianello and R. Zanovello, Adaptive bivariate Chebyshev approximation, in preparation.

[13] M. Vianello, Chebyshev-like compression of linear and nonlinear discretized integral operators, Neural, Parallel and Sci. Comput. 8 (2000), 327-353.