# Fast Solvers of Weakly Singular Integral Equations of the Second Kind.

1 IntroductionConsider the weakly singular Fredholm integral equation of the second kind

u(x) = [[integral].sup.1.sub.0] (a(x,y) [[absolute value of x - y].sup.-v] + b(x,y)) u(y)dy + f (x), 0 [less than or equal to] x [less than or equal to] 1, (1.1)

where 0 < v < 1. Denote by [C.sup.k] ([OMEGA]) the set of k times (k [greater than or equal to] 0) continuously differentiable functions on a domain [OMEGA]; in particular, C = C[0,1] = [C.sup.0][0,1] denotes the Banach space of continuous functions f on [0,1] with the usual norm [mathematical expression not reproducible]. By [C.sup.mv] = [C.sup.mv](0,1) (m [member of] N, 0 < v < 1) we denote the Banach space of functions f [member of] C[0,1] [intersection] [C.sup.m](0,1) such that

[mathematical expression not reproducible]

For given m [member of] N := {1, 2,... } and v [member of] (0,1) we assume that

(A1) f [member of] [C.sup.mv](0,1); (A2) a, b [member of] [C.sup.2m]([0,1] x [0,1]);

(A3) the homogeneous equation u(x)= [[integral].sup.1.sub.0](a(x, y)[[absolute value of x-y].sup.-v] + b(x, y)) u(y)dy, corresponding to (1.1) has in C[0,1] only the trivial solution u = 0.

Introduce also the following strengthened smoothness condition for functions a and b:

(A2') a,b [member of] [H.sup.2m,[mu]]([0,1] x [0,1]) with a [mu] [member of] (0,1].

The Hoelder space [H.sup.2m,[mu]]([0,1] x [0,1]) consists of functions v [member of] [C.sup.2m]([0,1] x [0,1]) with [([partial derivative]/[partial derivative]x).sup.i] [([partial derivative]/[partial derivative]x).sup.j]v(x, y), i + j = 2m, satisfying the Hoelder condition with the exponent [mu] [member of] (0,1] :

[mathematical expression not reproducible].

Denote by T = A + B the integral operator of equation (1.1) with operators A and B defined by

[mathematical expression not reproducible].

The operator T : C[0,1] [right arrow] C[0,1] is compact; it is compact also as an operator from [C.sup.m,v](0,1) into [C.sup.m,v](0,1) (see [12]); thus, by Fredholm alternative, equation (1.1) has a solution u [member of] [C.sup.m,v](0,1) which is unique in C[0,1].

Our aim is to construct fast/quasifast solvers of equation (1.1). In a fast solver, the conditions of optimal accuracy and minimal arithmetical work are met. We mean the order optimality and order minimal work on a class of problems. In our case the class of problems is defined by the smoothness conditions which we set above on the free term and the kernel of equation (1.1), see (A1), (A2) or (A1), (A2'). More precisely, we use the following notions of fast/quasifast solvers.

Definition 1. By a (C, [C.sup.m,v])-fast solver of equation (1.1) we mean a solver which produces approximate solutions un [member of] C[0,1], n [member of] N, such that

* given the values of a, b and f, each at not more than n* points (depending on the solver, with [n.sub.*] [right arrow] [infinity] as n [right arrow] [infinity]), the parameters of un can be determined at the cost of [[gamma]'.sub.m][n.sub.*] arithmetical operations and an accuracy

[mathematical expression not reproducible] (1.2)

is achieved, where u is the solution of (1.1);

* having the parameters of [u.sub.n] in hand, the value of [u.sub.n] at any point x [member of] [0,1] is available at the cost of arithmetical operations.

Here the constants [c.sub.m], [[gamma].sub.m], [[gamma]'.sub.m] are independent of f and n.

Note that estimate (1.2) is information optimal even in the case where a(x, y) = 0 for x, y [member of] [0,1] (in this case the solution of (1.1) can be presented in the form u = [(I - B).sup.-1] f, where I is the identity mapping and [(I - B).sup.-1] is the inverse of the operator I - B). Namely (see original work [34] or lecture notes [29]), for any m, m' [member of] N, [beta] > [bar.[beta]] > 1 and any solver of (1.1) with a(x, y) = 0 depending on [n.sub.*] evaluation points for f [member of] [C.sup.m] = [C.sup.m][0,1] and b [member of] [C.sup.m]'([0,1] x [0,1]), there is a "bad" pair f, b satisfying

[mathematical expression not reproducible],

and such that, disregarding the amount of arithmetical work, the lower error bound

[mathematical expression not reproducible]

holds where [c.sub.0] is a positive constant depending only on m, m', [beta] and [beta]. Thus, under traditional assumptions f [member of] [C.sup.m][0,1], b [member of] [C.sup.m]([0,1] x [0,1]), i.e. for m' = m, only the accuracy order [mathematical expression not reproducible] can be achieved by any solver (this partial result has been established already in [4]). A further consequence of the lower error bound is that accuracy (1.2) is possible only if m' > 2m, and this explains the constellation of our assumption (A2) with m' = 2m.

We speak about a ([L.sup.p],[C.sup.m],v)-fast solver (1 [less than or equal to] p < [infinity]) if the accuracy requirement (1.2) in Definition 1 is replaced by [mathematical expression not reproducible], where [parallel]u[parallel]][sub.p] = [([[integral].sup.1.sub.0][[absolute value of u(x)].sup.p]dx).sub.1/p] is the standard norm of u in [L.sup.p](0,1). Similarly, we obtain a (C, [C.sup.m])-fast solver if in the accuracy requirement (1.2) the norm [mathematical expression not reproducible] is replaced by [mathematical expression not reproducible] is replaced by [mathematical expression not reproducible].

Definition 2. In a (C, [C.sup.m,v])-quasifast solver, the accuracy requirement (1.2) is replaced by

[mathematical expression not reproducible], (1.3)

maintaining other requirements of Definition 1.

Remark 1. Estimate (1.2) can be rewritten with respect to the complexity

[n.sub.**] :=[[gamma].sub.n][n.sub.*]

of the solver in the equivalent form

[mathematical expression not reproducible].

This form of the estimate enables a comparison of (C, [C.sup.m,v])-fast solvers with different complexity parameters [[gamma].sub.m] : to smaller [C.sup.m] there corresponds more effective solver.

Remark 2. Consider also an alternative definition of a (C, [C.sup.m,v])-quasifast solver requiring accuracy (1.2) but allowing [[bar.[gamma]].sub.m], [n.sub.*]log [n.sub.*] arithmetical operations. Then with respect to the complexity [n.sub.**] = [[bar.[gamma]].sub.m], [n.sub.*]log [n.sub.*] estimate (1.2) takes the form

[mathematical expression not reproducible],

where w(x) = x log x, [w.sup.-1](x) ~ x/log x as x [right arrow] to, i.e ([w.sup.-1](x) log x)/x [right arrow] 1 as x [right arrow][infinity]. We see that for m [greater than or equal to] 2 Definition 2 is more restrictive (leads to a more high accuracy) than the alternative definition.

An intensive investigation of complexity for various kind of problems was started in [22,23]. In [16,17,18,34] the complexity of the approximate solutions of Fredholm integral equations of the second kind with smooth kernels has been studied. Actually, also in [28,30,31,33] fast or (C, [C.sup.m])-quasifast solvers have been constructed only for integral equations without singularities; for (1.1) this corresponds to the case a(x,y) [equivalent to] 0. The construction of (C, [C.sup.m])-fast/quasifast solvers of periodic weakly singular integral equations of the second kind in case a = 0 has been undertaken in [14]. Also some results of [2,5,19,21] can be interpreted as a construction of ([L.sup.2], [C.sup.m])-fast/quasifast or ([L.sup.2], [W.sup.m,2])-fast/quasifast solvers of periodic weakly singular integral equations ([W.sup.m,2] is the Sobolev space of functions on (0,1), see Section 3.1). However, up to now, the construction of (C, [C.sup.m,v])-fast/quasifast solvers for nonperiodic equations (1.1) was an open problem. In the present paper we construct the solvers which under the conditions (A1-(A3) are (C, [C.sup.m,v])-quasifast and ([L.sup.p], [C.sup.m,v])-fast, 1 [less than or equal to] p < [infinity]. Moreover, these solvers are (C, [C.sup.m,v])- fast under the conditions (A1), (A2'), (A3). Since we must discretize functions a and b of two variables, we use in our constructions [n.sub.*] = O([n.sup.2]) that is more convenient rather than n* = n. Perhaps, for the numerical praxis the obtained solvers are of too complicated structure, so the results of the paper have mainly theoretical interest, they characterize the smallest possible complexity of discretization methods for weakly singular integral equations of the second kind. Thus we obtain a possibility to estimate how "good" an arbitrary discretization method is from the point of view of complexity.

We now outline the rest of the present paper. In Section 2 we introduce a change of variables and after that a change of unknown functions that reduce (1.1) into a periodic problem. Section 3 contains preliminaries mainly about the trigonometric interpolation. In Section 4 we adapt and modify the method of [14] for the periodized version of equation (1.1). After some preparation work (Section 5), in the course of Sections 6-7, we reorganize this method to obtain fast/quasifast solvers for (1.1). In Section 8 we shortly formulate some open problems which we hope to study in the future.

Throughout the paper c, c', [c.sub.1], ... are some positive constants which can be different in different occurrences.

2 Periodization of the integral equation

It is well known [6, 12,26,32] (see also [11, 15,20]) that the derivatives of a solution to a weakly singular integral equation such as (1.1), in general, have certain boundary singularities. With the help of a suitable change of variables [8,10,13,25] (see also [3,7]) in the equation, these boundary singularities can be suppressed. Below we use a change integration variables and a change of the unknown functions to transform (1.1) into a 1-periodic problem.

To reduce (1.1) to a periodic form used in [14] we need a smooth function g(t), 0 < t < 1, which will be extended to 1-periodic function [??]. For v [member of] (0,1) and m [member of] N, we introduce the function g = g(t), 0 < t < 1, with

[mathematical expression not reproducible], (2.1)

where [gamma](t) is a polynomial of degree 4m + 1 determined by the conditions

[mathematical expression not reproducible],

where j = 0,1,..., 2m. After that we extend g from (0,1) into a 1-periodic function [??][member of][C.sup.2m](R\Z), where R:=(-[infinity], [infinity]) and Z:={..., -2, -1, 0,1, 2, ... }. Then (compare [14])

[absolute value of [[??].sup.(j)](t)] [less than or equal to] c[[absolute value of t].sup.-v-j], for 0 < [absolute value of t] [less than or equal to] 1/2, j = 0,1,..., 2m, (2.2)

[??](t) - [[absolute value of t].sup.-v] = 0, for [absolute value of t] [less than or equal to] 1/3. (2.3)

Perform in equation (1.1) the change the variables x = [phi](t), y = [phi]s), where [phi] : [0,1] -> [0,1] is given by the formula (see, e.g. [8,13,25])

[mathematical expression not reproducible]; (2.4)

condition on the smoothing parameter r [member of] N will be set later. Clearly, [phi] is a polynomial of degree [mathematical expression not reproducible]. Moreover, we have [phi](0) = 0, [phi](1) = 1, [phi]'(t) > 0 for 0 < t < 1. Since ([phi](t) - [phi] (s)j/(t - s) > 0 for 0 [less than or equal to] t, s [less than or equal to] 1, t [not equal to] s, equation (1.1) takes the form

[mathematical expression not reproducible],

or after some reorganizing,

[mathematical expression not reproducible], (2.5)

where for 0 [less than or equal to] t, s [less than or equal to] 1, [bar.u](t) = u([phi](t)), [bar.f](t) = f([phi](t)),

[mathematical expression not reproducible].

Since [phi](t) is a polynomial of degree 2r - 1, [PHI](t, s) is a polynomial of degree 2r - 2. Now we introduce a change of the unknown function. With respect to

[??](t) := [phi]'[(t).sup.(1-v)/2][bar.u](t) = [phi]'[(t).sup.(1-v)/2]u([phi](t))

equation (2.5) reads as

[mathematical expression not reproducible], (2.6)

or

[mathematical expression not reproducible], (2.7)

where

[mathematical expression not reproducible] (2.8)

with [??] and [??] defined by

[mathematical expression not reproducible]. (2.9)

Besides the equality [??](t) = [phi]'[(t).sup.(1-v)/2][bar.u](t), the solutions of equations (2.5) and (2.6) satisfy the integral relation

[mathematical expression not reproducible], (2.10)

where

[mathematical expression not reproducible]. (2.11)

The values of polynomials [phi](t) and [PHI](t, s) at one point can be computed in O(1) arithmetical operations, see [25] for corresponding procedures. Hence the values of [bar.a](t, s), [??](t, s), a*(t, s), [bar.b](t, s), [??](t, s), [b.sub.*](t, s) at one point can be computed at the cost of O(1) arithmetical operations provided that the values a([phi](t), [phi](s)) and b([phi](t), [phi](s)) are given. Using a uniform grid for t and s, a(x, y) and b(x, y) must be given or evaluated on a graded grid with respect to x and y. Due to (2.3), [[absolute value of t - s].sup.-v] - [??](t - s) = 0 in the vicinity of the diagonal t = s, thus [bar.b](t, s), [??](t, s) and [b.sub.*](t, s) are regular on the diagonal t = s of the square 0 [less than or equal to] t, s [less than or equal to] 1 but there appear point singularities at (0,1) and (1,0) of the term [??](t - s). Further, [PHI](t, s) vanishes at (0,0) and (1,1) causing there point singularities of [PHI][(t, s).sup.-v] of the order [(t+s).sup.-(r-1)v] and [((1-1) + (1 -s).sup.-(r-1)v] , respectively (see [25]):

[mathematical expression not reproducible], (2.12)

where j = 0, 1 . . . , 2m; for r > 2 these singularities are more strong than the singularities of [g.sup.(j)], see (2.2). All these four point singularities can be suppressed by the factors [phi]'[(t).sup.(1-v)/2] and [phi]'[(s).sup.(1+')/2] in the expressions for [??], [??] and by the factor [phi]'[(s).sup.(1+')/2] in the expressions for a*,b*. Actually, an analysis shows that the functions [??],[??], [a.sub.*] and [b.sub.*] can be extended so that these extensions (which we denote again by [??], [??], [a.sub.*], [b.sub.*]) belong to [C.sup.2m]([0,1] x [0,1]) provided that the smoothing parameter r is sufficiently large: the condition

r - 1 > 4m/(1 - v) (2.13)

is sufficient. Namely, under condition (2.13) it holds that

[mathematical expression not reproducible], (2.14)

for any t [member of] [0,1] and j = 0,1,..., 2m.

Indeed, let t [member of] [0,1] , 0 < s [less than or equal to] 1/2 and j = 0, 1, ..., 2m. Then we obtain from (2.12) the estimate [mathematical expression not reproducible], and from (2.4) the estimate

[mathematical expression not reproducible].

Therefore,

[mathematical expression not reproducible],

with (r - 1)((1 - v)/2) - 2m > 0, if r - 1 > 4m/(1 - v), and (2.14) follows.

Similarly, by symmetry,

[mathematical expression not reproducible],

for any t [member of] [0,1] and j = 0,1,..., 2m. Thus, the derivatives

[mathematical expression not reproducible]

have under the condition (2.13) no singularities at points (t, s) = (0, 0) and (t, s) = (1,1) which, in turn yields that [??], [??], [a.sub.*], [b.sub.*] [member of] [C.sup.2m]([0,1] x [0,1]).

Moreover, under the condition (2.13),

[mathematical expression not reproducible] (2.15)

with 0 [less than or equal to] j + k < 2m, and

[mathematical expression not reproducible], (2.16)

where [GAMMA] is the boundary of the square 0 [less than or equal to] t, s [less than or equal to] 1. Relations (2.15) allow to treat [??] and [??] as [C.sup.2m](R x R)-smooth 1-biperiodic functions, i.e., [mathematical expression not reproducible]. According to (2.16) [a.sub.*](t, s) and [b.sub.*](t, s) can be treated as [C.sup.2m]([0,1] x R)-smooth functions which are 1-periodic with respect to s. Further, (2.13) and f [member of] [C.sup.m,v] (0,1) imply that [bar.f], [??] [member of] [C.sup.m][0,1],

[mathematical expression not reproducible],

where the constants c and c' are independent of f; in particular, we can treat [??] as a [C.sup.m](R)-smooth 1-periodic function, i.e., [mathematical expression not reproducible].

3 Preliminaries

3.1 Some notations

We will use the following notations for spaces and norms in them: [C.sup.m][0,1] is the space of m times (m [greater than or equal to] 0) continuously differentiable functions u on [0,1], [mathematical expression not reproducible] is the space of 1-periodic functions u on R with the same norm [mathematical expression not reproducible]; the norm in [L.sup.p](0,1) , 1 [less than or equal to] p [less than or equal to] [infinity], is denoted

[mathematical expression not reproducible];

[mathematical expression not reproducible], is the space of 1-periodic functions [??] with the same norm: [mathematical expression not reproducible], is the Sobolev space of functions u on (0,1) equipped with the norm

[mathematical expression not reproducible];

[mathematical expression not reproducible], is the Sobolev space of 1-periodic functions [??] with the same norm [mathematical expression not reproducible], is the Hoelder space of functions u [member of] [C.sup.m][0,1] with [u.sup.(m)] satisfying the Hoelder condition with the exponent [lambda];

[mathematical expression not reproducible];

[[??].sup.m,[lambda]](R), 0 < [lambda] [less than or equal to] 1, is the Hoelder space of 1-periodic functions [??] with the same norm [mathematical expression not reproducible].

Next we introduce some known results about trigonometric interpolation and local interpolation by algebraic polynomials.

3.2 Representation forms for a trigonometric polynomial

For n [member of] N, we denote

[Z.sub.n] = {k [member of] Z : -n/2 < k [less than or equal to] n/2}, [[tau].sub.n] = span{[e.sup.ik2[pi]t] : k [member of] [Z.sub.n]}.

Thus [[tau].sub.n] consists of trigonometric polynomials, dim [[tau].sub.n] = n. There are two possible representations of [v.sub.n] [member of] [[tau].sub.n] - through its Fourier coefficients [[??].sub. n](k), [[??].sub.n](k) = [[integral].sup.1.sub.0] [v.sub.n](t)[e.sup.-ik2[pi]t] dt, k [member of] [Z.sub.n], and through its nodal values [v.sub.n]([jn.sup.-1]), j = 0, ..., n - 1:

[mathematical expression not reproducible]. (3.1)

The functions [[phi].sub.n,j], [member of] [[tau].sub.n] j = 0, 1, .. ., n - 1, called fundamental trigonometric polynomials, satisfy

[[phi].sub.n,j] (1n-1) = j, j,1 = 0,.. ., n - 1, (3.2)

where [[delta].sub.j,l] is the Kronecker symbol. Having the nodal values [v.sub.n] [member of] [[tau].sub.n] in hand, its Fourier coefficients are given by

[mathematical expression not reproducible],

where [[??].sub.n] is the vector with components [[??].sub.n](k), k [member of] [Z.sub.n], [[v.bar].sub.n] is the vector with components [v.sub.n]([jn.sup.-1]), j = 0, ..., n-1, and [F.sub.n] is the discrete Fourier transform.

Conversely, having the Fourier coefficients in hand, the nodal values of [v.sub.n] [member of] [[tau].sub.n] are given by the inverse discrete Fourier transform following from (3.1):

[mathematical expression not reproducible].

So we can change the form of representation of a trigonometric polynomial where needed. In usual matrix calculus, an application of [F.sub.n] or [F.sup.-1.sub.n] costs [n.sup.2] flops. Using fast Fourier transform (FFT) techniques, both transforms can be implemented in O(n log n) flops. See [21] for further discussions.

3.3 Trigonometric orthogonal and interpolation projections

For v [member of] [L.sup.1](0,1) and n [member of] N the Fourier projection [P.sub.n]v is defined by

[mathematical expression not reproducible].

For v [member of] [L.sup.2](0,1), [P.sub.n]v is the orthogonal projection of v onto [[tau].sub.n]. Clearly, we have [([P.sub.n]v).sup.(m)] = [P.sub.n][v.sup.(m)] for v [member of] [[??].sup.m](R). For v [member of] [??](R), the interpolation projection [Q.sub.n]v is defined by the requirements

[Q.sub.n]v [member of] [[tau].sub.n], ([Q.sub.n]v)([jn.sup.-1]) = v([jn.sup.-1]), j = 0, ..., n - 1.

Due to (3.2), [mathematical expression not reproducible], hence the Fourier coefficients [mathematical expression not reproducible], of [Q.sub.n]v can be computed from the sample values v([jn.sup.-1]), j = 0,..., n - 1, by FFT in O(nlogn) flops. It is known [35] that

[mathematical expression not reproducible] (3.3)

[mathematical expression not reproducible]. (3.4)

Here the constants c and cp are independent of n; we always assume that n > 2 in order to simplify the citing of estimates containing the factor log n. The following estimates are direct consequences of (3.3) and (3.4):

[parallel]v - [P.sub.n]v[parallel].sub.[infinity]] [less than or equal to] [c.sub.m][n.sup.-m](log n)[parallel][v.sup.(m)][parallel][sub.[infinity]], v [member of] [[??].sup.m,p](R), m [member of] N, (3.5)

[parallel]v - [P.sub.n]v[parallel].sub.p] < [c.sub.m,p][n.sup.-m][parallel][v.sub.(m)][parallel][sub.p], v [member of] [[??].sup.m,p](R), m [member of] N, 1 < p < [infinity], (3.6)

[mathematical expression not reproducible]. (3.7)

The constants in the estimates (3.5)-(3.7) are independent of n and v.

3.4 Local interpolation by polynomials

For n [member of] N denote h = 1/n. To u [member of] [??](R), assign the piecewise polynomial interpolant [[PI].sub.h,m]u [member of] [??](R) which is defined on every subinterval [ih, (i + 1)h] independently of other subintervals as an algebraic polynomial [u.sub.i] of degree m -1 (of order m) such that [u.sub.i](jh) = u(jh) for j - i [member of] [Z.sub.m], m [member of] N. Well known error estimates for a polynomial interpolant (cf. [1, 10]) yield the following results.

Lemma 1. (i) For u [member of] [[??].sup.m](R) (m [member of] N), it holds

[mathematical expression not reproducible];

at x = ih, i [member of] Z, this holds for both one side limits of [([[PI}.sub.h,m]u).sup.(k)](x).

(ii) For u [member of] [[??].sup.m,[lambda]](R), m [member of] {0} [union] N, 0 < [lambda] < 1, it holds

[mathematical expression not reproducible].

4 An approximate method for the periodized problem

In Section 2 we obtained an 1-periodic problem (2.6) with [mathematical expression not reproducible] satisfying (2.2) and (2.3). Fast solving of such a problem has been examined in [14]. In this section we recall and modify some results of [14] applied to equation (2.6).

For n [member of] N, let n' [member of] N be such that

n' [greater than or equal to] 2n, n' ~ [n.sup.[tau]], 2m/(m + 1 - v) <t< 2, (4.1)

where n' ~ [n.sup.[tau]] means that n'/[n.sup.[tau]] [right arrow] 1 as n [right arrow] [infinity]. We approximate equation (2.7) (equation (2.6)) by the equation

[mathematical expression not reproducible], (4.2)

where [P.sub.n']f is an approximation for the free term f in equation (2.7) and

[mathematical expression not reproducible] (4.3)

is an approximation for the integral operator [mathematical expression not reproducible] of equation (2.6) (see (2.8) and (2.9)). Here [P.sub.n] and [Q.sub.n] are respectively the orthogonal and interpolation projection operators introduced in Section 3.3,

[mathematical expression not reproducible],

(s in the index of [Q.sub.n;s] refers that [Q.sub.n] is applied w.r.t. the argument s),

[mathematical expression not reproducible],

where i = 0,..., n and [L.sub.j,n] (j [greater than or equal to] 1) is some difference approximation on the grid i/n (i G Z) of the differential operator [L.sub.j] = [[PI].sup.j=1.sub.l=0] ([(2[pi]i).sup.-1] [partial derivative]/[partial derivatives]s - lI) of the accuracy [mathematical expression not reproducible]; for j = 0 we put [L.sub.0] = [L.sub.0,n] = I. The matrix form of [[??].sup.(m).sub.n] needs also the values [[alpha].sub.j,n](i/n'), i = 0, ..., n' - 1, which we approximate via interpolation of [[alpha].sub.j,n] (i/n), i = 0, ..., n, by splines of degree 2m. See [14] for more detailed comments on the listed operators.

Lemma 2. Assume (A2) (which implies that [mathematical expression not reproducible]. Let n, n' [member of] N, and let n' ~ [n.sup.[tau]], [tau] > 1. Then for 1/(1 - v) < p < [infinity],

[mathematical expression not reproducible]; (4.4)

for 1/(1 - v) < p [greater than or equal to] [infinity], 0 < [lambda] < 1 - v - [p.sup.-1],

[mathematical expression not reproducible]; (4.5)

for 1/(1 - v) < p < [infinity], 0 < [lambda] < 1 - v - [p.sup.-1], v [member of] [[??].sub.m,p](R),

[mathematical expression not reproducible], (4.6)

[mathematical expression not reproducible], (4.7)

and, strengthening (A2) to the assumption (A2'),

[mathematical expression not reproducible]. (4.8)

Proof. Let 1/(1 - v) < p < [infinity]. Since I - [P.sub.n] as an orthogonal projector in [L.sup.2](0,1) is self-adjoint, it holds for t [member of] [0,1] that

[mathematical expression not reproducible].

Using (2.2) for j = 0 and j = 1, it is easy to check that for [absolute value of [sigma]] [less than or equal to] [delta]

[mathematical expression not reproducible]. (4.9)

By Nikolski's inequality (formulated in [14] as Lemma 2.2), estimate (4.9) implies that

[mathematical expression not reproducible],

which for n' ~ [n.sup.[tau]] yields (4.4). Estimates (4.5)-(4.8) are established in Lemma 3.5 of [14]; in the estimate (4.5) we corrected a misprint of [14].

Theorem 1. Assume (A1)-(A3). Moreover, assume that the smoothing parameter r in (2.4) satisfies (2.13) and the dimension parameter n' satisfies (4.1). Then equations (1.1) and (2.6) have unique solutions u [member of] [C.sup.m,v](0,1) and [mathematical expression not reproducible], respectively. These solutions are connected by the relation [??](t) = [phi]'[(t).sup.(1-v)/2]u([phi](t)); for sufficiently large n, say n [greater than or equal to] [n.sub.0], equation (4.2) has a unique solution [[??].sub.n,n'] [member of] [[tau].sub.n], and

[mathematical expression not reproducible], (4.10)

[mathematical expression not reproducible], (4.11)

with some positive constants c and c' which are independent of n and [??}.

Proof. For 1/(1 - v) < p [less than or equal to] [infinity], the operator [mathematical expression not reproducible] is compact, and since by the assumption (A3), the nullspace of I - T is trivial in C[0,1] implying that the null space of I - [??] is trivial in [??](R), the bounded inverse [mathematical expression not reproducible] exists. Hence equation (2.6) and with it also (1.1) are uniquely solvable. Further, due to (4.5), [mathematical expression not reproducible] as n [right arrow] [infinity] for 1/(1 - v) < p < [infinity], hence for sufficiently large n, say n [greater than or equal to] [n.sub.0], also [mathematical expression not reproducible] exists and is uniformly bounded in n:

[mathematical expression not reproducible]. (4.12)

Thus equation (4.2) is uniquely solvable for n [greater than or equal to] [n.sub.0].

Clearly, [mathematical expression not reproducible], or

[mathematical expression not reproducible]. (4.13)

Due to (4.12), [mathematical expression not reproducible] with n [greater than or equal to] [n.sub.0], 1/(1 - v) < p [greater than or equal to] [infinity]. Since [??] [member of] [C.sup.m](R), it follows from (3.5) and (3.6) that

[mathematical expression not reproducible].

This in view of (4.1) yields

[mathematical expression not reproducible]. (4.14)

Applying also (4.7) and (4.6) with any [lambda] [member of] (0,1 - v - [p.sup.-1]) we arrive at estimates (4.10) and (4.11).

Following ideas of [14], the matrix form of equation (4.2) reads as

[mathematical expression not reproducible], (4.15)

where [mathematical expression not reproducible] is the vector of values of [mathematical expression not reproducible] is the vector of the Fourier coefficients [mathematical expression not reproducible]

(k [member of] [Z.sub.n]') of the function [??], and

[mathematical expression not reproducible] (4.16)

is an n' x n' matrix. Here [F.sub.n'], [F.sup.-1.sub.n'] and [F.sub.2n], [F.sup.-1.sub.2n] are the Fourier transform matrices of dimensions n' x n' and 2n x 2n, respectively, changing the representation form of trigonometric polynomials (see Section 3); the projection-convolution [G.sub.j](I - [P.sub.n]) : [[tau].sub.n'] [right arrow] [[tau].sub.n] (j = 0,..., m - 1) is realized by the diagonal n' x n' matrix [G.sub.n',j] with the diagonal elements

[G.sub.n',j](k, k) = 0 for k [member of] [Z.sub.n], [G.sub.n',j] (k, k) = [[??].sub.j](k) for k [member of] [Z.sup.n']\[Z.sub.n];

the multiplication operator [M.sub.[alpha]j-n] (j = 0,..., m - 1) is realized by the diagonal n' x n' matrix Mn'-j with the diagonal elements

[M.sub.n',j](k, k) = [[alpha].sub.j-n] (k/n'), k = 0, 1, ..., n' - 1;

the projection [P.sub.n] : [[tau].sub.n] [right arrow] [[tau].sub.n] is realized by n x n' matrix [P.sub.n-n'] consisting of the n x n identity matrix completed from left and right by n x n' - n/2 zero matrix; the embedding [[tau].sub.n] [subset] [[tau].sub.2n] is realized by the 2n x n matrix [[epsilon].sub.2n-n] consisting of the n x n identity matrix complemented by n/2 x n zero matrix from above and below (for simplicity we assume that n and n' are even); the embedding [[tau].sub.2n] [subset] [[tau].sub.n] is realized by the n' x 2n matrix [[epsilon].sub.n'-2n] consisting of the 2n x 2n identity matrix completed by n' x n -2n/2 zero matrix from above and below; finally, [A.sub.2n] = ([a.sub.j,j']) and [B.sub.2n] = ([b.sub.j,j']) are 2n x 2n matrices with entries defined by the formulas

[mathematical expression not reproducible].

In (4.15) and (4.16) only the 2n x 2n matrix [A.sub.2n] + [B.sub.2n] and the diagonal n' x n' matrices [M.sub.n'-j] and [G.sub.n',j,] j = 0, ..., m - 1, and vector [[??].sub.n'] depend on the data of problem (1.1), namely on O([n.sup.2]) values [mathematical expression not reproducible], and on the Fourier coefficients [??](k) (k [member of] [Z.sub.n'+m-1]) of the function [mathematical expression not reproducible] defined due to (2.1), which can be computed in O([n.sup.2]) arithmetical operations with a very high accuracy O([n.sup.-4m]) from the values on a suitable graded grid consisting of [n.sup.2] points; see [14] for details. The application of [A.sub.2n]+[B.sub.2n] to an 2n-vector costs O([n.sup.2]), the application of FFT transformation matrices [F.sup.n'] and [F.sup.-1.sub.n'] of dimension n' x n' to an n'-vector costs O(n' log n), and the application of other matrices in Tn' is cheaper. Thus the application of [[T.bar].sub.n]' to a n'-vector costs O([n.sup.2]) + O(n' log n) arithmetical operations. This enables to solve system (4.15) in O([n.sup.2]) arithmetical operations by the two grid iteration method combined with the GMRES [9,21,24,27] on the coarse level.

It remains to comment on the computation of the Fourier coefficients [??](k), k [member of] [Z.sub.n']. In [14], a more complicated approximation of the free term is used that restricts the computation of Fourier coefficients to k [member of] [Z.sub.n]; this approximation is not suitable for goals of the present paper. Nevertheless, the idea of [14] can be used to compute also the Fourier coefficients [??](k), k [member of] [Z.sub.n']: in a special way described below, we approximate [??] by a function [[??].sub.fn,n"] depending on the parameters n and n" ~ [n.sup.[sigma]], [tau] < [sigma] < 2 (with t from (4.1)) so that the Fourier coefficients [mathematical expression not reproducible] are for k [member of] [Z.sub.n]' (exactly) computable in O([n.sup.2]) arithmetical operations and, with a p [member of] (1/(1 - v), [infinity]),

[mathematical expression not reproducible]. (4.17)

The following remark reveals that this accuracy occurs to be sufficient for our purposes.

Remark 3. Let [[??].sub.n,n'] be the solution of equation (4.2), and let [[??].sub.n,n',n"] be the solution of the perturbed equation [mathematical expression not reproducible], where [[??].sub.n,n"] satisfies (4.17) with a p [member of] (1/(1 - v), [infinity]). Then, for sufficiently large n,

[mathematical expression not reproducible]. (4.18)

This immediately follows from [mathematical expression not reproducible] and (4.12).

Let us describe how a suitable [[??].sub.n,n"] can be constructed. Using (smooth) splines of degree m with knots i/[n.sup.2], i [member of] Z, we construct in O([n.sup.2]) arithmetical operations the interpolant or quasi-interpolant [[??].sub.n] of [??] which satisfies (cf. [25]) with a p [member of] (1/(1 - v), [infinity]) the following inequalities:

[mathematical expression not reproducible].

Take a number n" ~ [n.sup.[sigma]], [tau] < [sigma] < 2 with [tau] from condition (4.1). Starting from [[??].sup(0).sub.n) = [[??].sub.n], compute the 1-periodic antiderivatives

[mathematical expression not reproducible],

where l [greater than or equal to] 2m+1/2 [tau]/[sigma] - [tau], and put [mathematical expression not reproducible]. The values [[??].sup.(-l).sub.n](i/n"), i = 0,..., n" - 1, determining the interpolant [Q.sub.n"][[??].sup.(-l).sub.n] are available at the cost of O([n.sup.2]) arithmetical operations. By FFT we can compute the Fourier coefficients [mathematical expression not reproducible], at the cost of O(n" log n) arithmetical operations. The Fourier coefficients of [P.sub.n][[??[.sub.n,n"] can be picked from the equality

[mathematical expression not reproducible].

Repeating the argument of [14] we get the estimate

[mathematical expression not reproducible]

Since [mathematical expression not reproducible], the estimate (4.17) follows:

[mathematical expression not reproducible].

Our next step is to compute the approximate solution of equation (2.5) using integral relation (2.10) in which we replace T, the solution of (2.6), by Tn-n', the solution of (4.2). Recall that the kernel of integral operator in (2.10) is periodic only w.r.t. argument s, so we cannot immediately use the techniques of the present section. To make this possible, we first decompose the kernel extracting from it a periodic part and a polynomial part. This is done in Section 6 after some preliminaries (Section 5).

5 Extracting a periodic and polynomial parts of a function

Denote by [P.sub.i] the space of polynomials z of degree not exceeding i + 1 and satisfying [[integral].sup.1.sub.0] z(t)dt = 0. There exist unique polynomials [z.sub.i] [member of] [P.sub.i], i = 0, 1, ..., such that

[z.sup.(k).sub.i](1) - [z.sup.(k).sub.i](0) = [[delta].sub.i-k] (Kronecker symbol), k = 0,1, 2,.... (5.1)

Indeed, fixing i, (5.1) is trivially fulfilled for k [greater than or equal to] i + 1, so we have to determine the coefficients [c.sup.ij], j = 0, ..., i + 1, of [z.sub.i](t) = [[summation].sup.i+1.sub.j=0] [c.sub.ij][t.sup.j] so that (5.1) holds for k = 0,..., i and [[integral].sup.1.sub.0] [z.sub.i](t)dt = 0. These conditions yield an i + 2 dimensional triangular system with nonzeroes on the main diagonal uniquely determining [c.sup.ij], j = 0, ..., i + 1. Clearly, [z.sub.0](t) = t - 1/2. Having [z.sub.i] in hand and knowing that [z.sub.i+1] exists and is unique, it is easy to check that it satisfies the recursion

[z.sub.i+1](t) = [[integral].sup.t.sub.0] [z.sub.i](s)ds + [[integral].sup.1.sub.0]s[z.sub.i](s)ds, i = 0, 1, ....

The first three polynomials z are as follows:

1 2 1 1 3 1 2 1

[z.sub.0](t) = t - 1/2, [z.sub.1](t) = 1/2 [t.sup.2] - 1/2t + 1/12, [z.sub.2](t) = 1/6[t.sup.3] - 1/4[t.sup.2] + 1/12 t.

Denote by [[??].sup.m][0,1] the subspace of functions [??] [member of] [C.sup.m][0,1] satisfying the periodic boundary conditions [[??].sup.(i)](1) - [[??].sup.(j)](0) = 0, i = 0,..., m. Every function w [member of] [C.sup.m][0,1] has the representation

[mathematical expression not reproducible]. (5.2)

Since an 1-periodic extension of a function [mathematical expression not reproducible] [0,1] is [C.sup.m] (R)-smooth, we can identify [[??].sup.m][0,1] with [[??].sup.m](R).

6 An approximate method for equation (1.1) (equation (2.5))

Let us apply decomposition (5.2) for [a.sub.*](t, s) and [a.sub.*](t, s) (see (2.11)) as functions of t:

[mathematical expression not reproducible].

In accordance to (5.2), the functions [[??].sub.*](t, s) and [[??].sub.*](t, s) are 1-periodic in t. Due to (2.13) it holds [[phi].sup.(j)](0) = [[phi].sup.(j)](1) = 0 for j = 1,..., 2m + 1 implying

[mathematical expression not reproducible],

[mu] = (1 + v)/2, and [mathematical expression not reproducible] for j = 0, ..., 2m. After 1-periodic extension, we have [mathematical expression not reproducible], and similarly [mathematical expression not reproducible], i = 0,..., 2m. Hence [mathematical expression not reproducible] (remember that [a.sub.*](t, s) and [b.sub.*](t, s) are 1-periodic in s). Denoting by [T.sub.*] = [A.sub.*] + [B.sub.*] the integral operator in (2.10), with [A.sub.*] and [B.sub.*] determined by

[mathematical expression not reproducible],

we obtain the decomposition

[mathematical expression not reproducible], (6.1)

where

[mathematical expression not reproducible] (6.2)

are periodic integral operators with biperiodic kernels, and the only nonperiodic operators in the decomposition (6.1) are [mathematical expression not reproducible]:

[mathematical expression not reproducible],

realizing the multiplication with the polynomials [z.sub.i]. We approximate the periodic integral operator [[??].sub.*] + [[??].sub.*] in (6.1) in analogy to (4.3) by the operator [mathematical expression not reproducible]. Also [[??].sub.i] + [[??].sub.i] in (6.1) could be approximated similarly as in (4.3) but since the coefficient functions [[??].sub.i](s) and [[??].sub.i](s) in (6.2) are independent of t, more simple approximations are available: we introduce for [mathematical expression not reproducible] the approximation [mathematical expression not reproducible], where

[mathematical expression not reproducible]

and [n'/2] is the integer part of n'/2 . Thus we approximate [T.sub.*] (see (6.1)) by

[mathematical expression not reproducible]. (6.3)

Given the sample values v(i/n'), i = 0, ..., n' - 1 of a function v [member of] [[tau].sub.n], the computation of ([T.sub.*-n-n'v])(i/n'), i = 0, ..., n' - 1, costs O([n.sup.2]) arithmetical operations (including the assembling of the matrix form of the operator), cf. Section 4. For the operators [T.sub.*] and [T.sub.*-n-n'], similar estimates as in Lemma 2 hold true.

Lemma 3. Assume (A2), and let n' ~ [n.sup.[tau]], [tau] > 1. Then for 1/(1-v) < p < [infinity],

[mathematical expression not reproducible]; (6.4)

for 1/(1 - v) < p [greater than or equal to] [infinity], 0 < [lambda] < 1 - v - [p.sup.-1],

[mathematical expression not reproducible]; (6.5)

for 1/(1 - v) < p < [infinity], 0 < [lambda] < 1 - v - [p.sup.-1], v [member of] [[??].sup.m-p](R),

[mathematical expression not reproducible], (6.6)

and, strengthening (A2) to the assumption (A2'),

[mathematical expression not reproducible]. (6.7)

Proof. By Lemma 2 the counterparts of the estimates (6.4)-(6.7) hold for [[??].sub.*] + [[??].sub.*] and its approximation [mathematical expression not reproducible], and the counterpart of (6.4) holds also for [[??].sub.i] + [[??].sub.i]. So we only have to check that the counterparts of estimates (6.5)-(6.7) hold for [[??].sub.i] + [[??].sub.i] and their approximation [mathematical expression not reproducible]. Split

[mathematical expression not reproducible]. (6.8)

Consider the first addend in the r.h.s. of (6.8). Let p and [lambda] satisfy the conditions 1/(1 - v) < p < [infinity], 0 < [lambda] < 1 - v - [p.sup.-1]. By (4.4), we obtain in support of (6.5)

[mathematical expression not reproducible];

for p = [infinity], according to [14] we again obtain

[mathematical expression not reproducible].

For v [member of] [[??].sup.m,p](R), due to (4.14) we obtain in support of (6.6)-(6.7)

[mathematical expression not reproducible].

Consider the second addend in the r.h.s of (6.8). We have with any w [member of] [[tau].sub.[n'/2]], [p.sup.-1] + [q.sup.-1] = 1 that

[mathematical expression not reproducible].

This supports estimates (6.4)-(6.7) since

[mathematical expression not reproducible],

and for [mathematical expression not reproducible], there exists a w [member of] [[tau].sub.[n'/2]] such that [parallel][[??].sub.i] - w[parallel][sub.[infinity]] [less than or equal to] [cn.sup.-2[tau]m].

In the equality [bar.u] = [T.sub.*][??] + [bar.f] which is a short writing of the integral relation (2.10), we approximate the solution [??] of (2.6) by the solution [[??].sub.n,n'] of (4.2), and we approximate the integral operator (6.1) by (6.3), obtaining

[[bar.u].sub.n,n'] = [T.sub.*,n,n'][[??].sub.n,n'] + [bar.f] (6.9)

which we treat as an approximate solution of equation (2.5). The approximation [[bar.u].sub.n,n'] is not discrete. Its discrete counterpart will be introduced and discussed in Section 7.

Theorem 2. Assume the conditions of Theorem 1. Then

[mathematical expression not reproducible], (6.10)

[mathematical expression not reproducible], (6.11)

where [bar.u](t) = u([phi](t)) is the solution of equation (2.5), u is the solution of equation (1.1), and [[bar.u].sub.n,n'] is defined by (6.9) in which [[??].sub.n,n'] is the solution of equation (4.2). If a and b satisfy (A2') then

[mathematical expression not reproducible], (6.12)

i.e. [parallel][bar.u] - [[bar.u].sub.n,n'][parallel] [n.sup.2m] [right arrow] 0 as n [right arrow] [infinity].

Proof. Since

[mathematical expression not reproducible],

we have

[mathematical expression not reproducible]. (6.13)

Due to (4.1), (1 + [tau])m > 2m; taking p < [infinity] sufficiently large and [lambda] > 0 sufficiently close to 1 - v - [p.sup.-1], we have [tau](m + [lambda]) > 2m, and the estimates (6.5), (4.11) imply for 1/(1 - v) < p < [infinity] that

[mathematical expression not reproducible], (6.14)

whereas (6.6)-(6.7) yield

[mathematical expression not reproducible], (6.15)

and in the case of (A2'),

[mathematical expression not reproducible]. (6.16)

Below we show that

[mathematical expression not reproducible]. (6.17)

Now the estimates (6.10)-(6.12) immediately follow from (6.13)-(6.17); actually, we obtain (6.11) only for 1/(1 - v) < p < [infinity]; to obtain (6.11) for smaller p [member of] [1,1/(1 - v)] we exploit the monotonicity in p of the norm [parallel]*[parallel][sub.p].

It remains to prove (6.17). Applying to both sides of equality (4.13) the operator T* and using the equality [mathematical expression not reproducible], we obtain

[mathematical expression not reproducible], (6.18)

where we took into account (4.12), the boundedness of [T.sub.*] : [[??].sup.p] [right arrow] C, and the uniform boundedness of operators [mathematical expression not reproducible] (see (4.5)).

Using the equality I - [P.sub.n'] = (I - [P.sub.n']) (2), (6.4) and (4.14), we estimate

[mathematical expression not reproducible].

According to (4.1), [tau](m +1 - v) > 2m, for sufficiently large p also [tau](m + 1 - v - 1/p) > 2m, hence

[mathematical expression not reproducible]. (6.19)

With the help of (6.5) and (4.14) we get similarly as in (6.14), (6.19)

[mathematical expression not reproducible].

Similarly to (6.15), (6.16) we have

[mathematical expression not reproducible]. (6.20)

Plugging (6.19)-(6.20) into (6.18) we obtain (6.17).

Remark 4. Consider the case where we use some approximation [[??].sub.n,n"] of [??] to compute the Fourier coefficients of f as in Remark 3 so that (4.17) and hence also (4.18) hold true. Then instead of (6.9) we obtain the approximation [[bar.u].sub.n,n',n"] = [T.sub.*,nn'] [[??].sub.n,n',n"] + [bar.f]. Following the proof scheme of Theorem 2 it is easily seen that, under conditions of Theorem 1,

[mathematical expression not reproducible] (A2').

Hence estimates (6.10)-(6.12) remain to be valid also for [[bar.u].sub.n,n',n"].

Remark 5. The operator [??] has the property (compare (3.2) in [14]) that for [mathematical expression not reproducible] is bounded; moreover, for those p and A, it can be proved by the techniques of [14] that [mathematical expression not reproducible] as n [right arrow] [infinity]. The definitions (6.1) and (6.3) of [T.sub.*] and [T.sub.*,n,n'] enable to extend these relations: for 1/1 - v < p [less than or equal to] [infinity], 0 < [lambda] < 1 - v - 1/p, [T.sub.*] : [[??].sup.m,p](R) - [H.sup.m,[lambda]][0,1] is bounded,

[mathematical expression not reproducible].

From here we conclude for the solution [[??].sub.n,n'] of equation (4.2) that

[mathematical expression not reproducible], (6.21)

[mathematical expression not reproducible]. (6.22)

Deriving (6.21) we exploited the fact that [mathematical expression not reproducible] for n [member of] N, 1 < p < [infinity]. Inequality (6.22) will be helpful in Section 7. It is valid also if we replace [[??].sub.n,n'] by [[??].sub.n,n',n"] assuming the conditions of Remark 3.

7 (C,[C.sup.m]) fast/quasifast solver of equation (1.1)

According to Section 4, the sample values [[??].sub.n,n'](i/n'), i = 0, ...,n' - 1 of the solution [[??].sub.n,n'] [member of] [[tau].sub.n] to (4.2) are available at the cost of O([n.sup.2]) arithmetical operations. After that also the values ([T.sub.*,n,n'][[??].sub.n,n'])(i/n'), i = 0, ..., n' of [T.sub.*,n,n'][[??].sub.n-n'] can be computed in O([n.sup.2]) arithmetical operations, and we can use the local (algebraic) polynomial interpolation to approximate [T.sub.*-n,n'][[??].sub.n,n'] between the grid points i/n', i = 0, ..., n'. Define the polynomially interpolated version [mathematical expression not reproducible] (see (6.9) and Section 3.4) as

[mathematical expression not reproducible], (7.1)

where [[PI].sub.n',m+1] is an operator of local interpolation of functions given on the grid {i/n' : i = 0, ..., n'} by polynomials of degree m (or of order m +1) and [mathematical expression not reproducible] is an operator of local interpolation by polynomials of degree m - 1 from the grid values on the net {i/[n.sup.2]) : i = 0, ..., [n.sup.2]}. Thus, the unknown parameters ([T.sub.*,n,n'] [[??].sub.n,n'])(i/n'), i = 0,..., n' of [[bar.v].sub.n,n'] are available at the cost of O([n.sup.2]) arithmetical operations, and having them in hand, the value of [[bar.v].sub.n,n'] at any point t [member of] [0,1] is available at the cost of O(1) arithmetical operations. We could define the approximate solution of equation (1.1) by the formula

[v.sub.n,n'](x) = [[bar.v].sub.n,n'] ([[phi].sup.-1](x)), 0 [less than or equal to] x [less than or equal to] 1, (7.2)

with [[[phi].sup.-1], the inverse of [phi] (see (2.4)), but since we cannot present a closed formula for [[phi].sup.-1](x) we first approximate it by a suitable local interpolation. Let us precompute [x.sub.i,n] = [phi](i/n) for i = 0, ..., n (this costs altogether only O(n) arithmetical operations) and use them to approximate t = [[phi].sup.-1](x) for any given x [member of] [0,1] via a local interpolation by polynomials of degree 2m - 1. Note that [[phi].sup.-1] [member of] [C.sup.2m-1/r] (0,1) where r is the (smoothing) parameter in the definition of [phi] (actually [[phi].sup.-1] [member of] [C.sub.l-1/r] (0,1) for any l [member of] N), and {[x.sub.i,n] : i = 0, ..., n} is a suitable graded grid for the interpolation of such functions - denoting by [[psi].sub.n] the interpolation approximation of [psi] = [[phi].sup.-1], we have

[mathematical expression not reproducible], (7.3)

see, e.g., [26]. Instead of (7.2), we define the final approximation to the solution of equation (1.1) via the formula

[u.sub.n,n'](x) = [[bar.v].sub.n,n'] ([[psi].sub.n](x)), 0 [less than or equal to] x [less than or equal to] 1. (7.4)

The grid values [T.sub.*,n,n'] [[??].sub.n,n'])(i/n')(i = 0, ..., n') and [bar.f](i/[n.sup.2]) = f ([phi](i/[n.sup.2]))(i = 0, ..., [n.sup.2]) can be considered as the parameters of the approximate solution (7.4). The grid values of f belong to a given information whereas the grid values of [T.sub.*,n,n'] [[??].sub.n,n'] are available at the cost of O([n.sup.2]) arithmetical operations using n* = O([n.sup.2]) sample values of a and b and the [n.sup.2] + 1 sample values of f just listed. To see that with (7.4) we have designed a fast/quasifast solver of equation (1.1), it remains to establish for unn' the estimates of type (1.2)/(1.3). Estimates (7.5)-(7.6) (see Theorem 3 below) mean that under condition a, b [member of] [C.sup.2m]([0,1] x [0,1]) approximation (7.4) defines a (C, [C.sup.m,v])-quasifast solver of equation (1.1) which is ([L.sup.p], [C.sup.m,v])-fast for 1 < p < to and, moreover, this solver is even (C, [C.sup.m,v])-fast if the mth derivatives of a, b are Hoelder continuous.

Theorem 3. Assume the conditions of Theorem 1. Then we have for all sufficiently large n [member of] N that

[mathematical expression not reproducible], (7.5)

where u is the solution of (1.1) and [u.sub.n,n'] is defined by (7.1), (7.4) with the solution [[??].sub.n,n'] of equation (4.2). The full computation cost of [u.sub.n,n'] is O([n.sup.2]) flops. So we have constructed a (C, [C.sup.m,v])-quasifast solver of equation (1.1); this solver is ([L.sup.p], [C.sup.m,v])-fast. Moreover,. under condition (A2') this solver is (C, [C.sup.m,v])-fast:

[mathematical expression not reproducible]. (7.6)

Proof. Let the conditions of Theorem 1 be fulfilled. With x = [phi](t), 0 [less than or equal to] t [less than or equal to] 1, we have for u, the solution of equation (1.1), and for its approximation [u.sub.n,n'], defined by (7.1) and (7.4), that

[mathematical expression not reproducible] .

We obtain the claims (7.5)-(7.6) estimating [bar.u] - [[bar.u].sub.n,n'] by (6.10)-(6.12), respectively, and noticing that in accordance to (7.1), (7.3) and (6.22)

[mathematical expression not reproducible]

and that in accordance to (6.9), (7.1) and (6.22) with sufficiently large p < [infinity] and [lambda] close to 1 - v,

[mathematical expression not reproducible].

Introducing a more dense basic interpolation set than {[x.sub.i,n] : i = 0,..., n} exploited above we obtain more accurate approximation of [[phi].sup-1] rather than (7.3).

For instance, the node set {[x.sub.i,n] n = [phi](i/[n.sup.2]) : i = 0, ..., [n.sup.2]} is still computable in O([n.sup.2]) arithmetical operations and leads to the estimate (cf. (7.3))

[mathematical expression not reproducible] .

In the following remark we assume quite moderate strengthening of (7.3).

Remark 6. Assume (A2') and let [parallel][[phi].sup.-1] - [[psi].sub.n][parallel][sub.[infinity]] = o([n.sup.-2m]). Then (cf. (7.6))

[mathematical expression not reproducible].

Thus, the main part of the error u - [u.sub.n,n'] is caused by the interpolation of f .

8 Some open problems for future study

The main purpose of the present paper has been to construct a fast/quasifast solver for a nonperiodical weakly singular integral equation of the form (1.1). To this end we have reduced the original problem to a periodic problem.

It seems that Theorem 3 remains partly valid when [P.sub.n'] [??] in (4.2) is replaced by [Q.sub.n][??] Note that this modified solver has computational advantages compared with (4.2) since the grid values of [??] and [Q.sub.n'][??] are known.

There also arises a question about extension of the obtained results to more general equations rather than (1.1). In particular, is it possible to modify the proposed construction of (C, [C.sup.m,v])-fast/quasifast solvers for equations (1.1) so that also some boundary singularities of a(x, y) and b(x, y) are allowed? Moreover, it is useful to extend the results of the paper to the case where a(x, y) and b(x, y) may have jumps on the diagonal x = y of the square 0 [less than or equal to] x, y [less than or equal to] 1 but are smooth in upper and lower triangles. In particular, can the results be extended to the case of weakly singular Volterra integral equations? We hope to answer these questions elsewhere.

https://doi.org/10.3846/mma.2018.039

Acknowledgements

This work was supported by institutional research funding IUT20-57 of the Estonian Ministry of Education and Research.

References

[1] K. Atkinson and W. Han. Theoretical Numerical Analysis. Springer, New York, 2009.

[2] W. Dahmen, H. Harbrecht and R. Schneider. Compression techniques for boundary integral equations-asymptotically optimal complexity estimates. SIAM J. Numer. Anal, 43:2251-2271, 2006. https://doi.org/10.1137/S0036142903428852.

[3] T. Diogo, P. M. Lima, A. Pedas and G. Vainikko. Smoothing transformation and spline collocation for weakly singular Volterra integro-differential equations. Appl. Numer. Math,, 114:63-76, 2017.

[4] K. V. Emel'yanov and A. M. Il'in. The number of arithmetical operations necessary for the approximate solution of Fredholm integral equations. USSR Comput. Math. Phys, 7:259-267, 1967. https://doi.org/10.1016/0041-5553(67)90160-7. (In Russian)

[5] K. Frank, S. Heinrich and S. Pereverzev. Information complexity of multivariate Fredholm integral equations in Sobolev classes. J. Complexity, 12:17-34, 1996. https://doi.org/10.1006/jcom.1996.0004.

[6] I. G. Graham. Singularity expansions for the solutions of second kind Fredholm integral equations with weakly singular convolution kernels. J. Integral Equations, 4:1-30, 1982.

[7] M. Kolk, A. Pedas and G. Vainikko. High-order methods for Volterra integral equations with general weak singularities. Numer. Funct. Anal. Optim, 30(10):1002-1024, 2009. https://doi.org/10.1080/01630560903393154.

[8] G. Monegato and L. Scuderi. High order methods for weakly singular integral equations with nonsmooth input functions. Math. Comput, 67:1493-1515, 1998. https://doi.org/10.1090/S0025-5718-98-01005-9.

[9] O. Nevanlinna. Convergence of iterations for linear equations. Birkhauser, Basel, 1993. https://doi.org/10.1007/978-3-0348-8547-8.

[10] K. Orav-Puurand, A. Pedas and G. Vainikko. Central part interpolation schemes for integral equations with singularities. J. Int. Eq. Appl, 29(3):401-440, 2017. https://doi.org/10.1216/JIE-2017-29-3-401.

[11] I. Parts, A. Pedas and E. Tamme. Piecewise polynomial collocation for Fredholm integro-differential equations with weakly singular kernels. SIAM J. Numer. Anal, 43:1897-1911, 2005. https://doi.org/10.1137/040612452.

[12] A. Pedas and G. Vainikko. Integral equations with diagonal and boundary singularities of the kernel. ZAA, 25:487-516, 2006. https://doi.org/10.4171/ZAA/1304.

[13] A. Pedas and G. Vainikko. Smoothing transformation and piecewise polynomial projection methods for weakly singular Fredholm integral equations. Comm. Pure and Appl. Anal, 5:395-413, 2006. https://doi.org/10.3934/cpaa.2006.5.395.

[14] A. Pedas and G. Vainikko. What is the complexity of periodic weakly singular integral equations? BIT Num. Math, 48:315-335, 2008. https://doi.org/10.1007/s10543-008-0181-0.

[15] A. Pedas and G. Vainikko. On the regularity of solutions to integral equations with nonsmooth kernels on a union of open intervals. J. Comp. Appl. Math, 229:440-451, 2009. https://doi.org/10.1016/jxam.2008.04.009.

[16] S. V. Pereverzev. On the complexity of the problem of finding the solutions of Fredholm equations of the second kind with smooth kernels. I. Ukrain. Math. Zh, 40(1):71-76, 1988. https://doi.org/10.1007/bf01056451.

[17] S. V. Pereverzev. On the complexity of the problem of finding the solutions of Fredholm equations of the second kind with smooth kernels. II. Ukrain. Math. Zh, 41(2):169-173, 1989. https://doi.org/10.1007/BF01060382.

[18] S. V. Pereverzev. Hyperbolic cross and the complexity of the approximate solution of Fredholm integral equations of the second kind with differentiable kernels. Sibirsk. Math. Zh, 32(1):85-92, 1991. https://doi.org/10.1007/BF00970164.

[19] S. V. Pereverzev and K. Sh. Makhkamov. Information complexity of weakly singular integral equations. Ukrainian Math. J, 46:1527-1533, 1994. https://doi.org/10.1007/BF01058886. (In Russian)

[20] J. Pitkaranta. Estimates for the derivatives of solutions to weakly singular Fredholm integral equations. SIAM J. Math. Anal, 11:952-968, 1980. https://doi.org/10.1137/0511085.

[21] J. Saranen and G. Vainikko. Periodic Integral and Pseudodifferential Equations with Numerical Approximation. Springer, Berlin, 2002. https://doi.org/10.1007/978-3-662-04796-5.

[22] J. F. Traub, G. Wozniakowski and H. Wozniakowski. A General Theory of Optimal Algorithms. Academic Press, New York, 1980.

[23] J. F. Traub, G. Wozniakowski and H. Wozniakowski. Information-Based Complexity. American Press, Boston, 1988.

[24] L. N. Trefethen and D. Bau. Numerical Linear Algebra. SIAM, Philadelphia, 1997. https://doi.org/10.1137/1.9780898719574.

[25] E. Vainikko and G. Vainikko. A spline product quasi-interpolation method for weakly singular Fredholm integral equations. SIAM J. Numer. Anal, 46:1799-1820, 2008. https://doi.org/10.1137/070693308.

[26] G. Vainikko. Multidimensional Weakly Singular Integral Equations. Springer-Verag, Berlin, 1993. https://doi.org/10.1007/BFb0088979.

[27] G. Vainikko. GMRES and discrete approximation of operators. Proc. Estonian Acad Sci. Phys. Math, 53:124-131, 2004.

[28] G. Vainikko. Fast solvers of integral equations of the second kind: quadrature methods. J. Integr. Eq. Appl., 17:91-120, 2005. https://doi.org/10.1216/jiea/1181075312.

[29] G. Vainikko. Fast solvers of integral equations. Lecture notes, HUT, UT, 2006. http://www.ut.ee/~gen/FASTlecturesSIAM.pdf

[30] G. Vainikko. Fast wavelet solvers of periodic integral equations. J. Analysis, 14:243-265, 2006.

[31] G. Vainikko, A. Kivinukk and J. Lippus. Fast solvers of integral equations of the second kind: wavelet methods. J. Complexity, 21:243-273, 2005. https://doi.org/10.1016/j.jco.2004.07.002.

[32] G. Vainikko and A. Pedas. The properties of solutions of weakly singular integral equations. J. Austral. Math. Soc, Ser.B, 22:419-430, 1980.

[33] G. Vainikko and I. Zolk. Fast spline quasicollocation solvers of integral equations. Math. Modelling and Analysis, 12:515-538, 2007. https://doi.org/10.3846/1392-6292.2007.12.515-538.

[34] A. G. Werschulz. Where does smoothness count the most for Fredholm equations of the second kind with noisy information? J. Complexity, 19:758-798, 2003. https://doi.org/10.1016/S0885-064X(03)00030-X.

[35] A. Zygmund. Trigonometric Series, volume 1, 2. Cambridge Univ. Press, 1959.

Sumaira Rehman, Arvet Pedas and Gennadi Vainikko

University of Tartu, Institute of Mathematics and Statistics

J.Liivi 2, Tartu, Estonia

E-mail: sumaira.rehman@ut.ee

E-mail(corresp.): arvet.pedas@ut.ee

E-mail: gennadi.vainikko@ut.ee

Received February 11, 2018; revised September 13, 2018; accepted September 13, 2018

Printer friendly Cite/link Email Feedback | |

Author: | Rehman, Sumaira; Pedas, Arvet; Vainikko, Gennadi |
---|---|

Publication: | Mathematical Modeling and Analysis |

Article Type: | Report |

Date: | Dec 1, 2018 |

Words: | 10248 |

Previous Article: | On Mathematical Modelling of Synthetic Measures. |

Next Article: | Existence of Solutions for Critical Systems with Variable Exponents. |

Topics: |