Efficient uncertainty quantification with the polynomial chaos method for stiff systems

The polynomial chaos (PC) method has been widely adopted as a computationally feasible approach for uncertainty quantification (UQ). Most studies to date have focused on non-stiff systems. When stiff systems are considered, implicit numerical integration requires the solution of a non-linear system of equations at every time step. Using the Galerkin approach the size of the system state increases from n to S × n, where S is the number of PC basis functions. Solving such systems with full linear algebra causes the computational cost to increase from O(n³) to O(S³n³). The S³-fold increase can make the computation prohibitive. This paper explores computationally efficient UQ techniques for stiff systems using the PC Galerkin, collocation, and collocation least-squares (LS) formulations. In the Galerkin approach, we propose a modification in the implicit time stepping process using an approximation of the Jacobian matrix to reduce the computational cost. The numerical results show a run time reduction with no negative impact on accuracy. In the stochastic collocation formulation, we propose a least-squares approach based on collocation at a low-discrepancy set of points. Numerical experiments illustrate that the collocation least-squares approach for UQ has similar accuracy with the Galerkin approach, is more efficient, and does not require any modification of the original code.     

The collocation method for the numerical approximation of the periodic solutions of functional differential equations

A collocation method with trigonometric trial functions is presented form-order non-linear functional differential equations with periodicity boundary conditions. In general, uniform approximation of an isolated solution and of its firstm?1 derivatives is achieved, while them-derivative is approximated in mean square. In some special cases we have also the uniform approximation of them-derivative. The solution of then-th non-linear collocation equation may be approximated by Newton's iteration with an arbitrary starting point belonging to a suitable neighbourhood of an isolated solution, for alln>n ₀ withn ₀ large enough.     

The Tau Method as an analytic tool in the discussion of equivalence results across numerical methods

A Tau Method approximate solution of a given differential equation defined on a compact [a, b] is obtained by adding to the right hand side of the equation a specific minimal polynomial perturbation termH _n(x), which plays the role of a representation of zero in [a,b] by elements of a given subspace of polynomials. Neither discretization nor orthogonality are involved in this process of approximation. However, there are interesting relations between the Tau Method and approximation methods based on the former techniques. In this paper we use equivalence results for collocation and the Tau Method, contributed recently by the authors together with classical results in the literature, to identify precisely the perturbation termH(x) which would generate a Tau Method approximate solution, identical to that generated by some specific discrete methods over a given mesh Π ∈ [a, b]. Finally, we discuss a technique which solves the inverse problem, that is, to find adiscrete perturbed Runge-Kutta scheme which would simulate a prescribed Tau Method. We have chosen, as an example, a Tau Method which recovers the same approximation as an orthogonal expansion method. In this way we close the diagram defined by finite difference methods, collocation schemes, spectral techniques and the Tau Method through a systematic use of the latter as an analytical tool.     

hp-Legendre–Gauss collocation method for impulsive differential equations

The original Legendre–Gauss collocation method is derived for impulsive differential equations, and the convergence is analysed. Then a new hp-Legendre–Gauss collocation method is presented for impulsive differential equations, and the convergence for the hp-version method is also studied. The results obtained in this paper show that the convergence condition for the original Legendre–Gauss collocation method depends on the impulsive differential equation, and it cannot be improved, however, the convergence condition for the hp-Legendre–Gauss collocation method depends both on the impulsive differential equation and the meshsize, and we always can choose a sufficient small meshsize to satisfy it, which show that the hp-Legendre–Gauss collocation method is superior to the original version. Our theoretical results are confirmed in two test problems.     

A class of hybrid collocation methods for third-order ordinary differential equations

A class of numerical methods is proposed for solving general third-order ordinary differential equations directly by collocation at the grid points x = x _n+j , i = 0(1)k and at an off grid point x = x _n+u , where k is the step number of the method and u is an arbitrary rational number in (x _n , x _n+k ). A predictor of order 2k ? 1 is also proposed to cater for y _n+k in the main method. Taylor series expansion is employed for the calculation of y _n+1, y _n+2, y _n+u and their higher derivatives. Evaluation of the resulting method at x = x _n+k for any value of u in the specified open interval yields a particular discrete scheme as a special case of the method. The efficiency of the method is tested on some general initial value problems of third-order ordinary differential equations.     

A Fast Collocation Method for Eigen-Problems of Weakly Singular Integral Operators

A multiscale collocation method is developed for solving the eigen-problem of weakly singular integral operators. We employ a matrix truncation strategy of Chen, Micchelli and Xu to compress the collocation matrix, which the compressed matrix has only O(NlogN)\mathcal{O}(N\log N) nonzero entries, where N denotes the order of the matrix. This truncation leads to a fast collocation method for solving the eigen-problem. We prove that the fast collocation method has the optimal convergence order for approximation of the eigenvalues and eigenvectors. The power iteration method is used for solving the corresponding discrete eigen-problem. We present a numerical example to demonstrate how the methods can be used to compute a nonzero eigenvalue rapidly and efficiently.     

A Nonoverlapping Domain Decomposition Method for Legendre Spectral Collocation Problems

We consider the Dirichlet boundary value problem for Poisson’s equation in an L-shaped region or a rectangle with a cross-point. In both cases, we approximate the Dirichlet problem using Legendre spectral collocation, that is, polynomial collocation at the Legendre–Gauss nodes. The L-shaped region is partitioned into three nonoverlapping rectangular subregions with two interfaces and the rectangle with the cross-point is partitioned into four rectangular subregions with four interfaces. In each rectangular subregion, the approximate solution is a polynomial tensor product that satisfies Poisson’s equation at the collocation points. The approximate solution is continuous on the entire domain and its normal derivatives are continuous at the collocation points on the interfaces, but continuity of the normal derivatives across the interfaces is not guaranteed. At the cross point, we require continuity of the normal derivative in the vertical direction. The solution of the collocation problem is first reduced to finding the approximate solution on the interfaces. The discrete Steklov–Poincaré operator corresponding to the interfaces is self-adjoint and positive definite with respect to the discrete inner product associated with the collocation points on the interfaces. The approximate solution on the interfaces is computed using the preconditioned conjugate gradient method. A preconditioner is obtained from the discrete Steklov–Poincaré operators corresponding to pairs of the adjacent rectangular subregions. Once the solution of the discrete Steklov–Poincaré equation is obtained, the collocation solution in each rectangular subregion is computed using a matrix decomposition method. The total cost of the algorithm is O(N ³), where the number of unknowns is proportional to N ².      

Comparison of collocation methods for the solution of second order non-linear boundary value problems

This article concerns the application of cubic spline collocation tau-method for solving non-linear second order ordinary differential equations. Three collocation methods [Taiwo, O.A., 1986, A computational method for ordinary differential equations and error estimation. MSc dissertation, University of Ilorin, Nigeria (unpublished); Taiwo, O.A., 2002, Exponential fitting for the solution of two point boundary value problem with cubic spline collocation tau-method. International Journal of Computer Mathematics, 79(3), 229–306.] are discussed and applied to some second order non-linear problems. They are standard collocation, perturbed collocation, and exponentially fitted collocation. Numerical examples are given to illustrate the accuracy, efficiency and computational cost.     

A Bessel polynomial approach for solving general linear Fredholm integro-differential–difference equations

In this paper, to find an approximate solution of general linear Fredholm integro-differential–difference equations (FIDDEs) under the initial-boundary conditions in terms of the Bessel polynomials, a practical matrix method is presented. The idea behind the method is that it converts FIDDEs to a matrix equation which corresponds to a system of linear algebraic equations and is based on the matrix forms of the Bessel polynomials and their derivatives by means of collocation points. The solutions are obtained as the truncated Bessel series in terms of the Bessel polynomials J _n (x) of the first kind defined in the interval [0, ∞). The error analysis and the numerical examples are included to demonstrate the validity and applicability of the technique.     

The discrete collocation method for weakly singular Urysohn equations

In this paper, we analyse the iterated collocation method for the nonlinear Urysohn operator equation x=y+K(x) with K a singular kernel. The paper extends the study [H. Kaneko, R.D. Noren, and P.A. Padilla, J. Comput. Appl. Math. 80 (1997), pp. 335–349] in which the convergence of the iterated collocation method for Urysohn equations is considered.     

Doubling the Degree of Precision Without Doubling the Grid When Solving a Differential Equation with a Pseudo-Spectral Collocation Method

In the conventional pseudo-spectral collocation method to solve an ordinary first order differential equation, the derivative is obtained from Lagrange interpolation and has degree of precision N for a grid of (N+1) points. In the present, novel method Hermite interpolation is used as point of departure. From this the second order derivative is obtained with degree of precision (2N+1) for the same grid as above. The associated theorem constitutes the main result of this paper. Based on that theorem a method in put forward in which the differential equation and the differentiated differential equation are simultaneously collocated. In this method every grid point counts for two. The double collocation leads to a solution accuracy which is superior to the precision obtained with the conventional method for the same grid. This superiority is demonstrated by 3 examples, 2 linear problems and a non-linear one. In the examples it is shown that the accuracy obtained with the present method is comparable to the solution accuracy of the standard method with twice the number of grid points. However, the condition number of the present method grows like N ³ as compared to N ² in the standard method.     

An extended collocation method

Given an approximate solutionx _n of a linear operator equation obtained by a collocation method, an improved solutionx ^* _n+m is obtained fromx _n by an «extended collocation method» which consists in solving a further (m)-order linear system instead of an (n+m)-order one, diminishing the effects of rounding error in carrying out the calculations. For a suitable choice of the knot, the method may be recursively performed both by spline approximation and by algebraic and trigonometric polynomial approximation. A numerical example with a two point boundary value problem confirms the advantages of the extended method with respect to the direct one.     

A new numerical method to calculate the vibrations of clamped kirchhoff-plates of arbitrary form

A new collocation method is presented which is able to calculate numerically the vibrations of clamped plates with no external load. The method works in Cartesian coordinates and allows to investigate plates with boundaries given byF(x, y)=0. FORTRAN andMathematica codes are available. It does not use polynomials or splines, but analytic solutions.     

Nth-order fuzzy linear differential equations

In this paper a numerical method for solving nth-order linear differential equations with fuzzy initial conditions is considered. The idea is based on the collocation method. The existence theorem of the fuzzy solution is considered. This method is illustrated by solving several examples.     

Pseudospectral methods for solving infinite-horizon optimal control problems

An important aspect of numerically approximating the solution of an infinite-horizon optimal control problem is the manner in which the horizon is treated. Generally, an infinite-horizon optimal control problem is approximated with a finite-horizon problem. In such cases, regardless of the finite duration of the approximation, the final time lies an infinite duration from the actual horizon at t=+∞. In this paper we describe two new direct pseudospectral methods using Legendre–Gauss (LG) and Legendre–Gauss–Radau (LGR) collocation for solving infinite-horizon optimal control problems numerically. A smooth, strictly monotonic transformation is used to map the infinite time domain t∈[0,∞) onto a half-open interval τ∈[−1,1). The resulting problem on the finite interval is transcribed to a nonlinear programming problem using collocation. The proposed methods yield approximations to the state and the costate on the entire horizon, including approximations at t=+∞. These pseudospectral methods can be written equivalently in either a differential or an implicit integral form. In numerical experiments, the discrete solution exhibits exponential convergence as a function of the number of collocation points. It is shown that the map ?:[−1,+1)→[0,+∞) can be tuned to improve the quality of the discrete approximation.     

On the stability of collocation methods for the two-dimensional Burgers equation — The Fourier case

We investigate Fourier collocation approximations of the evolutionary twodimensional Burgers equation. The numerical schemes are not required to be semi-conservative. We obtain stability estimates in theH ¹() norm that are uniform in time. Our results show that collocation techniques do not yield instability, at least if the resolution is fine enough.     

Shifted fractional Legendre spectral collocation technique for solving fractional stochastic Volterra integro-differential equations

This paper presents a spectral collocation technique to solve fractional stochastic Volterra integro-differential equations (FSV-IDEs). The algorithm is based on shifted fractional order Legendre orthogonal functions generated by Legendre polynomials. The shifted fractional order Legendre–Gauss–Radau collocation (SFL-GR-C) method is developed for approximating the FSV-IDEs, with the objective of obtaining a system of algebraic equations. For computational purposes, the Brownian motion function W(x) is discretized by Lagrange interpolation, while the integral terms are interpolated by Legendre–Gauss–Lobatto quadrature. Numerical examples demonstrate the accuracy and applicability of the proposed technique, even when dealing with non-smooth solutions.

     

A tight lower bound for the worst case of Bottom-Up-Heapsort

Bottom-Up-Heapsort is a variant of Heapsort. Its worst-case complexity for the number of comparisons is known to be bounded from above by 3/2n logn+0(n), wheren is the number of elements to be sorted. There is also an example of a heap which needs 5/4n logn-0(n log logn) comparisons. We show in this paper that the upper bound is asymptotically tight, i.e., we prove for largen the existence of heaps which need at least 3/2n logn–O(n log logn) comparisons. This result also proves the old conjecture that the best case for classical Heapsort needs only asymptotic n logn + O(n log logn) comparisons.This work was supported by the ESPRIT II program of the EC under Contract No. 3075 (project ALCOM).     

Changing the diameter of the locally twisted cube

The hypercube network Q _n has been proved to be one of the most popular interconnection networks. The n-dimensional locally twisted cube LTQ _n is an important variant of Q _n . One of the critical performance factors of an interconnection network is the diameter which determines the maximum communication time between any pair of processors. In this paper, we investigate the diameter variability problems arising from the addition and deletion of edges in LTQ _n . We obtain three results in this paper: (1) for any integer n≥2, we find the least number of edges (denoted by ch ^?(LTQ _n )), whose deletion from LTQ _n causes the diameter to increase, (2) for any integer n≥2, when ch ^?(LTQ _n ) edges are deleted, the diameter will increase by 1 and (3) for any integer n≥4, the least number of edges whose addition to LTQ _n will decrease the diameter is at most 2 ^n?1.     

A Note on the Spectral Collocation Approximation of Some Differential Equations with Singular Source Terms

The solution of differential equations with singular source terms contains the local jump discontinuity in general and its spectral approximation is oscillatory due to the Gibbs phenomenon. To minimize the Gibbs oscillations near the local jump discontinuity and improve convergence, the regularization of the approximation is needed. In this note, a simple derivative of the discrete Heaviside function H _c (x) on the collocation points is used for the approximation of singular source terms δ(x−c) or δ ⁽ⁿ⁾(x−c) without any regularization. The direct projection of H _c (x) yields highly oscillatory approximations of δ(x−c) and δ ⁽ⁿ⁾(x−c). In this note, however, it is shown that the direct projection approach can yield a non-oscillatory approximation of the solution and the error can also decay uniformly for certain types of differential equations. For some differential equations, spectral accuracy is also recovered. This method is limited to certain types of equations but can be applied when the given equation has some nice properties. Numerical examples for elliptic and hyperbolic equations are provided. The current address: Department of Mathematics, State University of New York at Buffalo, Buffalo, NY 14260-2900, USA.