Multidimensional ARKN methods for general oscillatory second-order initial value problems

Based on B-series theory, the order conditions of the multidimensional ARKN methods are presented for the general multi-frequency and multidimensional oscillatory second-order initial value problems by Wu et al. (2009). These multidimensional ARKN methods exactly integrate the multi-frequency and multidimensional unperturbed oscillators. In this paper, we pay attention to the analysis of the concrete multidimensional ARKN methods for the general multi-frequency oscillatory second-order initial value problems whose right-hand side functions depend on both  y$y$and  y^′$y^{\prime }$ (the class of physical problems which fall within its scope is broader). Numerical experiments are carried out to show that the new multidimensional ARKN methods are more efficient compared with some well-known methods for dealing with the oscillatory problems in the scientific literature.     

Order conditions for ARKN methods solving oscillatory systems

For the perturbed oscillators in one-dimensional case, J.M. Franco designed the so-called Adapted Runge-Kutta-Nyström (ARKN) methods and derived the sufficient order conditions as well as the necessary and sufficient order conditions for ARKN methods based on the B-series theory [J.M. Franco, Runge-Kutta-Nyström methods adapted to the numerical integration of perturbed oscillators, Comput. Phys. Comm. 147 (2002) 770-787]. These methods integrate exactly the unperturbed oscillators and are highly efficient when the perturbing function is small. Unfortunately, some critical mistakes have been made in the derivation of order conditions in that paper. On the basis of the results from that paper, Franco extended directly the ARKN methods and the corresponding order conditions to multidimensional case where the perturbed function f does not depend on the first derivative y^′ [J.M. Franco, New methods for oscillatory systems based on ARKN methods, Appl. Numer. Math. 56 (2006) 1040-1053]. In this paper, we present the order conditions for the ARKN methods for the general multidimensional perturbed oscillators where the perturbed function f may depend on only y or on both y and y^′.     

ERKN integrators for systems of oscillatory second-order differential equations

For systems of oscillatory second-order differential equations y^″+My=f with M∈Rm×m, a symmetric positive semi-definite matrix, X. Wu et al. have proposed the multidimensional ARKN methods [X. Wu, X. You, J. Xia, Order conditions for ARKN methods solving oscillatory systems, Comput. Phys. Comm. 180 (2009) 2250-2257], which are an essential generalization of J.M. Franco's ARKN methods for one-dimensional problems or for systems with a diagonal matrix M=w²I [J.M. Franco, Runge-Kutta-Nyström methods adapted to the numerical integration of perturbed oscillators, Comput. Phys. Comm. 147 (2002) 770-787]. One of the merits of these methods is that they integrate exactly the unperturbed oscillators y^″+My=0. Regretfully, even for the unperturbed oscillators the internal stages Yi of an ARKN method fail to equal the values of the exact solution y(t) at tn+cih, respectively. Recently H. Yang et al. proposed the ERKN methods to overcome this drawback [H.L. Yang, X.Y. Wu, Xiong You, Yonglei Fang, Extended RKN-type methods for numerical integration of perturbed oscillators, Comput. Phys. Comm. 180 (2009) 1777-1794]. However, the ERKN methods in that paper are only considered for the special case where M is a diagonal matrix with nonnegative entries. The purpose of this paper is to extend the ERKN methods to the general case with M∈Rm×m, and the perturbing function f depends only on y. Numerical experiments accompanied demonstrates that the ERKN methods are more efficient than the existing methods for the computation of oscillatory systems. In particular, if M∈Rm×m is a symmetric positive semi-definite matrix, it is highly important for the new ERKN integrators to show the energy conservation in the numerical experiments for problems with Hamiltonian in comparison with the well-known methods in the scientific literature. Those so called separable Hamiltonians arise in many areas of physical sciences, e.g., macromolecular dynamics, astronomy, and classical mechanics.     

Trigonometrically-fitted Scheifele two-step methods for perturbed oscillators

In this paper, a new family of trigonometrically-fitted Scheifele two-step (TFSTS) methods for the numerical integration of perturbed oscillators is proposed and investigated. An essential feature of TFSTS methods is that they are exact in both the internal stages and the updates when solving the unperturbed harmonic oscillator y^″=−ω²y for known frequency ω. Based on the linear operator theory, the necessary and sufficient conditions for TFSTS methods of up to order five are derived. Two specific TFSTS methods of orders four and five respectively are constructed and their stability and phase properties are examined. In the five numerical experiments carried out the new integrators are shown to be more efficient and competent than some well-known methods in the literature.     

Note on derivation of order conditions for ARKN methods for perturbed oscillators

J.M. Franco derived the sufficient order conditions as well as the necessary and sufficient order conditions for his Adapted Runge-Kutta-Nyström methods (in short notation ARKN methods) based on the B-series theory [J.M. Franco, Runge-Kutta-Nyström methods adapted to the numerical integration of perturbed oscillators, Comput. Phys. Comm. 147 (2002) 770-787]. Unfortunately, some fundamental mistakes have been made in the derivation of order conditions in that paper. In view of importance of the algebraic order theory for ARKN methods, a new and correct derivation of the order conditions for the ARKN methods is presented in this short note.     

One step integration methods of third-fourth order accuracy with large hyperbolic stability limits

One step integration methods of third and fourth order accuracy that use K function evaluations to solve the system of differential equations $\text{d}\text{y}\text{d}\text{t}\text{= A · y}$ are proposed. These methods are shown to have a hyperbolic stability limit of y (K ? 1)² ? 1 which approaches the theoretical maximum limit of K ? 1 at large K obtained for methods of lower order accuracy.     

A General Deterministic Sequence for Sampling <Emphasis Type="Italic">d</Emphasis>-Dimensional Configuration Spaces

Previous works have already demonstrated that deterministic sampling can be competitive with respect to probabilistic sampling in sampling-based path planners. Nevertheless, the definition of a general sampling sequence for any d-dimensional configuration space satisfying the requirements needed for path planning is not a trivial issue. This paper makes a proposal of a simple and yet efficient deterministic sampling sequence based on the recursive use, over a multi-grid cell decomposition, of the ordering of the 2 ^d descendant cells of any parent cell. This ordering is generated by the digital construction method using a d×d matrix T _d . A general expression of this matrix (i.e. for any d) is introduced and its performance analyzed in terms of the mutual distance. The paper ends with a performance evaluation of the use of the proposed deterministic sampling sequence in different well known path planners. This work was partially supported by the CICYT projects DPI2004-03104 and DPI2005-00112. M. Roa is supported by Alβan (European Union Programme of High Level Scholarships for Latin America) under Scholarship No. E04D039103CO.     

The iterated defect correction methods for singular two-point boundary value problems

In this paper, the iterated defect correction (IDeC) techniques based on the centered Euler method for the equivalent first order system of the singular two-point boundary value problem in linear case (x ^α y′(x))′ = f(x), y(0) = a,y(1) = b, where 0 < α < 1 are considered. By using the asymptotic expansion of the global error, it is analyzed that the IDeC methods improved the approximate results by means of IDeC steps and the degree of the interpolating polynomials used. Some numerical examples from the literature are given in illustration of this theory.     

New explicit filters and smoothers for diffusions with nonlinear drift and measurements

The optimal least-squares filtering of a diffusion x(t) from its noisy measurements {y(τ); 0 τ t} is given by the conditional mean E[x(t)|y(τ); 0 τ t]. When x(t) satisfies the stochastic diffusion equation dx(t) = f(x(t)) dt + dw(t) and y(t) = ∫₀^tx(s) ds + b(t), where f(·) is a global solution of the Riccati equation /xf(x) + f(x)² = f(x)² = αx² + βx + γ, for some , and w(·), b(·) are independent Brownian motions, Benes gave an explicit formula for computing the conditional mean. This paper extends Benes results to measurements y(t) = ∫₀^tx(s) ds + ∫₀^t dx(s) + b(t) (and its multidimensional version) without imposing additional conditions on f(·). Analogous results are also derived for the optimal least-squares smoothed estimate E[x(s)|y(τ); 0 τ t], s < t. The methodology relies on Girsanov's measure transformations, gauge transformations, function space integrations, Lie algebras, and the Duncan-Mortensen-Zakai equation.     

On closed-form approximations for the free energy ofd-dimensional Ising model,II

It has been shown that it is possible to construct families of closed-form approximations lnZ* _d to lnZ _d for the anisotropic Ising model on ad-dimensional hypercubical lattice whose high- and low-temperature series expansions coincide with the corresponding exact expansions up to some order. For the isotropic case the density of zeros ofZ* _d near the critical pointK _c is found under the assumption that they behave like sinh2K=±(sinh2K _c +y±iy). It is shown that there exists a family of closed-form approximations such that ford3 the only possible densities of zeros arem(y)=|y|³ for=0 andm(y)=|y| for 0<||1, i.e., it contains the exact case ford5 corresponding to ||=1.     

Preconditioning the Matrix Exponential Operator with Applications

The idea of preconditioning is usually associated with solution techniques for solving linear systems or eigenvalue problems. It refers to a general method by which the original system is transformed into one which admits the same solution but which is easier to solve. Following this principle we consider in this paper techniques for preconditioning the matrix exponential operator, e ^A y ₀, using different approximations of the matrix A. These techniques are based on using generalized Runge Kutta type methods. Preconditioners based on the sparsity structure of the matrix, such as diagonal, block diagonal, and least-squares tensor sum approximations are presented. Numerical experiments are reported to compare the quality of the schemes introduced.     

Two-step extended RKN methods for oscillatory systems

In this paper, two-step extended Runge–Kutta–Nyström-type methods for the numerical integration of perturbed oscillators are presented and studied. The new methods inherit the framework of two-step hybrid methods and are adapted to the special feature of the true flows in both the internal stages and the updates. Based on the EN-trees theory [H.L. Yang, X.Y. Wu, X. You, Y.L. Fang, Extended RKN-type methods for numerical integration of perturbed oscillators, Comput. Phys. Comm. 180 (2009) 1777–1794], order conditions for the new methods are derived via the BBT-series defined on the set BT of branches and the BBWT-series defined on the subset BWT of BT. The stability and phase properties are analyzed. Numerical experiments show the applicability and efficiency of our new methods in comparison with the well-known high quality methods proposed in the scientific literature.     

A simplified Nyström-tree theory for extended Runge–Kutta–Nyström integrators solving multi-frequency oscillatory systems

In the study of extended Runge–Kutta–Nyström (abbr. ERKN) methods for the integration of multi-frequency oscillatory systems, a quite complicated set of algebraic conditions arises which must be satisfied for a method to achieve some specified order. A theory of tri-colored tree was proposed by Yang et al. (2009), for achieving the order conditions of ERKN methods which are designed specially for multi-frequency and multidimensional perturbed oscillators. The tri-colored tree theory for the order conditions in that paper is useful, but not completely satisfactory due to the existence of redundant trees. In this paper, a simplified tri-colored theory and the order conditions for ERKN integrators are developed by constructing a set of simplified special extended Nyström trees (abbr. SSENT) and defining some real-valued mappings on it. In order to simplify the tri-colored tree theory, two special mappings, the extended elementary differential and the sign mapping for a tree are investigated in detail. This leads to a novel Nyström-tree theory for the order conditions for ERKN methods without any redundant trees, which simplifies the tri-colored theory.     

Sextic C 1-spline collocation methods for solving delay differential equations

In this paper, we propose a global collocation method for the numerical solution of the delay differential equations (DDEs). The method presented is based on sextic C ¹-splines s(x) as an approximation to the exact solution y(x) of the DDEs. Convergence results shows that the error bounds ‖ s ^j ?y ^j ‖=O(h ⁶), j=0, 1, in the uniform norm. Moreover, the stability analysis properties of these methods have been studied. Numerical experiments will also be considered.     

Panconnectivity and edge-pancyclicity of 3-ary <Emphasis Type="Italic">N</Emphasis>-cubes

We study two topological properties of the 3-ary n-cube Q _n ³. Given two arbitrary distinct nodes x and y in Q _n ³, we prove that there exists an x–y path of every length ranging from d(x,y) to 3 ⁿ −1, where d(x,y) is the length of a shortest path between x and y. Based on this result, we prove that Q _n ³ is edge-pancyclic by showing that every edge in Q _n ³ lies on a cycle of every length ranging from 3 to 3 ⁿ .

Order conditions and symmetry for two-step hybrid methods

In this study of two-step hybrid methods for second-order equations of the type y″?=?f(y), we apply P-series [Hairer, E., Lubich, C. and Wanner, G. (2002). Geometric Numerical Integration Structure-Preserving Algorithms for Ordinary Differential Equations. Springer Series in Computational Mathematics.] to formalise the approach of Chan [Chan, R. P. K. (2002). Two-step hybrid methods. Internal Publication.] to the order conditions, and present two characterizations of symmetry. Although order conditions can be obtained through the classical theory for the Nyström methods, it is of interest to derive particular simpler formulas for the class of two-step hybrid methods in order to facilitate the search for high-order methods. Moreover, the approach proves useful in analysing the symmetry of the hybrid methods.     

New strategy to improve estimation of diffuse attenuation coefficient for highly turbid inland waters

The diffuse attenuation coefficient, K_d(λ), is an important water optical property. Detection of K_d(λ) by means of remote sensing can provide significant assistance in understanding water environment conditions and many biogeochemical processes. Even when existing algorithms exhibit good performance in clear open ocean and turbid coastal waters, accurate quantification of highly turbid inland water bodies can still be a challenge due to their bio-optical complexity. In this study, we examined the performance of two typical pre-existing K_d(490) models in inland water bodies from Lake Taihu, Lake Chaohu, and the Three Gorges Reservoir in China. On the basis of water optical classification, new K_d(490) models were developed for these waters by means of the support vector machine approach. The obtained results showed that the two pre-existing K_d(490) models presented relatively large errors by comparison with the new models, with mean absolute percentage error (MAPE) values above ~30%. More importantly, among the new models, type-specific models generally outperformed the aggregated model. For water classified as Type 1 + Type 2, the type-specific model produced validation errors with MAPE = 16.8% and RMSE = 0.98 m^?1. For water classified as Type 3, the MAPE and RMSE of the type-specific model were found to be 18.8% and 1.85 m^?1, respectively. The findings in this study demonstrate that water classification (prior to algorithm development) is needed for the development of excellent K_d(490) retrieval algorithms, and the type-specific models thus developed are an important supplement to existing K_d(490) retrieval models for highly turbid inland waters.     

Adaptive Indexing of Moving Objects with Highly Variable Update Frequencies

In recent years, management of moving objects has emerged as an active topic of spatial access methods. Various data structures （indexes） have been proposed to handle queries of moving points, for example, the well-known B^x-tree uses a novel mapping mechanism to reduce the index update costs. However, almost all the existing indexes for predictive queries are not applicable in certain circumstances when the update frequencies of moving objects become highly variable and when the system needs to balance the performance of updates and queries. In this paper, we introduce two kinds of novel indexes, named B^y-tree and αB^y-tree. By associating a prediction life period with every moving object, the proposed indexes are applicable in the environments with highly variable update frequencies. In addition, the αB^y-tree can balance the performance of updates and queries depending on a balance parameter. Experimental results show that the B^y-tree and αB^y-tree outperform the B^x-tree in various conditions.     

The μ-basis of a planar rational curve—properties and computation

A moving line L(x,y;t)=0 is a family of lines with one parameter t in a plane. A moving line L(x,y;t)=0 is said to follow a rational curve P(t) if the point P(t₀) is on the line L(x,y;t₀)=0 for any parameter value t₀. A μ-basis of a rational curve P(t) is a pair of lowest degree moving lines that constitute a basis of the module formed by all the moving lines following P(t), which is the syzygy module of P(t). The study of moving lines, especially the μ-basis, has recently led to an efficient method, called the moving line method, for computing the implicit equation of a rational curve [3 and 6]. In this paper, we present properties and equivalent definitions of a μ-basis of a planar rational curve. Several of these properties and definitions are new, and they help to clarify an earlier definition of the μ-basis [3]. Furthermore, based on some of these newly established properties, an efficient algorithm is presented to compute a μ-basis of a planar rational curve. This algorithm applies vector elimination to the moving line module of P(t), and has O(n²) time complexity, where n is the degree of P(t). We show that the new algorithm is more efficient than the fastest previous algorithm [7].     

Multidimensional illumination functions for visualization of complex 3D environments

This paper presents a new view-independent, energy equilibrium method for determining the light distributed in a complex 3D environment consisting of surfaces with general reflectance properties. The method does not depend on discretization of directions or discretization of surfaces to differential elements. Hence, it is a significant improvement over the earlier complete view-independent method which is computationally intractable for complex environments or the hybrid methods which include an extended view-dependent ray tracing second pass. The new method is based on an efficient data structure of order O(N²) called the spherical cover. The spherical cover elegantly captures the complex multidimensional directional nature of light distributed over surfaces. Subdivision techniques based on range estimation of various parameters using interval-arithmetic-like methods are next described for efficiently computing the spherical cover for a given 3D environment. Using the spherical cover, light is progressively propagated through the environment until energy equilibrium is reached. Complexity analysis of the propagation step is carried out to show that the method is computationally tractable. The paper also includes a comprehensive review of earlier rendering techniques viewed from the point of view of capturing the multidimensional nature of light distribution over surfaces.