Dimension–Adaptive Tensor–Product Quadrature

We consider the numerical integration of multivariate functions defined over the unit hypercube. Here, we especially address the high–dimensional case, where in general the curse of dimension is encountered. Due to the concentration of measure phenomenon, such functions can often be well approximated by sums of lower–dimensional terms. The problem, however, is to find a good expansion given little knowledge of the integrand itself. The dimension–adaptive quadrature method which is developed and presented in this paper aims to find such an expansion automatically. It is based on the sparse grid method which has been shown to give good results for low- and moderate–dimensional problems. The dimension–adaptive quadrature method tries to find important dimensions and adaptively refines in this respect guided by suitable error estimators. This leads to an approach which is based on generalized sparse grid index sets. We propose efficient data structures for the storage and traversal of the index sets and discuss an efficient implementation of the algorithm. The performance of the method is illustrated by several numerical examples from computational physics and finance where dimension reduction is obtained from the Brownian bridge discretization of the underlying stochastic process.     

An Algebraic Multigrid Method for Higher-order Finite Element Discretizations

In this paper, we will design and analyze a class of new algebraic multigrid methods for algebraic systems arising from the discretization of second order elliptic boundary value problems by high-order finite element methods. For a given sparse stiffness matrix from a quadratic or cubic Lagrangian finite element discretization, an algebraic approach is carefully designed to recover the stiffness matrix associated with the linear finite element disretization on the same underlying (but nevertheless unknown to the user) finite element grid. With any given classical algebraic multigrid solver for linear finite element stiffness matrix, a corresponding algebraic multigrid method can then be designed for the quadratic or higher order finite element stiffness matrix by combining with a standard smoother for the original system. This method is designed under the assumption that the sparse matrix to be solved is associated with a specific higher order, quadratic for example, finite element discretization on a finite element grid but the geometric data for the underlying grid is unknown. The resulting new algebraic multigrid method is shown, by numerical experiments, to be much more efficient than the classical algebraic multigrid method which is directly applied to the high-order finite element matrix. Some theoretical analysis is also provided for the convergence of the new method.     

Sparse Grids, Adaptivity, and Symmetry

Sparse grid methods represent a powerful and efficient technique for the representation and approximation of functions and particularly the solutions of partial differential equations in moderately high space dimensions. To extend the approach to truly high-dimensional problems as they arise in quantum chemistry, an additional property has to be brought into play, the symmetry or antisymmetry of the functions sought there. In the present article, an adaptive sparse grid refinement scheme is developed that takes full advantage of such symmetry properties and for which the amount of work and storage remains strictly proportional to the number of degrees of freedom. To overcome the problems with the approximation of the inherently complex antisymmetric functions, augmented sparse grid spaces are proposed.     

Computation of Singular Integral Operators in Wavelet Coordinates

With respect to a wavelet basis, singular integral operators can be well approximated by sparse matrices, and in Found. Comput. Math. 2: 203–245 (2002) and SIAM J. Math. Anal. 35: 1110–1132 (2004), this property was used to prove certain optimal complexity results in the context of adaptive wavelet methods. These results, however, were based upon the assumption that, on average, each entry of the approximating sparse matrices can be computed at unit cost. In this paper, we confirm this assumption by carefully distributing computational costs over the matrix entries in combination with choosing efficient quadrature schemes.     

Gaussian quadrature formulae-second peano kernels,nodes, weights and Bessel functions

The central results of this paper are bounds for the second Peano kernels of the Gaussian quadrature formulae. Hence, for these quadrature formulae, we derive asymptotically optimal error constants for classes of functions with a bounded second derivative or with a first derivative of bounded variation, or for a class of convex functions. To obtain these bounds, we first prove inequalities related to MacMahon's expansion and some further results on the Bessel functionJ _o , as well as some “trapezoid theorems for the weights of Gaussian formulae” (cf. Davis and Rabinowitz [6]) with explicit bounds for the error term.     

Newton-Cotes Formulae for the Numerical Evaluation of Certain Hypersingular Integrals

The quadrature formulae of Newton-Cotes type for the computation of hypersingular integrals with second order singularity on interval are discussed. We improve the estimates given by Linz [22] such that the Newton-Cotes method is valid with less restriction on the location of the singular point. We also present a new Newton-Cotes formula which is applicable when the singular point coincides with a mesh point, while the classical Newton-Cotes method fails in this case. Error analysis for the new formula is given. Numerical experiments are presented to validate the analysis.     

Differential quadrature element analysis using extended differential quadrature

The extended differential quadrature (EDQ) has been proposed. A certain order derivative or partial derivative of the variable function with respect to the coordinate variables at an arbitrary discrete point is expressed as a weighted linear sum of the values of function and/or its possible derivatives at all grid nodes. The grid pattern can be fixed while the selection of discrete points for defining discrete fundamental relations is flexible. This method can be used to the differential quadrature element and generalized differential quadrature element analyses.     

Computing Interval Enclosures for Definite Integrals by Application of Triple Adaptive Strategies

In addition to the well-known and widely-used adaptive strategies for region subdivision and the choice of local quadrature rules, there still exists a third possibility for doing numerical integration adaptively, when interval computation is considered. Based on the Peano's kernels theorem and interval arithmetic, we are able to estimate the truncation error of a quadrature rule by means of different derivatives of the integrand, where the available orders of the derivatives depend on the degree of smoothness of the integrand and the exactness degree of the underlying quadrature rule. We classify the methods as the adaptive orders strategies, if they make use of the derivatives of different orders to improve each single local error estimation. In this paper, alternatives for adaptive error estimation are discussed. Moreover, a practical way for realization of the optimal error estimation is suggested. Numerical results for integrands of different classes as well as numerical comparisons of different methods are given.     

Adaptive Techniques for Spline Collocation

We integrate optimal quadratic and cubic spline collocation methods for second-order two-point boundary value problems with adaptive grid techniques, and grid size and error estimators. Some adaptive grid techniques are based on the construction of a mapping function that maps uniform to non-uniform points, placed appropriately to minimize a certain norm of the error. One adaptive grid technique for cubic spline collocation is mapping-free and resembles the technique used in COLSYS (COLNEW) [2], [4]. Numerical results on a variety of problems, including problems with boundary or interior layers, and singular perturbation problems indicate that, for most problems, the cubic spline collocation method requires less computational effort for the same error tolerance, and has equally reliable error estimators, when compared to Hermite piecewise cubic collocation. Comparison results with quadratic spline collocation are also presented.     

Convergenza di formule gaussiane per il calcolo delle derivate di integrali A valor principale secondo Cauchy

We consider gaussian quadrature rules for the numerical approximation of the derivatives of Cauchy principal value integrals. Convergence results are given and some estimates of the remainder are established in relation to the regularity of the «density» function.     

On Chebyshev quadrature for ultraspherical weight functions

It is well-known that for the ultraspherical weight function (1-x²)^λ-1/2 there exist no Chebyshev quadrature formulae in the strict sense having n nodes, where n is sufficiently large and λ>0, whereas on the other hand for λ=0 every Gaussian quadrature formulae is a Chebyshev formula in the strict sense. In this paper we study the open question of Chebyshev quadrature for λ <0. It is shown that there exists no Chebyshev quadrature formula in the strict sense having more than two nodes for λ≤λ₀=-.30056... (for definition of λ₀ see (1.8) below). Moreover, results are obtained for Chebyshev-type formulae and Chebyshev formulae of closed type. For the remaining values of λ (λ₀<λ<0) numerical results are given.     

Higher Order Sparse Grid Methods for Elliptic Partial Differential Equations with Variable Coefficients

We present a method for discretizing and solving general elliptic partial differential equations on sparse grids employing higher order finite elements. On the one hand, our approach is charactarized by its simplicity. The calculation of the occurring functionals is composed of basic pointwise or unidirectional algorithms. On the other hand, numerical experiments prove our method to be robust and accurate. Discontinuous coefficients can be treated as well as curvilinearly bounded domains. When applied to adaptively refined sparse grids, our discretization results to be highly efficient, yielding balanced errors on the computational domain.     

Data Mining with Sparse Grids

O (h _n ⁻¹ n ^{d −1}) instead of O(h _n ^−d ) grid points and unknowns are involved. Here d denotes the dimension of the feature space and h _n = 2 ⁻ⁿ gives the mesh size. To be precise, we suggest to use the sparse grid combination technique [42] where the classification problem is discretized and solved on a certain sequence of conventional grids with uniform mesh sizes in each coordinate direction. The sparse grid solution is then obtained from the solutions on these different grids by linear combination. In contrast to other sparse grid techniques, the combination method is simpler to use and can be parallelized in a natural and straightforward way. We describe the sparse grid combination technique for the classification problem in terms of the regularization network approach. We then give implementational details and discuss the complexity of the algorithm. It turns out that the method scales only linearly with the number of instances, i.e. the amount of data to be classified. Finally we report on the quality of the classifier built by our new method. Here we consider standard test problems from the UCI repository and problems with huge synthetical data sets in up to 9 dimensions. It turns out that our new method achieves correctness rates which are competitive to that of the best existing methods. Received April 25, 2001     

A Matrix-free Two-grid Preconditioner for Solving Boundary Integral Equations in Electromagnetism

In this paper, we describe a matrix-free iterative algorithm based on the GMRES method for solving electromagnetic scattering problems expressed in an integral formulation. Integral methods are an interesting alternative to differential equation solvers for this problem class since they do not require absorbing boundary conditions and they mesh only the surface of the radiating object giving rise to dense and smaller linear systems of equations. However, in realistic applications the discretized systems can be very large and for some integral formulations, like the popular Electric Field Integral Equation, they become ill-conditioned when the frequency increases. This means that iterative Krylov solvers have to be combined with fast methods for the matrix-vector products and robust preconditioning to be affordable in terms of CPU time. In this work we describe a matrix-free two-grid preconditioner for the GMRES solver combined with the Fast Multipole Method. The preconditioner is an algebraic two-grid cycle built on top of a sparse approximate inverse that is used as smoother, while the grid transfer operators are defined using spectral information of the preconditioned matrix. Experiments on a set of linear systems arising from real radar cross section calculation in industry illustrate the potential of the proposed approach for solving large-scale problems in electromagnetism.     

Application of an Adaptive Sparse-Grid Technique to a Model Singular Perturbation Problem

In this paper we show how, under minimal conditions, a combination extrapolation can be introduced for an adaptive sparse grid. We apply this technique for the solution of a two-dimensional model singular perturbation problem, defined on the domain exterior of a circle. Received October 18, 1999     

Algorithm of Gaussian Sum Filter Based on SGQF for Nonlinear Non-Gaussian Models

To improve the filtering effect of the sparse grid quadrature filter (SGQF) under non-Gaussian conditions, the Gaussian sum technique is introduced, and the Gaussian sum sparse grid quadrature filter (GSSGQF) is developed. We present a systematic formulation of the SGQF and extend it to the discrete-time nonlinear system with the non-Gaussian noise. The proposed algorithm approximates the non-Gaussian probability densities by a finite number of weighted sums of Gaussian densities, and takes the SGQF as the Gaussian sub-filter to conduct the time and measurement update for each Gaussian component. An application in the discrete-time nonlinear system with the non-Gaussian noise has been shown to demonstrate the accuracy of the GSSGQF. It outperforms the unscented Kalman filter (UKF), the cubature Kalman filter (CKF) and the SGQF. Theoretical analysis and simulation results prove that the GSSGQF provides significant performance improvement in the calculation accuracy for nonlinear non-Gaussian filtering problems.

     

Boundary Element Tearing and Interconnecting Methods

In this paper we introduce the Boundary Element Tearing and Interconnecting (BETI) methods as boundary element counterparts of the well-established Finite Element Tearing and Interconnecting (FETI) methods. In some practical important applications such as far field computations, handling of singularities and moving parts etc., BETI methods have certainly some advantages over their finite element counterparts. This claim is especially true for the sparse versions of the BETI preconditioners resp. methods. Moreover, there is an unified framework for coupling, handling, and analyzing both methods. In particular, the FETI methods can benefit from preconditioning components constructed by boundary element techniques. The first numerical results confirm the efficiency and the robustness predicted by our analysis.     

On some new approximate factorization methods for block tridiagonal matrices suitable for vector and parallel processors

In this paper, to obtain an efficient parallel algorithm to solve sparse block-tridiagonal linear systems, stair matrices are used to construct some parallel polynomial approximate inverse preconditioners. These preconditioners are suitable when the desired goal is to maximize parallelism. Moreover, some theoretical results concerning these preconditioners are presented and how to construct preconditioners effectively for any nonsingular block tridiagonal H-matrices is also described. In addition, the validity of these preconditioners is illustrated with some numerical experiments arising from the second order elliptic partial differential equations and oil reservoir simulations.     

Error Analysis of a Derivative-Free Algorithm for Computing Zeros of Holomorphic Functions

We consider the quadrature method developed by Kravanja and Van Barel (Computing 63(1):69–91, 1999) for computing all the zeros of a holomorphic function that lie inside the unit circle. The algorithm uses only the function values and no (first or higher order) derivatives. Information about the location of the zeros is obtained from certain integrals along the unit circle. In numerical computations these are replaced by their trapezoidal rule approximations. We investigate the resulting quadrature error. Our error analysis shows that the zeros located inside the unit circle do not affect the accuracy of the computed approximations whereas the quadrature error related to the zeros located outside the unit circle tends to zero exponentially as the number of quadrature points tends to infinity.     

On computing derivatives forC 1 interpolating schemes: an optimization

The application of Powell-Sabin’s or Clough-Tocher’s schemes to scattered data problems, as known requires the knowledge of the partial derivatives of first order at the vertices of an underlying triangulation. We study alocal method for generating partial derivatives based on the minimization of the energy functional on the star of triangles sharing a node that we called acell. The functional is associated to some piecewise polynomial function interpolating the points. The proposed method combines theglobal Method II by Renka and Cline (cf. [16, pp. 230–231]) with the variational approach suggested by Alfeld (cf. [2]) with care to efficiency in the computations. The locality together with some implementation strategies produces a method well suited for the treatment of a big amount of data. An improvement of the estimates is also proposed.