High-Dimensional Adaptive Sparse Polynomial Interpolation and Applications to Parametric PDEs

We consider the problem of Lagrange polynomial interpolation in high or countably infinite dimension, motivated by the fast computation of solutions to partial differential equations (PDEs) depending on a possibly large number of parameters which result from the application of generalised polynomial chaos discretisations to random and stochastic PDEs. In such applications there is a substantial advantage in considering polynomial spaces that are sparse and anisotropic with respect to the different parametric variables. In an adaptive context, the polynomial space is enriched at different stages of the computation. In this paper, we study an interpolation technique in which the sample set is incremented as the polynomial dimension increases, leading therefore to a minimal amount of PDE solving. This construction is based on the standard principle of tensorisation of a one-dimensional interpolation scheme and sparsification. We derive bounds on the Lebesgue constants for this interpolation process in terms of their univariate counterpart. For a class of model elliptic parametric PDE’s, we have shown in Chkifa et al. (Modél. Math. Anal. Numér. 47(1):253–280, 2013) that certain polynomial approximations based on Taylor expansions converge in terms of the polynomial dimension with an algebraic rate that is robust with respect to the parametric dimension. We show that this rate is preserved when using our interpolation algorithm. We also propose a greedy algorithm for the adaptive selection of the polynomial spaces based on our interpolation scheme, and illustrate its performance both on scalar valued functions and on parametric elliptic PDE’s.     

MODWT-ARMA model for time series prediction

Many time series in the applied sciences display a time-varying second order structure and long-range dependence (LRD). In this paper, we present a hybrid MODWT-ARMA model by combining the maximal overlap discrete wavelet transform (MODWT) and the ARMA model to deal with the non-stationary and LRD time series. We prove theoretically that the details series obtained by MODWT are stationary and short-range dependent (SRD). Then we derive the general form of MODWT-ARMA model. In the experimental study, the daily rainfall and Mackey–Glass time series are used to assess the performance of the hybrid model. Finally, the normalized error comparison with DWT-ARMA, EMD-ARMA and ARIMA model indicates that this combined model is an effective way to improve forecasting accuracy.     

Cluster synchronization for T–S fuzzy complex networks using pinning control with probabilistic time‐varying delays

In this article, cluster synchronization problem for Lur'e type Takagi–Sugeno (T–S) fuzzy complex networks with probabilistic time‐varying delays is considered. Pinning control strategy is proposed. The probability distribution of the time‐varying delay is considered. In terms of the probability distribution of the delays, a new type of system model with probability‐distribution‐dependent parameter matrices is proposed. Moreover, probabilistic delay is assumed to satisfy certain probability distribution and the probability of the delay takes values in some intervals. By constructing a suitable Lyapunov–Krasovskii functional involving triple integral terms and using Kronecker product with convex combination technique, some sufficient conditions are derived to ensure the cluster synchronization of designed networks such that the linear feedback controller can be used to every cluster. The problem of controller design is converted into solving a series of linear matrix inequalities. The effectiveness of our results is verified through numerical examples and simulations. © 2014 Wiley Periodicals, Inc. Complexity 21: 59–77, 2015     

Memory properties of transformations of linear processes

In this paper, we study the memory properties of transformations of linear processes. Dittmann and Granger (J Econ 110:113–133, 2002) studied the polynomial transformations of Gaussian FARIMA(0, d, 0) processes by applying the orthonormality of the Hermite polynomials under the measure for the standard normal distribution. Nevertheless, the orthogonality does not hold for transformations of non-Gaussian linear processes. Instead, we use the decomposition developed by Ho and Hsing (Ann Stat 24:992–1024, 1996; Ann Probab 25:1636–1669, 1997) to study the memory properties of nonlinear transformations of linear processes, which include the FARIMA(p, d, q) processes, and obtain consistent results as in the Gaussian case. In particular, for stationary processes, the transformations of short-memory time series still have short-memory and the transformation of long-memory time series may have different weaker memory parameters which depend on the power rank of the transformation. On the other hand, the memory properties of transformations of non-stationary time series may not depend on the power ranks of the transformations. This study has application in econometrics and financial data analysis when the time series observations have non-Gaussian heavy tails. As an example, the memory properties of call option processes at different strike prices are discussed in details.     

Multi-depot rural postman problems

This paper studies multi-depot rural postman problems on an undirected graph. These problems extend the well-known undirected rural postman problem to the case where there are several depots instead of just one. Linear integer programming formulations that only use binary variables are proposed for the problem that minimizes the overall routing costs and for the model that minimizes the length of the longest route. An exact branch-and-cut algorithm is presented for each considered model, where violated constraints of both types are separated in polynomial time. Despite the difficulty of the problems, the numerical results from a series of computational experiments with various types of instances illustrate a quite good behavior of the algorithms. When the overall routing costs are minimized, over 43 % of the instances were optimally solved at the root node, and 95 % were solved at termination, most of them with a small additional computational effort. When the length of the longest route is minimized, over 25 % of the instances were optimally solved at the root node, and 99 % were solved at termination.     

Baer and Quasi-Baer Properties of Skew Generalized Power Series Rings

Let R be a ring, (S, ≤) a strictly ordered monoid and ω: S → End(R) a monoid homomorphism. The skew generalized power series ring R[[S, ω]] is a common generalization of (skew) polynomial rings, (skew) power series rings, (skew) Laurent polynomial rings, (skew) group rings, and Mal'cev–Neumann Laurent series rings. In this article, we study relations between the (quasi-) Baer, principally quasi-Baer and principally projective properties of a ring R, and its skew generalized power series extension R[[S, ω]]. As particular cases of our general results, we obtain new theorems on (skew) group rings, Mal'cev–Neumann Laurent series rings, and the ring of generalized power series.     

Computing Derivatives of Jacobi Polynomials Using Bernstein Transformation and Differentiation Matrix

In this paper, we give a new, simple, and efficient method for evaluating the pth derivative of the Jacobi polynomial of degree n. The Jacobi polynomial is written in terms of the Bernstein basis, and then the pth derivative is obtained. The results are given in terms of both Bernstein basis of degree n ? p and Jacobi basis form of degree n ? p and presented in a matrix form. Numerical examples and comparisons with other well-known methods are presented.     

Superconvergence of H 1-Galerkin Mixed Finite Element Methods for Second-Order Elliptic Equations

We derive superconvergence result for H ¹-Galerkin mixed finite element method for second-order elliptic equations over rectangular partitions. Compared to standard mixed finite element procedure, the method is not subject to the Ladyzhenskaya–Bab?ska–Brezzi (LBB) condition and the approximating finite element spaces are allowed to be of different polynomial degrees. Superconvergence estimate of order 𝒪(h ^k+3), where k ≥ 1 is the order of the approximating polynomials employed in the Raviart–Thomas elements, is established for the flux via a postprocessing technique.     

A Deterministic Algorithm to Compute Approximate Roots of Polynomial Systems in Polynomial Average Time

We describe a deterministic algorithm that computes an approximate root of n complex polynomial equations in n unknowns in average polynomial time with respect to the size of the input, in the Blum–Shub–Smale model with square root. It rests upon a derandomization of an algorithm of Beltrán and Pardo and gives a deterministic affirmative answer to Smale’s 17th problem. The main idea is to make use of the randomness contained in the input itself.     

Differential Equations for Singular Vectors of sp(2n)

ABSTRACT

Given a weight λ of sp(2n), we derive a system of variable-coefficient second-order linear partial differential equations that determines the singular vectors in the corresponding Verma module. Moreover, we find a family of exact solutions of the system in a certain space of power series. The polynomial solutions correspond to the singular vectors in the Verma module. In particular, we find the explicit expression of a singular vector corresponding to the single condition that ? λ,α? + ht α is a nonnegative integer for some positive root α, whose existence was proven by Jantzen. In the case n = 2, we completely solved the system in a certain space of power series.     

A spectral element method using the modal basis and its application in solving second‐order nonlinear partial differential equations

We present a high‐order spectral element method (SEM) using modal (or hierarchical) basis for modeling of some nonlinear second‐order partial differential equations in two‐dimensional spatial space. The discretization is based on the conforming spectral element technique in space and the semi‐implicit or the explicit finite difference formula in time. Unlike the nodal SEM, which is based on the Lagrange polynomials associated with the Gauss–Lobatto–Legendre or Chebyshev quadrature nodes, the Lobatto polynomials are used in this paper as modal basis. Using modal bases due to their orthogonal properties enables us to exactly obtain the elemental matrices provided that the element‐wise mapping has the constant Jacobian. The difficulty of implementation of modal approximations for nonlinear problems is treated in this paper by expanding the nonlinear terms in the weak form of differential equations in terms of the Lobatto polynomials on each element using the fast Fourier transform (FFT). Utilization of the Fourier interpolation on equidistant points in the FFT algorithm and the enough polynomial order of approximation of the nonlinear terms can lead to minimize the aliasing error. Also, this approach leads to finding numerical solution of a nonlinear differential equation through solving a system of linear algebraic equations. Numerical results for some famous nonlinear equations illustrate efficiency, stability and convergence properties of the approximation scheme, which is exponential in space and up to third‐order in time. Copyright © 2014 John Wiley & Sons, Ltd.     

Estimation of fixed points for nonlinear time series

Identification of fixed points is very important in dynamic systems analysis. One method used is based on polynomial regression. In this article, we show that methods other than that of Aguirre and Souza can be more accurate if the classical assumptions for regression are violated. Simulation results reveal that an artificial neural network (ANN) is more precise than the Aguirre and Souza method, which is based on cluster expansion method. Overall, ANN is the best method for finding fixed (equilibrium) points of nonlinear time series, followed by nonparametric regression in terms of accuracy. For larger sample sizes, ANN estimates are generally accurate and the method is robust to changes in the signal/noise ratio. © 2013 Wiley Periodicals, Inc. Complexity 19: 30–39, 2014     

Codimension Growth of Strong Lie Nilpotent Associative Algebras

We study Lie nilpotent varieties of associative algebras. We explicitly compute the codimension growth for the variety of strong Lie nilpotent associative algebras. The codimension growth is polynomial and found in terms of Stirling numbers of the first kind. To achieve the result we take the free Lie algebra of countable rank L(X), consider its filtration by the lower central series and shift it. Next we apply generating functions of special type to the induced filtration of the universal enveloping algebra U(L(X)) = A(X).     

On the Froissart phenomenon in multivariate homogeneous Padé approximation

In univariate Padé approximation we learn from the Froissart phenomenon that Padé approximants to perturbed Taylor series exhibit almost cancelling pole–zero combinations that are unwanted. The location of these pole–zero doublets was recently characterized for rational functions by the so‐called Froissart polynomial. In this paper the occurrence of the Froissart phenomenon is explored for the first time in a multivariate setting. Several obvious questions arise. Which definition of Padé approximant is to be used? Which multivariate rational functions should be investigated? When considering univariate projections of these functions, our analysis confirms the univariate results obtained so far in [13], under the condition that the noise is added after projection. At the same time, it is apparent from section 4 that for the unprojected multivariate Froissart polynomial no conjecture can be formulated yet.

     

Quintic spline technique for time fractional fourth‐order partial differential equation

Higher order non‐Fickian diffusion theories involve fourth‐order linear partial differential equations and their solutions. A quintic polynomial spline technique is used for the numerical solutions of fourth‐order partial differential equations with Caputo time fractional derivative on a finite domain. These equations occur in many applications in real life problems such as modeling of plates and thin beams, strain gradient elasticity, and phase separation in binary mixtures, which are basic elements in engineering structures and are of great practical significance to civil, mechanical, and aerospace engineering. The quintic polynomial spline technique is used for space discretization and the time‐stepping is done using a backward Euler method based on the L1 approximation to the Caputo derivative. The stability and convergence analysis are also discussed. The numerical results are given, which demonstrate the effectiveness and accuracy of the numerical method. The numerical results obtained in this article are also compared favorably well with the results of (S. S. Siddiqi and S. Arshed, Int. J. Comput. Math. 92 (2015), 1496–1518). © 2016 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 33: 445–466, 2017     

N-tuple S&P patterns across decades, 1950–2011

Numerous studies have analyzed the movements of the S&P 500 index using several methodologies such as technical analysis, econometric modeling, time series techniques and theories from behavioral finance. In this paper we take a novel approach. We use daily closing prices for the S&P 500 index for a very long period from 1/3/1950 to 7/19/2011 for a total of 15,488 daily observations. We then investigate the up and down movements and their combinations for 1–7 days giving us multiple possible patterns for over six decades. Some patterns of each type are more dominant across decades. We split the data into training and validation sets and then select the dominant patterns to build conditional forecasts in several ways, including using a decision tree methodology. The best model is correct 51 % of the time on the validation set when forecasting a down day, and 61 % when forecasting an up day. We show that certain conditional forecasts outperform the unconditional random walk model.     

Fast algorithms for fragmentable items bin packing

Bin packing with fragmentable items is a variant of the classic bin packing problem where items may be cut into smaller fragments. The objective is to minimize the number of item fragments, or equivalently, to minimize the number of cuts, for a given number of bins. Models based on packing fragmentable items are useful for representing finite shared resources. In this article, we present improvements to approximation and metaheuristic algorithms to obtain an optimality-preserving optimization algorithm with polynomial complexity, worst-case performance guarantees and parametrizable running time. We also present a new family of fast lower bounds and prove their worst-case performance ratios. We evaluate the performance and quality of the algorithm and the best lower bound through a series of computational experiments on representative problem instances. For the studied problem sets, one consisting of 180 problems with up to 20 items and another consisting of 450 problems with up to 1024 items, the lower bound performs no worse than 5 / 6. For the first problem set, the algorithm found an optimal solution in 92 % of all 1800 runs. For the second problem set, the algorithm found an optimal solution in 99 % of all 4500 runs. No run lasted longer than 220 ms.     

Marcinkiewicz–Zygmund Inequalities and Polynomial Approximation from Scattered Data on SO(3)

We consider scattered data approximation problems on SO(3). To this end, we construct a new operator for polynomial approximation on the rotation group. This operator reproduces Wigner-D functions up to a given degree and has uniformly bounded L ^p -operator norm for all 1 ≤ p ≤ ∞. The operator provides a polynomial approximation with the same approximation degree of the best polynomial approximation. Moreover, the operator together with a Markov type inequality for Wigner-D functions enables us to derive scattered data L ^p -Marcinkiewicz–Zygmund inequalities for these functions for all 1 ≤ p ≤ ∞. As a major application of such inequalities, we consider the stability of the weighted least squares approximation problem on SO(3).     

Plane wave approximation of homogeneous Helmholtz solutions

In this paper, we study the approximation of solutions of the homogeneous Helmholtz equation Δu + ω ² u = 0 by linear combinations of plane waves with different directions. We combine approximation estimates for homogeneous Helmholtz solutions by generalized harmonic polynomials, obtained from Vekua’s theory, with estimates for the approximation of generalized harmonic polynomials by plane waves. The latter is the focus of this paper. We establish best approximation error estimates in Sobolev norms, which are explicit in terms of the degree of the generalized polynomial to be approximated, the domain size, and the number of plane waves used in the approximations.     

Global exponential stability for the Mackey–Glass model of respiratory dynamics with a control term

This paper is concerned with the stability of positive periodic solutions for the Mackey–Glass model of respiratory dynamics with a control term. We prove the existence, positivity, and permanence of solutions, which help to deduce the global exponential stability of positive periodic solutions for this model. Our method relies upon a differential inequality technique and a Lyapunov functional. At the end, we give an example with numerical simulations to demonstrate the theoretical results. Copyright © 2016 John Wiley & Sons, Ltd.