### Refine

#### Year of publication

#### Faculty / Organisational entity

We study the complexity of local solution of Fredholm integral equations. This means that we want to compute not the full solution, but rather a functional (weighted mean, value in a point) of it. For certain Sobolev classes of multivariate periodic functions we prove matching upper and lower bounds and construct an algorithm of the optimal order, based on Fourier coefficients and a hyperbolic cross approximation.

In recent years, Smolyak quadrature rules (also called hyperbolic cross points or sparse grids) have gained interest as a possible competitor to number theoretic quadratures for high dimensional problems. A standard way of comparing the quality of multivariate quadrature formulas
consists in computing their \(L_2\)-discrepancy. Especially for larger dimensions, such computations are a highly complex task. In this paper we develop a fast recursive algorithm for computing the \(L_2\)-discrepancy (and related quality measures) of general Smolyak quadratures. We carry out numerical comparisons between the discrepancies of certain Smolyak rules, Hammersley and Monte Carlo sequences.

A notion of discrepancy is introduced, which represents the integration error on spaces of \(r\)-smooth periodic functions. It generalizes the diaphony and constitutes a periodic counterpart to the classical \(L_2\)-discrepancy as weil as \(r\)-smooth versions of it introduced recently by Paskov [Pas93]. Based on previous work [FH96], we develop an efficient algorithm for computing periodic discrepancies for quadrature formulas possessing certain tensor product structures, in particular, for Smolyak quadrature rules (also called sparse grid methods). Furthermore, fast algorithms of computing periodic discrepancies for lattice rules can easily be derived from well-known properties of lattices. On this basis we carry out numerical comparisons of discrepancies between Smolyak and lattice rules.

Approximation properties of the underlying estimator are used to improve the efficiency of the method of dependent tests. A multilevel approximation procedure is developed such that in each level the number of samples is balanced with the level-dependent variance, resulting in a considerable reduction of the overall computational cost. The new technique is applied to the Monte Carlo estimation of integrals depending on a parameter.

A new variance reduction technique for the Monte Carlo solution of integral
equations is introduced. It is based on separation of the main part. A neighboring equation with exactly known solution is constructed by the help of a deterministic Galerkin scheme. The variance of the method is analyzed, and an application to the radiosity equation of computer graphics, together with numerical test results is given.

We study the global solution of Fredholm integral equations of the second kind by the help of Monte Carlo methods. Global solution means that we seek to approximate the full solution function. This is opposed to the usual applications of Monte Carlo, were one only wants to approximate a functional of the solution. In recent years several researchers developed Monte Carlo methods also for the global problem. In this paper we present a new Monte Carlo algorithm for the global solution of integral equations. We use multiwavelet expansions to approximate the solution. We study the behaviour of variance on increasing levels, and based on this, develop a new variance reduction technique. For classes of smooth kernels and right hand sides we determine the convergence rate of this algorithm and show that it is higher
than those of previously developed algorithms for the global problem. Moreover, an information-based complexity analysis shows that our algorithm is optimal among all stochastic algorithms of the same computational
cost and that no deterministic algorithm of the same cost can reach its convergence rate.

The \(L_2\)-discrepancy is a quantitative measure of precision for multivariate quadrature rules. It can be computed explicitly. Previously known algorithms needed \(O(m^2\)) operations, where \(m\) is the number of nodes. In this paper we present algorithms which require
\(O(m(log m)^d)\) operations.

We study the problem of global solution of Fredholm integral equations. This means that we seek to approximate the full solution function (as opposed to the local problem, where only the value of the solution in a single point or a functional of the solution is sought). We analyze the Monte Carlo complexity, i.e. the complexity of stochastic solution of this problem. The framework for this analysis is provided by information based complexity theory. Our investigations complement previous ones on stochastic complexity of local solution and on deterministic complexity of
both local and global solution. The results show that even in the global case Monte Carlo algorithms can perform better than deterministic ones, although the difference is not as large as in the local case.

The Monte Carlo complexity of computing integrals depending on a parameter is analyzed for smooth integrands. An optimal algorithm is developed on the basis of a multigrid variance reduction technique. The complexity analysis implies that our algorithm attains a higher convergence rate than any deterministic algorithm. Moreover, because of savings due to computation on multiple grids, this rate is also higher than that of previously developed Monte Carlo algorithms for parametric integration.