Hierarchical Quadrature for Singular Integrals

We introduce a method for the computation of singular integrals arising in the discretization of integral equations. The basic method is based on the concept of admissible subdomains, known, e.g., from panel clustering techniques and -matrices: We split the domain of integration into a hierarchy of subdomains and perform standard quadrature on those subdomains that are amenable to it. By using additional properties of the integrand, we can significantly reduce the algorithmic complexity of our approach. The method works also well for hypersingular integrals.     

Symbolic analysis of linear polyhedra

This paper concerns several analytical problems related to linear polyhedra in euclidean three-dimensional-space. Symbolic formulas for line, surface, and volume integration are given, and it is shown that domain integrals are computable in polynomial time. In particular, it is shown that mass, first and second moments, and products of inertia are computable inO(E) time, whereE is the number of edges of the boundary. Simple symbolic expressions for the normal derivatives of domain integrals are also derived. In particular, it is shown that they are closely linked to the topology of the integration domain, as well as that they are expressible as combinations of domain integrals over lower-order domains (faces, edges, and vertices). The symbolic results presented in this paper may lead to an easy incorporation of integral constraints, for example, concerning mass and inertia, in the engineering designing process of solid objects.     

Numerical evaluation of singular and finite-part integrals on curved surfaces using symbolic manipulation

The numerical integration of all singular surface integrals arising in 3-d boundary element methods is analyzed theoretically and computationally. For all weakly singular integrals arising in BEM, Duffy's triangular or local polar coordinates in conjunction with tensor product Gaussian quadrature are efficient and reliable for bothh-andp-boundary elements. Cauchy- and hypersingular surface integrals are reduced to weakly singular ones by analytic regularization which is done automatically by symbolic manipulation.     

Indexing very high-dimensional sparse and quasi-sparse vectors for similarity searches

Similarity queries on complex objects are usually translated into searches among their feature vectors. This paper studies indexing techniques for very high-dimensional (e.g., in hundreds) vectors that are sparse or quasi-sparse, i.e., vectors each having only a small number (e.g., ten) of non-zero or significant values. Based on the R-tree, the paper introduces the xS-tree that uses lossy compression of bounding regions to guarantee a reasonable minimum fan-out within the allocated storage space for each node. In addition, the paper studies the performance and scalability of the xS-tree via experiments. Received: 3 May 1999 / Accepted: 23 October 2000 Published online: 27 April 2001     

Runge Kutta Type Methods for Isodynamical Matrix Flows: Applications to Balanced Realizations

Recently several numerical methods have been proposed for solving isospectral problems which are matrix differential systems whose solutions preserve the spectrum during the evolution. In this paper we consider matrix differential systems called isodynamical flows in which only a component of the matrix solution preserves the eigenvalues during the evolution and we propose procedures for their numerical solution. Applications of such numerical procedures may be found in systems theory, in particular in balancing realization problems. Several numerical tests will be reported. Received April 27, 2001; revised October 25, 2001 Published online February 18, 2002     

A natural stress boundary integral equation for calculating the near boundary stress field

The stress computational accuracy of internal points by conventional boundary element method becomes more and more deteriorate as the points approach to the boundary due to the nearly singular integrals including nearly strong singularity and hyper-singularity. For calculating the boundary stress, a natural boundary integral equation in which the boundary variables are the displacements, tractions and natural boundary variables was established in the authors’ previous work. Herein, a natural stress boundary integral equation (NSBIE) is further proposed by introducing the natural variables to analyze the stress field of interior points. There are only nearly strong singular integrals in the NSBIE, i.e., the singularity is reduced by one order. The regularization algorithm proposed by the authors is taken over to deal with these singular integrals. Consequently, the NSBIE can analyze the stress field closer to the boundary. Numerical examples demonstrated that two orders of magnitude improvement in reducing the approaching degree can be achieved by NSBIE compared to the conventional one when the near boundary stress field is evaluated. Furthermore, this new way is extended to the multi-domain elasticity problem to calculate the stress field near the boundary and interface.     

Smolyak's Construction of Cubature Formulas of Arbitrary Trigonometric Degree

We study cubature formulas for d-dimensional integrals with a high trigonometric degree. To obtain a trigonometric degree in dimension d, we need about function values if d is large. Only a small number of arithmetical operations is needed to construct the cubature formulas using Smolyak's technique. We also compare different methods to obtain formulas with high trigonometric degree. Received: April 8, 1998     

The Fourier-Nitsche-mortaring for elliptic problems with reentrant edges

The Fourier method is combined with the Nitsche-finite-element method (as a mortar method) and applied to the Dirichlet problem of the Poisson equation in three-dimensional axisymmetric domains with reentrant edges generating singularities. The approximating Fourier method yields a splitting of the 3D problem into a set of 2D problems on the meridian plane of the given domain. For solving the 2D problems bearing corner singularities, the Nitsche-finite-element method with non-matching meshes and mesh grading near reentrant corners is applied. Using the explicit representation of some singularity function of non-tensor product type, the rate of convergence of the Fourier-Nitsche-mortaring is estimated in some H ¹-like norm as well as in the L ₂-norm for weak regularity of the solution. Finally, some numerical results are presented.      

Integration of polynomials over n-dimensional linear polyhedra

This paper is concerned with explicit integration formulae for computing integrals of n-variate polynomials over linear polyhedra in n-dimensional space ⁿ. Two different approaches are discussed; the first set of formulae is obtained by mapping the polyhedron in n-dimensional space ⁿ into a standard n-simplex in ⁿ, while the second set of formulae is obtained by reducing the n-dimensional integral to a sum of n − 1 dimensional integrals which are n + 1 in number. These formulae are followed by an application example for which we have explained the detailed computational scheme. The symbolic integration formulae presented in this paper may lead to an easy and systematic incorporation of global properties of solid objects, such as, for example, volume, centre of mass, moments of inertia etc., required in engineering design problems.     

Computing complete answers to queries in the presence of limited access patterns

In data applications such as information integration, there can be limited access patterns to relations, i.e., binding patterns require values to be specified for certain attributes in order to retrieve data from a relation. As a consequence, we cannot retrieve all tuples from these relations. In this article we study the problem of computing the complete answer to a query, i.e., the answer that could be computed if all the tuples could be retrieved. A query is stable if for any instance of the relations in the query, its complete answer can be computed using the access patterns permitted by the relations. We study the problem of testing stability of various classes of queries, including conjunctive queries, unions of conjunctive queries, and conjunctive queries with arithmetic comparisons. We give algorithms and complexity results for these classes of queries. We show that stability of datalog programs is undecidable, and give a sufficient condition for stability of datalog queries. Finally, we study data-dependent computability of the complete answer to a nonstable query, and propose a decision tree for guiding the process to compute the complete answer.Received: 6 December 2001, Accepted: 25 November 2002, Published online: 3 April 2003Chen Li: This article combines and integrates some content in the technical report at Stanford University [25] and the paper presented in the 8th International Conference on Database Theory (ICDT), London, UK, January, 2001 [28]. In addition to the prior materials, this article contains more results and complete proofs that were not included in the original reports.     

The computation of fourth virial coefficients for pairwise-additive spherically symmetric interaction potentials

A method is given for computing the fourth virial coefficient D(T) for a pairwise additive spherically symmetric interaction potential. Taking one of the four interacting particles as origin and using the appropriate co-ordinate transformations in the usual way the ninefold integrals defining D(T) are reduced to sixfold integrals which are then formally reduced to triple integrals by expanding out those Ursell-Mayer functions in the integrals not involving the origin particle as infinite series in Legendre polynomials P_S(cos?), where ? is the angle between the radius vectors of the interacting particles. The coefficients in these expansions are integrals of highly oscillatory functions, especially for large s, and are evaluated using the Chebyshev polynomial expansion for the Ursell-Mayer functions, thus making explicit use of the oscillatory behaviour of P_S(cos?). The triple integrals are evaluated using a nonproduct integration formula of the seventh degree employed earlier in the computation of the thirdh virial coefficient. The values of D(T) computed by the present method have the same qualitative behaviour as the literature values but appear to be more accurate, particularly at lower temperatures.     

Numerical integration using Wang-Landau sampling

We report a new application of Wang-Landau sampling to numerical integration that is straightforward to implement. It is applicable to a wide variety of integrals without restrictions and is readily generalized to higher-dimensional problems. The feasibility of the method results from a reinterpretation of the density of states in statistical physics to an appropriate measure for numerical integration. The properties of this algorithm as a new kind of Monte Carlo integration scheme are investigated with some simple integrals, and a potential application of the method is illustrated by the evaluation of integrals arising in perturbation theory of quantum many-body systems.     

Numerical solution of the two-dimensional Helmholtz equation with variable coefficients by the radial integration boundary integral and integro-differential equation methods

This paper presents new formulations of the boundary–domain integral equation (BDIE) and the boundary–domain integro-differential equation (BDIDE) methods for the numerical solution of the two-dimensional Helmholtz equation with variable coefficients. When the material parameters are variable (with constant or variable wave number), a parametrix is adopted to reduce the Helmholtz equation to a BDIE or BDIDE. However, when material parameters are constant (with variable wave number), the standard fundamental solution for the Laplace equation is used in the formulation. The radial integration method is then employed to convert the domain integrals arising in both BDIE and BDIDE methods into equivalent boundary integrals. The resulting formulations lead to pure boundary integral and integro-differential equations with no domain integrals. Numerical examples are presented for several simple problems, for which exact solutions are available, to demonstrate the efficiency of the proposed methods.     

Some preconditioners for elliptic PDE-constrained optimization problems

For the structured systems of linear equations arising from the Galerkin finite element discretizations of elliptic PDE-constrained optimization problems, some preconditioners are proposed to accelerate the convergence rate of Krylov subspace methods such as GMRES for both cases of the Tikhonov parameter $\beta$ not very small (equal or greater than 1e?6) and sufficiently small (less than 1e?6), respectively. We derive the explicit expressions for the eigenvalues and eigenvectors of the corresponding preconditioned matrices. Numerical results show that the corresponding preconditioned GMRES methods perform and match well with the theoretical results.     

Numerical study of dynamic processes in a continuous medium with a crack initiated by a near-surface disturbance by means of the grid-characteristic method

The purpose of this work is to study the problem of the near-surface disturbance propagation in a massive rock containing various heterogeneities, i.e., empty or filled cracks. Numerical solutions have been obtained for problems of wave propagation in such highly heterogeneous media, including those taking into account the plastic properties of the rock that can be manifested in the vicinity of a seismic gap or a well bore. All kinds of elastic and elastoplastic waves are analyzed resulting from the propagation of the initial disturbance and the waves arising from the reflection from the cracks and from the boundaries of the integration domain. An investigation was carried out of wave identification by means of seismograms obtained at the receiver located near the ground surface. In this study, the grid-characteristic method is employed using computational grids with triangular meshes and boundary conditions formulated at the interface between the rock and the crack, and on free surfaces in an explicit form. The proposed numerical method is extremely general and is suitable for investigations of the processes of seismic waves’ interaction with heterogeneous inclusions because it ensures the construction of the most correct computational algorithms at the boundaries of the integration domain and at the medium’s interface.     

Image Restoration in Optical-Acoustic Tomography

We consider the optical-acoustic tomography problem. In the general case, the problem is to reconstruct a real-valued function with a compact support in the n-dimensional Euclidean space via its spherical integrals, i.e., integrals over all (n – 1)-dimensional spheres centered at points on some (n – 1)-dimensional hypersurface. We deal with the cases n = 2 and n = 3, which are of the most practical interest from the standpoint of possible medical applications. We suggest a new effective method of reconstruction, develop restoration algorithms, and investigate the quality of the algorithms for these cases. The main result of the paper is construction of explicit approximate reconstruction formulas; from the mathematical standpoint, these formulas give the parametrix for the optical-acoustic tomography problem. The formulas constructed is a background for the restoration algorithms. We performed mathematical experiments to investigate the quality of the restoration algorithms using the generally accepted tomography quality criteria. The results obtain lead to the general conclusion: the quality of the restoration algorithms developed for optical-acoustic tomography is only slightly lower then the quality of the convolution and back projection algorithm used in Radon tomography, which is a standard de facto.     

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.     

hp-adaptive Two-Level Methods for Boundary Integral Equations on Curves

p - and hp-versions of the Galerkin boundary element method for hypersingular and weakly singular integral equations of the first kind on curves. We derive a-posteriori error estimates that are based on stable two-level decompositions of enriched ansatz spaces. The Galerkin errors are estimated by inverting local projection operators that are defined on small subspaces of the second level. A p-adaptive and two hp-adaptive algorithms are defined and numerical experiments confirm their efficiency. Received August 30, 2000; revised April 3, 2001     

Partiality and Nondeterminacy in Program Proofs

Specifications and programs make much use of nondeterministic and/or partial expressions, i.e. expressions which may yield several or no outcomes for some values of their free variables. Traditional 2-valued logics do not comfortably accommodate reasoning about undefined expressions, and do not cater at all for nondeterministic expressions. We seek to rectify this with a 4-valued typed logic E4 which classifies formulae as either “true”, “false”, “neither true nor false”, or “possibly true, possibly false”. The logic is derived in part from the 2-valued logic E and the 3-valued LPF, and preserves most of the theorems of E. Indeed, the main result is that nondeterminacy can be added to a logic covering partiality at little cost. Received July 1996 / Accepted in revised form April 1998     

On numerical cubatures of nearly singular surface integrals arising in BEM collocation

In this paper we present efficient methods to approximate nearly singular surface integrals arising massively when discretizing boundary integral equations via the collocation method. The idea is to introduce local polar coordinates centred at a corner of the triangle. Thus it is possible to perform the inner integration analytically, where either the corresponding formulae can be evaluated numerically stable or can be replaced by simple (rational) approximation quite efficiently. We show that the outer integration can be performed by simple Gauß-Legendre quadrature and how to adapt the order of the Gauß formulae to a required order of consistency. Numerical tests will emphasize the efficiency of our method.