New embedded explicit pairs of exponentially fitted Runge-Kutta methods

Two new embedded pairs of exponentially fitted explicit Runge-Kutta methods with four and five stages for the numerical integration of initial value problems with oscillatory or periodic solutions are developed. In these methods, for a given fixed ω the coefficients of the formulae of the pair are selected so that they integrate exactly systems with solutions in the linear space generated by {sinh(ωt),cosh(ωt)}, the estimate of the local error behaves as O(h⁴) and the high-order formula has fourth-order accuracy when the stepsize h→0. These new pairs are compared with another one proposed by Franco [J.M. Franco, An embedded pair of exponentially fitted explicit Runge-Kutta methods, J. Comput. Appl. Math. 149 (2002) 407-414] on several problems to test the efficiency of the new methods.     

A simple and space-efficient fragment-chaining algorithm for alignment of DNA and protein sequences

In the segment-based approach to sequence alignment, nucleic acid, and protein sequence alignments are constructed from fragments, i.e., from pairs of ungapped segments of the input sequences. Given a set F of candidate fragments and a weighting function w : F → R⁺₀, the score of an alignment is defined as the sum of weights of the fragments it consists of, and the optimization problem is to find a consistent collection of pairwise disjoint fragments with maximum sum of weights. Herein, a sparse dynamic programming algorithm is described that solves the pairwise segment-alignment problem in O(L + N_max) space where L is the maximum length of the input sequences while N_max ≤ #F holds. With a recently introduced weighting function w, small sets F of candidate fragments are sufficient to obtain alignments of high quality. As a result, the proposed algorithm runs in essentially linear space.     

Design and analysis of predictive sorting algorithms

The focus of this research is the class of sequential algorithms, called predictive sorting algorithms, for sorting a given set ofn elements using pairwise comparisons. The order in which these pairwise comparisons are made is defined by a fixed sequence of all unordered pairs of distinct integers {1, 2, ...,n} called a sort sequence. A predictive sorting algorithm associated with a sort sequence specifies pairwise comparisons of elements in the input set in the order defined by the sort sequence, except that the comparisons whose outcomes can be inferred from the preceding pairs of comparisons are not performed. In this paper predictive sorting algorithms are obtained, based on known sorting algorithms, and are shown to be required on the averageO(n logn) comparisons.     

Stabilization of solutions to Shilov-type parabolic systems with nonnegative genus

We examine some class of Shilov-type parabolic systems with a nonnegative genus and bounded smooth coefficients depending on time and spatial variables and study the behavior of solutions when t tends to infinity. The initial data at t = 0 belong to a wide class of distributions.     

Global optimization algorithm for a generalized linear multiplicative programming

This article present a branch and bound algorithm for globally solving generalized linear multiplicative programming problems with coefficients. The main computation involve solving a sequence of linear relaxation programming problems, and the algorithm economizes the required computations by conducting the branch and bound search in R ^p , rather than in R ⁿ , where p is the number of rank and n is the dimension of decision variables. The proposed algorithm will be convergent to the global optimal solution by means of the subsequent solutions of the series of linear relaxation programming problems. Numerical results are given to show the feasibility and effectiveness of the proposed algorithm.     

Simultaneity and non‐linear variability in financial markets: simulation and forecasting

Non‐linear variability in financial markets can emerge from several mechanisms, including simultaneity and time‐varying coefficients. In simultaneous equation systems, the reduced‐form coefficients that determine the behaviour of jointly dependent variables are products and ratios of the original structural coefficients. If the coefficients are stochastic, the resulting multiplicative interactions will result in high degrees of non‐linearity. Processes generated in this way will scale as fractals: they will exhibit intermittent outliers and scaling symmetries, i.e. proportionality relationships between fluctuations at different separation distances. A model is specified in which both the exchange rate itself and the exchange rate residual exhibit simultaneity. The exchange rate depends on other exchange rates, while the residual depends on the other residuals. The model is then simulated using embedding noise from a t‐distribution. The simulations replicate the observed properties of exchange rates, heavy‐tailed distributions and long memory in the variance. A forecasting algorithm is specified in two stages. The first stage is a model for the actual process. In the second stage the residuals are modelled as a function of the predicted rate of change. The first and second stage models are then combined. This algorithm exploits the scaling symmetry: the residual is proportional to the predicted rate of change at separation distances corresponding to the forecast horizon. The procedure is tested empirically on three exchange rates. At a daily frequency and a 1‐day forecast horizon, two‐stage models reduce the forecast error by one fourth. At a 5‐day horizon, the improvement is 10–15 percent. At a weekly frequency, the improvement at the 1‐week horizon is on the order of 30–40 percent. Copyright © 2006 John Wiley & Sons, Ltd.     

Approximations and Inequalities for Moving Sums

In this article accurate approximations and inequalities are derived for the distribution, expected stopping time and variance of the stopping time associated with moving sums of independent and identically distributed continuous random variables. Numerical results for a scan statistic based on a sequence of moving sums are presented for a normal distribution model, for both known and unknown mean and variance. The new R algorithms for the multivariate normal and t distributions established by Genz et?al. (2010) provide readily available numerical values of the bounds and approximations.     

A numerical method for solving the Dirichlet problem for the wave equation

In this paper we present a numerical method for solving the Dirichlet problem for a two-dimensional wave equation. We analyze the ill-posedness of the problem and construct a regularization algorithm. Using the Fourier series expansion with respect to one variable, we reduce the problem to a sequence of Dirichlet problems for one-dimensional wave equations. The first stage of regularization consists in selecting a finite number of problems from this sequence. Each of the selected Dirichlet problems is formulated as an inverse problem Aq = f with respect to a direct (well-posed) problem. We derive formulas for singular values of the operator A in the case of constant coefficients and analyze their behavior to judge the degree of ill-posedness of the corresponding problem. The problem Aq = f on a uniform grid is reduced to a system of linear algebraic equations A _ll q = F. Using the singular value decomposition, we find singular values of the matrix A _ll and develop a numerical algorithm for constructing the r-solution of the original problem. This algorithm was tested on a discrete problem with relatively small number of grid nodes. To improve the calculated r-solution, we applied optimization but observed no noticeable changes. The results of computational experiments are illustrated.     

t-Pebbling and Extensions

Graph pebbling is the study of moving discrete pebbles from certain initial distributions on the vertices of a graph to various target distributions via pebbling moves. A pebbling move removes two pebbles from a vertex and places one pebble on one of its neighbors (losing the other as a toll). For t ≥ 1 the t-pebbling number of a graph is the minimum number of pebbles necessary so that from any initial distribution of them it is possible to move t pebbles to any vertex. We provide the best possible upper bound on the t-pebbling number of a diameter two graph, proving a conjecture of Curtis et al., in the process. We also give a linear time (in the number of edges) algorithm to t-pebble such graphs, as well as a quartic time (in the number of vertices) algorithm to compute the pebbling number of such graphs, improving the best known result of Bekmetjev and Cusack. Furthermore, we show that, for complete graphs, cycles, trees, and cubes, we can allow the target to be any distribution of t pebbles without increasing the corresponding t-pebbling numbers; we conjecture that this behavior holds for all graphs. Finally, we explore fractional and optimal fractional versions of pebbling, proving the fractional pebbling number conjecture of Hurlbert and using linear optimization to reveal results on the optimal fractional pebbling number of vertex-transitive graphs.     

Tailweight, quantiles and kurtosis: A study of competing distributions

This paper studies analytically and numerically the tail behavior of the symmetric variance-gamma (VG), t, and exponential-power (EP) distributions. Special emphasis is on the VG, which is a direct competitor of the t in the financial context of modeling the distribution of log-price increments.     

Improved Approximation Algorithms for Tree Alignment

Multiple sequence alignment is a task at the heart of much of current computational biology[4]. Several different objective functions have been proposed to formalize the task of multiple sequence alignment, but efficient algorithms are lacking in each case. Thus multiple sequence alignment is one of the most critical, essentially unsolved problems in computational biology. In this paper we consider one of the more compelling objective functions for multiple sequence alignment, formalized as thetree alignment problem. Previously in[13], a ratio-two approximation method was developed for tree alignment, which ran incubictime (as a function of the number of fixed length strings to be aligned), along with a polynomial time approximation scheme (PTAS) for the problem. However, the PTAS in[13]had a running time which made it impractical to reduce the performance ratio much below two for small size biological sequences (100 characters long). In this paper we first develop a ratio-two approximation algorithm which runs inquadratictime, and then use it to develop a PTAS which has a better performance ratio and a vastly improved worst case running time compared to the scheme in[13]for the case where the given tree is a regular deg-ary tree. With the new approximation scheme, it is now practical to guarantee a ratio of 1.583 for strings of lengths 200 characters or less.     

Bootstrapping Autoregressive and Moving Average Parameter Estimates of Infinite Order Vector Autoregressive Processes

We consider anr-dimensional multivariate time series {y_t, tZ} which is generated by an infinite order vector autoregressive process. We show that a bootstrap procedure which works by generating time series replicates via an estimated finitek-order vector autoregressive process (k→∞ at an appropriate rate with the sample size) gives asymptotically valid approximations to the joint distribution of the growing set of estimated autoregressive coefficients and to the corresponding set of estimated moving average coefficients (impuls responses).     

A new method for computing the matrix exponential operation based on vector valued rational approximations

In this paper a new method for computing the action of the matrix exponential on a vector e^Atb, where A is a complex matrix and t is a positive real number, is proposed. Our approach is based on vector valued rational approximation where the approximants are determined by the denominator polynomials whose coefficients are obtained by solving an inexpensive linear least-squares problem. No matrix multiplications or divisions but matrix-vector products are required in the whole process. A technique of scaling and recurrence enables our method to be more effective when the problem is for fixed A,b and many values of t. We also give a backward error analysis in exact arithmetic for the truncation errors to derive our new algorithm. Preliminary numerical results illustrate that the new algorithm performs well.     

Global optimization for first order Markov Random Fields with submodular priors

This paper copes with the global optimization of Markovian energies. Energies are defined on an arbitrary graph and pairwise interactions are considered. The label set is assumed to be linearly ordered and of finite cardinality, while each interaction term (prior) shall be a submodular function. We propose an algorithm that computes a global optimizer under these assumptions. The approach consists of mapping the original problem into a combinatorial one that is shown to be globally solvable using a maximum-flow/s-t minimum-cut algorithm. This restatement relies on considering the level sets of the labels (seen as binary variables) instead of the label values themselves. The submodularity assumption of the priors is shown to be a necessary and sufficient condition for the applicability of the proposed approach. Finally, some numerical results are presented.     

A note on the time series which is the product of two stationary time series

The time series […,x_-1y_-1,x₀y₀,x₁y₁,…]> which is the product of two stationary time series x_t and y_t is studied. Such sequences arise in the study of nonlinear time series, censored time series, amplitude modulated time series, time series with random parameters, and time series with missing observations. The mean and autocovariance function of the product sequence are derived.     

A Multigrid Algorithm for Hybrid Joint PDF Simulations in Complex Geometries

In hybrid joint probability density function (joint PDF) algorithms for turbulent reactive flows the equations for the mean flow discretized with a classical grid based method (e.g. finite volume methods (FVM)) are solved together with a Monte Carlo (particle) method for the joint velocity composition PDF. When applied for complex geometries, the solution strategy for such methods which aims at obtaining a converged solution of the coupled problem on a sufficiently fine grid becomes very important. This paper describes one important aspect of this solution strategy, i.e. multigrid computing, which is well known to be very efficient for computing numerical solutions on fine grids. Two sets of grid based variables are involved: cell-centered variables from the FVM and node-centered variables, which denote the moments of the PDF extracted from the particle fields. Starting from a given multiblock grid environment first a new (refined or coarsened) grid is defined retaining the grid quality. The projection and prolongation operators are defined for the two sets of variables. In this new grid environment the particles are redistributed. The effectiveness of the multigrid algorithm is demonstrated. Compared to solely solving on the finest grid, convergence can be reached about one order of magnitude faster when using the multigrid algorithm in three stages. Computation time used for projection or prolongation is negligible. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On testing equality of pairwise rank correlations in a multivariate random vector

Spearman’s rank-correlation coefficient (also called Spearman’s rho) represents one of the best-known measures to quantify the degree of dependence between two random variables. As a copula-based dependence measure, it is invariant with respect to the distribution’s univariate marginal distribution functions. In this paper, we consider statistical tests for the hypothesis that all pairwise Spearman’s rank correlation coefficients in a multivariate random vector are equal. The tests are nonparametric and their asymptotic distributions are derived based on the asymptotic behavior of the empirical copula process. Only weak assumptions on the distribution function, such as continuity of the marginal distributions and continuous partial differentiability of the copula, are required for obtaining the results. A nonparametric bootstrap method is suggested for either estimating unknown parameters of the test statistics or for determining the associated critical values. We present a simulation study in order to investigate the power of the proposed tests. The results are compared to a classical parametric test for equal pairwise Pearson’s correlation coefficients in a multivariate random vector. The general setting also allows the derivation of a test for stochastic independence based on Spearman’s rho.     

On testing the divisibility of lacunary polynomials by cyclotomic polynomials

An algorithm is described that determines whether a given polynomial with integer coefficients has a cyclotomic factor. The algorithm is intended to be used for sparse polynomials given as a sequence of coefficient-exponent pairs. A running analysis shows that, for a fixed number of nonzero terms, the algorithm runs in polynomial time.

     

Numerical approximations and Padé approximants for a fractional population growth model

This paper presents an efficient numerical algorithm for approximate solutions of a fractional population growth model in a closed system. The time-fractional derivative is considered in the Caputo sense. The algorithm is based on Adomian’s decomposition approach and the solutions are calculated in the form of a convergent series with easily computable components. Then the Padé approximants are effectively used in the analysis to capture the essential behavior of the population u(t) of identical individuals.     

Factorization of analytic functions by means of Koenig's theorem and Toeplitz computations

Summary. By providing a matrix version of Koenig's theorem we reduce the problem of evaluating the coefficients of a monic factor r(z) of degree h of a power series f(z) to that of approximating the first h entries in the first column of the inverse of an Toeplitz matrix in block Hessenberg form for sufficiently large values of n. This matrix is reduced to a band matrix if f(z) is a polynomial. We prove that the factorization problem can be also reduced to solving a matrix equation for an matrix X, where is a matrix power series whose coefficients are Toeplitz matrices. The function is reduced to a matrix polynomial of degree 2 if f(z) is a polynomial of degreeN and . These reductions allow us to devise a suitable algorithm, based on cyclic reduction and on the concept of displacement rank, for generating a sequence of vectors that quadratically converges to the vector having as components the coefficients of the factor r(z). In the case of a polynomial f(z) of degree N, the cost of computing the entries of given is arithmetic operations, where is the cost of solving an Toeplitz-like system. In the case of analytic functions the cost depends on the numerical degree of the power series involved in the computation. From the numerical experiments performed with several test polynomials and power series, the algorithm has shown good numerical properties and promises to be a good candidate for implementing polynomial root-finders based on recursive splitting strategies. Applications to solving spectral factorization problems and Markov chains are also shown. Received September 9, 1998 / Revised version received November 14, 1999 / Published online February 5, 2001