Numerical integration formulas of degree two

Numerical integration formulas in n-dimensional nonsymmetric Euclidean space of degree two, consisting of n+1 equally weighted points, are discussed, for a class of integrals often encountered in statistics. This is an extension of Stroud's theory [A.H. Stroud, Remarks on the disposition of points in numerical integration formulas, Math. Comput. 11 (60) (1957) 257–261; A.H. Stroud, Numerical integration formulas of degree two, Math. Comput. 14 (69) (1960) 21–26]. Explicit formulas are given for integrals with nonsymmetric weights. These appear to be new results and include the Stroud's degree two formula as a special case.     

Optimal cubature formulas for tensor products of certain classes of functions

We study the problem of constructing an optimal formula of approximate integration along a d-dimensional parallelepiped. Our construction utilizes mean values along intersections of the integration domain with n hyperplanes of dimension (d−1), each of which is perpendicular to some coordinate axis. We find an optimal cubature formula of this type for two classes of functions. The first class controls the moduli of continuity with respect to all variables, whereas the second class is the intersection of certain periodic multivariate Sobolev classes. We prove that all node hyperplanes of the optimal formula in each case are perpendicular to a certain coordinate axis and are equally spaced and the weights are equal. For specific moduli of continuity and for sufficiently large n, the formula remains optimal for the first class among cubature formulas with arbitrary positions of hyperplanes.     

Invariant cubature formulas of degree eleven which contain the Laplace operator

For the integral over the n-dimensional space with a radially symmetric weight function, two cubature formulas of degree eleven which are invariant under the group of hyperoctahedron are constructed. The formulas for the cubature sum contain the value of the Laplacian of the integrand at the point O(0, 0, ..., 0). Examples of approximate values of the parameters in these formulas are given.     

Numerical identification of source terms for a two dimensional heat conduction problem in polar coordinate system

This work investigates the inverse problem of reconstructing a spacewise dependent heat source in a two-dimensional heat conduction equation using a final temperature measurement. Problems of this type have important applications in several fields of applied science. Under certain assumptions, this problem can be transformed into a one-dimensional problem where the heat source only depends on the variable r  . However, being different from other one-dimensional inverse heat source problems, there exists singularity on the coefficient of our model, which may make the analysis more difficult, regardless of theoretical or numerical. The inverse problem is reduced to an operator equation of the first kind and the corresponding adjoint operator is deuced. For the two dimensional case, i.e., f=f(r,θ)$f=f(r\text{,}\theta )$, theoretical analysis can be done by similar derivation. Based on the landweber regularization framework, an iterative algorithm is proposed to obtain the numerical solution. Some typical numerical examples are presented to show the validity of the inversion method.     

A Unified Constructive Approach to the Topological Degree in Rn

The paper gives an approach to the topological degree in Rⁿ which takes into account numerical requirements and permits derivation of the known degree computation formulas in a simple way. The new approach subsumes several earlier approaches and represents a general principle of construction of degree computation formulas. The basic idea consists of computing the degree of a continuous function relative to a bounded open subset Ω of Rⁿ by means of an auxiliary function which is defined on a polyhedron approximating Ω and maps into a known fixed convex polyhedron containing the origin of Rⁿ. It is further shown that the topological degree of a continuous function relative to an n-dimensional polyhedron P can be computed alone by means of a subset of the boundary of P .     

Fast orthogonalization to the kernel of the discrete gradient operator with application to Stokes problem

We obtain a simple tensor representation of the kernel of the discrete d-dimensional gradient operator defined on tensor semi-staggered grids. We show that the dimension of the nullspace grows as O(n^d-2), where d is the dimension of the problem, and n is one-dimensional grid size. The tensor structure allows fast orthogonalization to the kernel. The usefulness of such procedure is demonstrated on three-dimensional Stokes problem, discretized by finite differences on semi-staggered grids, and it is shown by numerical experiments that the new method outperforms usually used stabilization approach.     

Density condensation of Boolean formulas

The following problem is considered: given a Boolean formula f, generate another formula g such that: (i) If f is unsatisfiable then g is also unsatisfiable. (ii) If f is satisfiable then g is also satisfiable and furthermore g is “easier” than f. For the measure of this easiness, we use the density of a formula f which is defined as (the number of satisfying assignments)/2ⁿ, where n is the number of Boolean variables of f. In this paper, we mainly consider the case that the input formula f is given as a 3-CNF formula and the output formula g may be any formula using Boolean AND, OR and negation. Two different approaches to this problem are presented: one is to obtain g by reducing the number of variables and the other by increasing the number of variables, both of which are based on existing SAT algorithms. Our performance evaluation shows that, a little surprisingly, better SAT algorithms do not always give us better density-condensation algorithms.     

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.     

A generator of high-order embedded P-stable methods for the numerical solution of the Schrödinger equation

A generator of new embedded P-stable methods of order 2n+2, where n is the number of layers used by the embedded methods, for the approximate numerical integration of the one-dimensional Schrödinger equation is developed in this paper. These new methods are called embedded methods because of a simple natural error control mechanism. Numerical results obtained for one-dimensional differential equations of the Schrödinger type show the validity of the developed theory.     

Numerical integration using sparse grids

We present new and review existing algorithms for the numerical integration of multivariate functions defined over d-dimensional cubes using several variants of the sparse grid method first introduced by Smolyak [49]. In this approach, multivariate quadrature formulas are constructed using combinations of tensor products of suitable one-dimensional formulas. The computing cost is almost independent of the dimension of the problem if the function under consideration has bounded mixed derivatives. We suggest the usage of extended Gauss (Patterson) quadrature formulas as the one‐dimensional basis of the construction and show their superiority in comparison to previously used sparse grid approaches based on the trapezoidal, Clenshaw–Curtis and Gauss rules in several numerical experiments and applications. For the computation of path integrals further improvements can be obtained by combining generalized Smolyak quadrature with the Brownian bridge construction. This revised version was published online in August 2006 with corrections to the Cover Date.     

Cubature formulas for function spaces with moderate smoothness

We construct simple algorithms for high-dimensional numerical integration of function classes with moderate smoothness. These classes consist of square-integrable functions over the d-dimensional unit cube whose coefficients with respect to certain multiwavelet expansions decay rapidly. Such a class contains discontinuous functions on the one hand and, for the right choice of parameters, the quite natural d-fold tensor product of a Sobolev space H^s[0,1] on the other hand.The algorithms are based on one-dimensional quadrature rules appropriate for the integration of the particular wavelets under consideration and on Smolyak's construction. We provide upper bounds for the worst-case error of our cubature rule in terms of the number of function calls. We additionally prove lower bounds showing that our method is optimal in dimension d=1 and almost optimal (up to logarithmic factors) in higher dimensions. We perform numerical tests which allow the comparison with other cubature methods.     

An analytical formula for pricing m-th to default swaps

The computational effort of pricing an m-th to default swap depends highly on the size n of the underlying basket. Usually, n different default times are modeled, but in fact the valuation only depends on the m-th smallest default time of this tuple. In this paper we attain an analytical formula for the distribution of this m-th default time. With the help of this distribution we simplify the valuation problem from an n-dimensional quadrature to a one-dimensional quadrature and break the curse of dimensionality. Applications of this modification are efficient pricing of m-th to default swaps, estimation of sensitivities and pricing of European max/min options.     

Fourier spectral projection method and nonlinear convergence analysis for Navier-Stokes equations

In this paper, we investigate the convergence rate of the Fourier spectral projection methods for the periodic problem of n-dimensional Navier-Stokes equations. Based on some alternative formulations of the Navier-Stokes equations and the related projection methods, the error estimates are carried out by a global nonlinear error analysis. It simplifies the analysis, relaxes the restriction on the time step size, weakens the regularity requirements on the genuine solution, and leads to some improved convergence results. A new correction technique is proposed for improving the accuracy of the numerical pressure.     

Exact integration formulas for the finite volume element method on simplicial meshes

This article considers the technological aspects of the finite volume element method for the numerical solution of partial differential equations on simplicial grids in two and three dimensions. We derive new classes of integration formulas for the exact integration of generic monomials of barycentric coordinates over different types of fundamental shapes corresponding to a barycentric dual mesh. These integration formulas constitute an essential component for the development of high‐order accurate finite volume element schemes. Numerical examples are presented that illustrate the validity of the technology. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

An analysis of parallel routing algorithm on hypercube network by employing covering problem and assignment problem

The application of Hadamard matrix to the parallel routings on the hypercube network was presented by Rabin. In this matrix, every two rows differ from each other by exactlyn/2 positions. A set ofn disjoint paths onn-dimensional hypercube network was designed using this peculiar property of Hadamard matrix. Then, the data is dispersed into n packets and these n packet are transmitted along thesen disjoint paths. In this paper, Rabin’s routing algorithm is analyzed in terms of covering problem and assignment problem. Finally, we conclude thatn packets dispersed are placed in well-distributed positions during transmission, and the randomly selected paths are almost a set ofn edge-disjoint paths with high probability.     

Recursive approximation of the high dimensional max function

This paper proposes a smoothing method for the general n-dimensional max function, based on a recursive extension of smoothing functions for the two-dimensional max function. A theoretical framework is introduced, and some applications are discussed. Finally, a numerical comparison with a well-known smoothing method is presented.     

A fourth degree integration formula for the n-dimensional simplex

A fourth degree integration formula is given for the n-dimensional simplex for all n2, which is invariant under the group G of all affine transformations of T_n onto itself. The formula contains (n²+5n+6)/2 nodes.     

Method of analytic continuation for the inverse spherical mean transform in constant curvature spaces

The following problem arises in thermoacoustic tomography and has intimate connection with PDEs and integral geometry. Reconstruct a function f supported in an n-dimensional ball B given the spherical means of f over all geodesic spheres centered on the boundary of B. We propose a new approach to this problem, which yields explicit reconstruction formulas in arbitrary constant curvature space, including euclidean space ? ⁿ , the n-dimensional sphere, and hyperbolic space. The main idea is analytic continuation of the corresponding operator families. The results are applied to inverse problems for a large class of Euler-Poisson-Darboux equations in constant curvature spaces of arbitrary dimension.