Computing Discrepancies of Smolyak Quadrature Rules

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

Computation of the Riesz-Herglotz transform and its application to quadrature formulas over the unit circle

Summary A method is proposed for the computation of the Riesz-Herglotz transform. Numerical experiments show the effectiveness of this method. We study its application to the computation of integrals over the unit circle in the complex plane of analytic functions. This approach leads us to the integration by Taylor polynomials. On the other hand, with the goal of minimizing the quadrature error bound for analytic functions, in the set of quadrature formulas of Hermite interpolatory type, we found that this minimum is attained by the quadrature formula based on the integration of the Taylor polynomial. These two different approaches suggest the effectiveness of this formula. Numerical experiments comparing with other quadrature methods with the same domain of validity, or even greater such as Szeg? formulas, (traditionally considered as the counterpart of the Gauss formulas for integrals on the unit circle) confirm the superiority of the numerical estimations. This work was supported by the ministry of education and culture of Spain under contract PB96-1029.     

Convergence and computation of simultaneous rational quadrature formulas

We discuss the convergence and numerical evaluation of simultaneous quadrature formulas which are exact for rational functions. The problem consists in integrating a single function with respect to different measures using a common set of quadrature nodes. Given a multi-index n, the nodes of the integration rule are the zeros of the multi-orthogonal Hermite–Padé polynomial with respect to (S, α, n), where S is a collection of measures, and α is a polynomial which modifies the measures in S. The theory is based on the connection between Gauss-type simultaneous quadrature formulas of rational type and multipoint Hermite–Padé approximation. The numerical treatment relies on the technique of modifying the integrand by means of a change of variable when it has real poles close to the integration interval. The output of some tests show the power of this approach in comparison with other ones in use.     

Smolyak cubature of given polynomial degree with few nodes for increasing dimension

Summary. Some recent investigations (see e.g., Gerstner and Griebel [5], Novak and Ritter [9] and [10], Novak, Ritter and Steinbauer [11], Wasilkowski and Woźniakowski [18] or Petras [13]) show that the so-called Smolyak algorithm applied to a cubature problem on the d-dimensional cube seems to be particularly useful for smooth integrands. The problem is still that the numbers of nodes grow (polynomially but) fast for increasing dimensions. We therefore investigate how to obtain Smolyak cubature formulae with a given degree of polynomial exactness and the asymptotically minimal number of nodes for increasing dimension d and obtain their characterization for a subset of Smolyak formulae. Error bounds and numerical examples show their good behaviour for smooth integrands. A modification can be applied successfully to problems of mathematical finance as indicated by a further numerical example. Received September 24, 2001 / Revised version received January 24, 2002 / Published online April 17, 2002 RID="*" ID="*" The author is supported by a Heisenberg scholarship of the Deutsche Forschungsgemeinschaft     

Weighted quadrature rules for finite element methods

We discuss the numerical integration of polynomials times non-polynomial weighting functions in two dimensions arising from multiscale finite element computations. The proposed quadrature rules are significantly more accurate than standard quadratures and are better suited to existing finite element codes than formulas computed by symbolic integration. We validate this approach by introducing the new quadrature formulas into a multiscale finite element method for the two-dimensional reaction–diffusion equation.     

On Some Special Effects in Theory on Numerical Integration and Functions Recovery

We discuss two questions. First, we consider the existence of close to optimal quadrature formulas with a “bad” L²-discrepancy of their grids, and the second is the question of how much explicit quadrature formulas are preferable to sorting algorithms. Also, in the model case, we obtain the solution to the question of approximative possibilities of Smolyak’s grid in the problems of recovery of functions.     

LANCZOS,GAUSS AND THE PROBLEM OF MOMENTS

Abstract

An algorithm due to Lanczos for solving the problem of weighted moments is discussed including the treatment of double nodes and related to the early work of Gauss on super-interpolatory numerical quadrature.     

Estimating the largest singular values of large sparse matrices via modified moments

We describe a procedure for determining a few of the largest singular values of a large sparse matrix. The method by Golub and Kent which uses the method of modified moments for estimating the eigenvalues of operators used in iterative methods for the solution of linear systems of equations is appropriately modified in order to generate a sequence of bidiagonal matrices whose singular values approximate those of the original sparse matrix. A simple Lanczos recursion is proposed for determining the corresponding left and right singular vectors. The potential asynchronous computation of the bidiagonal matrices using modified moments with the iterations of an adapted Chebyshev semi-iterative (CSI) method is an attractive feature for parallel computers. Comparisons in efficiency and accuracy with an appropriate Lanczos algorithm (with selective re-orthogonalization) are presented on large sparse (rectangular) matrices arising from applications such as information retrieval and seismic reflection tomography. This procedure is essentially motivated by the theory of moments and Gauss quadrature.This author's work was supported by the National Science Foundation under grants NSF CCR-8717492 and CCR-910000N (NCSA), the U.S. Department of Energy under grant DOE DE-FG02-85ER25001, and the Air Force Office of Scientific Research under grant AFOSR-90-0044 while at the University of Illinois at Urbana-Champaign Center for Supercomputing Research and Development.This author's work was supported by the U.S. Army Research Office under grant DAAL03-90-G-0105, and the National Science Foundation under grant NSF DCR-8412314.     

On the Smolyak cubature error for analytic functions

We consider Smolyak's construction for the numerical integration over the d‐dimensional unit cube. The underlying class of integrands is a tensor product space consisting of functions that are analytic in the Cartesian product of ellipses. The Kronrod–Patterson quadrature formulae are proposed as the corresponding basic sequence and this choice is compared with Clenshaw–Curtis quadrature formulae. First, error bounds are derived for the one‐dimensional case, which lead by a recursion formula to error bounds for higher dimensional integration. The applicability of these bounds is shown by examples from frequently used test packages. Finally, numerical experiments are reported. This revised version was published online in June 2006 with corrections to the Cover Date.     

Structured eigenvalue problems for rational gauss quadrature

The connection between Gauss quadrature rules and the algebraic eigenvalue problem for a Jacobi matrix was first exploited in the now classical paper by Golub and Welsch (Math. Comput. 23(106), 221–230, 1969). From then on many computational problems arising in the construction of (polynomial) Gauss quadrature formulas have been reduced to solving direct and inverse eigenvalue problems for symmetric tridiagonals. Over the last few years (rational) generalizations of the classical Gauss quadrature formulas have been studied, i.e., formulas integrating exactly in spaces of rational functions. This paper wants to illustrate that stable and efficient procedures based on structured numerical linear algebra techniques can also be devised for the solution of the eigenvalue problems arising in the field of rational Gauss quadrature.     

Sard-optimal prefilters for the Fast Wavelet Transform

A direct input of function samples into the Fast Wavelet Transform often gives inaccurate results. We use the refinement equation for the construction of prefiltering quadrature formulas which are optimal in Sard's sense, i.e.,in the standard class of functions with ‖ f ^(p)‖₂ < ∞. A detailed analysis of the error and several applications are given. This revised version was published online in August 2006 with corrections to the Cover Date.     

Extended product integration rules

In this paper we introduce a class of extended product quadrature rules to associate with the corresponding standard product rules, and present an algorithm for their construction. A general discussion on the convergence of such formulas is then given. Finally some examples and applications are considered.Work sponsored by the Ministero della Pubblica Istruzione of Italy.     

Suboptimal Kronrod extension formulae for numerical quadrature

Summary We consider cases where the Stieltjes polynomial associated with a Gaussian quadrature formula has complex zeros. In such cases a Kronrod extension of the Gaussian rule does not exist. A method is described for modifying the Stieltjes polynomial so that the resulting polynomial has no complex zeros. The modification is performed in such a way that the Kronrod-type extension rule resulting from the addition of then+1 zeros of the modified Stieltjes polynomial to the original knots of the Gaussian rule has only slightly lower degree of precision than normally achieved when the Kronrod extension rule exists. As examples of the use of the method, we present some new formulae extending the classical Gauss-Hermite quadrature rules. We comment on the limited success of the method in extending Gauss-Laguerre rules and show that several modified extensions of the Gauss Gegenbauer formulae exist in cases where the standard Kronrod extension does not.     

Quadrature formulae with multiple nodes and a maximal trigonometric degree of exactness

In this paper we consider interpolatory quadrature formulae with multiple nodes, which have the maximal trigonometric degree of exactness. Our approach is based on a procedure given by Ghizzeti and Ossicini (Quadrature formulae, Academie-Verlag, Berlin, 1970). We introduce and consider the so-called σ-orthogonal trigonometric polynomials of semi-integer degree and give a numerical method for their construction. Also, some numerical examples are included. The authors were supported in part by the Serbian Ministry of Science and Technological Development (Project: Orthogonal Systems and Applications, grant number #144004) and the Swiss National Science Foundation (SCOPES Joint Research Project No. IB7320-111079 “New Methods for Quadrature”).     

NP-stability of Runge-Kutta methods based on classical quadrature

Recently Bellen, Jackiewicz and Zennaro have studied stability properties of Runge-Kutta (RK) methods for neutral delay differential equations using a scalar test equation. In particular, they have shown that everyA-stable collocation method isNP-stable, i.e., the method has an analogous stability property toA-stability with respect to the test equation. Consequently, the Gauss, Radau IIA and Lobatto IIIA methods areNP-stable. In this paper, we examine the stability of RK methods based on classical quadrature by a slightly different approach from theirs. As a result, we prove that the Radau IA and Lobatto IIIC methods equipped with suitable continuous extensions are alsoNP-stable by virtue of fundamental notions related to those methods such as simplifying conditions, algebraic stability, and theW-transformation.     

Quadrature Formulas for Refinable Functions and Wavelets II: Error Analysis

This paper is concerned with the construction and the analysis of Gauss quadrature formulas for computing integrals of (smooth) functions against refinable functions and wavelets. The main goal of this paper is to develop rigorous error estimates for these formulas. For the univariate setting, we derive asymptotic error bounds for a huge class of weight functions including spline functions. We also discuss multivariate quadrature rules and present error estimates for specific nonseparable refinable functions, i.e., for some special box splines.     

The exponent of discrepancy of sparse grids is at least 2.1933

We study bounds on the exponents of sparse grids for L ₂‐discrepancy and average case d‐dimensional integration with respect to the Wiener sheet measure. Our main result is that the minimal exponent of sparse grids for these problems is bounded from below by 2.1933. This shows that sparse grids provide a rather poor exponent since, due to Wasilkowski and Woźniakowski [16], the minimal exponent of L ₂‐discrepancy of arbitrary point sets is at most 1.4778. The proof of the latter, however, is non‐constructive. The best known constructive upper bound is still obtained by a particular sparse grid and equal to 2.4526.... This revised version was published online in June 2006 with corrections to the Cover Date.     

On the quadrature error in operational quadrature methods for convolutions

Summary We analyze the quadrature error associated with operational quadrature methods for convolution equations. The assumptions are that the convolution kernel is inL ¹ and that its Laplace transform is analytic and bounded in an obtuse sector of the complex plane. Under these circumstances the Laplace transform has a slow variation property which admits a Fourier analysis of the quadrature error. We provide generalL ^p error estimates assuming suitable smoothness conditions on the function under convolution.     

Local error estimates in quadrature

A theoretical error estimate for quadrature formulas, which depends on four approximations of the integral, is derived. We obtain a bound, often sharper than the trivial one, which requires milder conditions to be satisfied than a similar result previously presented by Laurie. A selection of numerical tests with one-dimensional integrals is reported, to show how the error estimate works in practice.     

Applications of Smolyak quadrature formulas to the numerical integration of Fourier coefficients and in function recovery problems

In this paper with the help of Smolyak quadrature formulas we calculate exact orders of errors of the numerical integration of trigonometric Fourier coefficients of functions from generalized classes of Korobov and Sobolev types. We apply the obtained results to the recovery of functions from their values at a finite number of points in terms of the K. Sherniyazov approach.