The adaptive operational Tau method for systems of ODEs

As the Tau method, like many other numerical methods, has the limitation of using a fixed step size with some high degree (order) of approximation for solving initial value problems over long intervals, we introduce here the adaptive operational Tau method. This limitation is very much problem dependent and in such case the fixed step size application of the Tau method loses the true track of the solution. But when we apply this new adaptive method the true solution is recovered with a reasonable number of steps. To illustrate the effectiveness of this method we apply it to some stiff systems of ordinary differential equations (ODEs). The numerical results confirm the efficiency of the method.     

An asymptotic solution to non-linear transmission lines

This paper explores an asymptotic approach to the solution of a non-linear transmission line model. The model is based on a set of non-linear partial differential equations without analytical solution. The perturbations method is used to reduce the system of non-linear equations to a single non-linear partial differential equation, the modified Korteweg–de Vries equation (KdV). By using the Laplace transform, the solution is represented in integral form in terms of Green's functions. The solution for the non-linear case is obtained by means of asymptotic methods. Thus, an approximate explicit analytical solution to the problem is obtained where the errors can be controlled. This allows us to analyze the non-linear behavior of the solution. This kind of information is difficult to obtain by means of numerical methods due to the fact that for large periods of time greater computational resources are required and also accumulated errors increase. For this reason, asymptotic methods have a great importance like a natural complement to numerical methods. Computer simulations support the developments presented.     

Accuracy of multivalue methods during change of time‐step size: Adams‐Moulton

Multivalue methods are a class of time‐stepping procedures for numerical solution of differential equations that progress to a new time level using the approximate solution for the function of interest and its derivatives at a single time level. The methods differ from multistep procedures, which make use of solutions to the differential equation at multiple time levels to advance to the new time level. Multistep methods are difficult to employ when a change in time‐step is desired, because the standard formulas (e.g., Adams‐Moulton or Gear) must be modified to accommodate the change. Multivalue methods seem to possess the desirable feature that the time‐step may be changed arbitrarily as one proceeds, since the solution proceeds from a single time level. However, in practice, changes in the time‐step introduce lower order errors or alter the coefficient in the truncation error term. Here, the multivalue Adams‐Moulton method is presented based on a general interpolation procedure. Modifications required to retain the high‐order accuracy of these methods during a change in time‐step are developed. Additionally, a formula for the unknown initial derivatives is presented. Finally, two examples are provided to illustrate the potential merit of the modification to the standard multivalue methods. © 2000 John Wiley & Sons, Inc. Numer Methods Partials Differential Eq 16: 312–326, 2000     

A multigrid preconditioner for an adaptive Black-Scholes solver

This paper is concerned with the efficient solution of the linear systems of equations that arise from an adaptive space-implicit time discretisation of the Black-Scholes equation. These nonsymmetric systems are very large and sparse, so an iterative method will usually be the method of choice. However, such a method may require a large number of iterations to converge, particularly when the timestep used is large (which is often the case towards the end of a simulation which uses adaptive timestepping). An appropriate preconditioner is therefore desirable. In this paper we show that a very simple multigrid algorithm with standard components works well as a preconditioner for these problems. We analyse the eigenvalue spectrum of the multigrid iteration matrix for uniform grid problems and illustrate the method’s efficiency in practice by considering the results of numerical experiments on both uniform grids and those which use adaptivity in space.     

Performance and numerical behavior of the second‐order scheme of precise time‐step integration for transient dynamic analysis

Spurious high‐frequency responses resulting from spatial discretization in time‐step algorithms for structural dynamic analysis have long been an issue of concern in the framework of traditional finite difference methods. Such algorithms should be not only numerically dissipative in a controllable manner, but also unconditionally stable so that the time‐step size can be governed solely by the accuracy requirement. In this article, the issue is considered in the framework of the second‐order scheme of the precise integration method (PIM). Taking the Newmark‐β method as a reference, the performance and numerical behavior of the second‐order PIM for elasto‐dynamic impact‐response problems are studied in detail. In this analysis, the differential quadrature method is used for spatial discretization. The effects of spatial discretization, numerical damping, and time step on solution accuracy are explored by analyzing longitudinal vibrations of a shock‐excited rod with rectangular, half‐triangular, and Heaviside step impact. Both the analysis and numerical tests show that under the framework of the PIM, the spatial discretization used here can provide a reasonable number of model types for any given error tolerance. In the analysis of dynamic response, an appropriate spatial discretization scheme for a given structure is usually required in order to obtain an accurate and meaningful numerical solution, especially for describing the fine details of traction responses with sharp changes. Under the framework of the PIM, the numerical damping that is often required in traditional integration schemes is found to be unnecessary, and there is no restriction on the size of time steps, because the PIM can usually produce results with machine‐like precision and is an unconditionally stable explicit method. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

For numerical differentiation, dimensionality can be a blessing!

Finite difference methods, such as the mid-point rule, have been applied successfully to the numerical solution of ordinary and partial differential equations. If such formulas are applied to observational data, in order to determine derivatives, the results can be disastrous. The reason for this is that measurement errors, and even rounding errors in computer approximations, are strongly amplified in the differentiation process, especially if small step-sizes are chosen and higher derivatives are required. A number of authors have examined the use of various forms of averaging which allows the stable computation of low order derivatives from observational data. The size of the averaging set acts like a regularization parameter and has to be chosen as a function of the grid size . In this paper, it is initially shown how first (and higher) order single-variate numerical differentiation of higher dimensional observational data can be stabilized with a reduced loss of accuracy than occurs for the corresponding differentiation of one-dimensional data. The result is then extended to the multivariate differentiation of higher dimensional data. The nature of the trade-off between convergence and stability is explicitly characterized, and the complexity of various implementations is examined.

     

Shooting methods for some steady diffusion and convection problems

For diffusion-dominated steady flows, classical second-order methods are usually used. A large number of iterations, and hence a long computing time, is required to solve the set of discretized equations using an iterative method. On the other hand, a direct solver is degraded because of the accumulation of round- off errors. For convection-dominated flows, first-order upwinding has been used over the past few decades but suffered from severe inaccuracy. In this paper we first discuss the accuracy improvement of solving a diffusion equation by shooting methods. We manage to achieve the theoretical order of accuracy as the mesh size decreases as far as single-precision arithmetic is concerned. We then discuss an application to the interface coupling of subproblems in the context of domain decomposition methods. Finally, we discuss high-order nonoscillatory solutions of a convection-diffusion equation based on shooting methods.     

Piecewise parabolic method on local stencil for gasdynamic simulations

A numerical method based on piecewise parabolic difference approximations is proposed for solving hyperbolic systems of equations. The design of its numerical scheme is based on the conservation of Riemann invariants along the characteristic curves of a system of equations, which makes it possible to discard the four-point interpolation procedure used in the standard piecewise parabolic method (PPM) and to use the data from the previous time level in the reconstruction of the solution inside difference cells. As a result, discontinuous solutions can be accurately represented without adding excessive dissipation. A local stencil is also convenient for computations on adaptive meshes. The new method is compared with PPM by solving test problems for the linear advection equation and the inviscid Burgers equation. The efficiency of the methods is compared in terms of errors in various norms. A technique for solving the gas dynamics equations is described and tested for several one-and two-dimensional problems.     

The validity of least squares estimation in a time series model using the bootstrap methodology

The boostrap methodology may be used for estimating standard errors of the estimated parameters in a time series model. The idea is to approximate the theoretical error distribution by the residual distribution. The main objective of this article is to demonstrate the use of the bootstrap to attach standard errors to coefficient estimates in a second-order auto-regressive model fitted by least squares estimation. A comparison of the conventional and bootstrap methodology is made. A numerical result shows that the traditional least squares asymptotic formula for estimating standard errors appear to overestimate the true standard errors. But there are two problems in the simulation world of bootstrap for the autoregressive model of order two: (1) the first two observations y₁ and y₂ have been fixed, and (2) the residuals have not been inflated. After these two factors are considered in the trial and bootstrap experiment, both the conventional least squares and bootstrap estimates of the standard errors appear to be performing quite well.     

Adaptive stabilized mixed finite volume methods for the incompressible flow

In this article, we study adaptive stabilized mixed finite volume methods for the incompressible flows approximated using the lower order elements. A residual type of a posteriori error estimator is designed and studied with the derivation of upper and lower bounds between the exact solution and the finite volume solution. A discrete local lower bound between two successive finite volume solutions is also obtained. Also, convergence of the adaptive stabilized mixed finite volume methods is established. The presented methods have three prominent features. First, it is of practical convenience in real applications with the same partitions for velocity and pressure. Second, less computational time is required by easily applying both the lower order elements and the local grid refinement necessary for the elements of interest. Third, compared with the standard finite element method, its analysis of H¹‐norm and L²‐norm for the velocity and pressure are usually derived without any high order regularity conditions on the exact solution. © 2015 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 1424–1443, 2015     

Tabu search heuristics for the order batching problem in manual order picking systems

In a manual order picking system, order pickers walk or ride through a distribution warehouse in order to collect items requested by (internal or external) customers. In order to perform these operations efficiently, it is usually required that customer orders be combined into (more substantial) picking orders that are limited in size. The order batching problem considered in this paper deals with the question of how a given set of customer orders should be combined into picking orders such that the total length of all picker tours necessary for all of the requested items to be collected is minimized. For the solution of this problem the authors suggest two approaches based on the tabu search principle. The first is a (classic) tabu search (TS), and the second is the attribute-based hill climber (ABHC). In a series of extensive numerical experiments, these approaches are benchmarked against other solution methods put forward in the current literature. It is demonstrated that the proposed methods are superior to the existing methods and provide solutions which may allow distribution warehouses to operate more efficiently.     

Adaptive Monte Carlo methods for matrix equations with applications

This paper discusses empirical studies with both the adaptive correlated sequential sampling method and the adaptive importance sampling method which can be used in solving matrix and integral equations. Both methods achieve geometric convergence (provided the number of random walks per stage is large enough) in the sense: e_ν≤cλ^ν, where e_ν is the error at stage ν, λ∈(0,1) is a constant, c>0 is also a constant. Thus, both methods converge much faster than the conventional Monte Carlo method. Our extensive numerical test results show that the adaptive importance sampling method converges faster than the adaptive correlated sequential sampling method, even with many fewer random walks per stage for the same problem. The methods can be applied to problems involving large scale matrix equations with non-sparse coefficient matrices. We also provide an application of the adaptive importance sampling method to the numerical solution of integral equations, where the integral equations are converted into matrix equations (with order up to 8192×8192) after discretization. By using Niederreiter’s sequence, instead of a pseudo-random sequence when generating the nodal point set used in discretizing the phase space Γ, we find that the average absolute errors or relative errors at nodal points can be reduced by a factor of more than one hundred.     

Peculiarities of error accumulation in solving problems for simple equations of mathematical physics by finite difference methods

A mixed problem for the one-dimensional heat conduction equation with several versions of initial and boundary conditions is considered. To solve this problem, explicit and implicit schemes are used. Sweep and iterative methods are used for the implicit scheme when solving the system of equations. Numerical filtering of a finite sequence of results obtained for various grids with an increasing number of node points is used to analyze the method and rounding errors. To investigate rounding errors, the results obtained for various machine word mantissa lengths are compared. The numerical solution of a mixed problem for the wave equation is studied by similar methods. Some deterministic dependencies of the numerical method and rounding errors on the spatial coordinates, time, and the number of nodes are found. Some models of sources to describe the behavior of the errors in time are constructed. They are based on the results of computational experiments under various conditions. According to these models, which have been experimentally verified, the errors increase, decrease, or stabilize in time under the conditions, similarly to energy or mass.     

Equipment Location in Machining Transfer Lines with Multi-spindle Heads

The considered problem appears when a machining line must be configured. It is necessary to define the number of workstations and the number of spindle heads at each workstation to be put in the line in order to produce a given part. This problem is known to be $\mathcal{NP}$ -hard and, as a consequence, the solution time increases exponentially with the size of the problem. A number of pre-processing procedures are suggested in this article in order to decrease the initial problem size and thus shorten the solution time. A new algorithm for calculating a lower bound on the number of required equipment is also presented. A numerical example is given.     

On the choice of a method for integrating the equations of motion of a set of fluid particles

Results of numerical experiments are described in which the evolution of a set of fluid particles is computed using various time integration methods. Known exact solutions of the inviscid equations are used to analyze the errors of the methods occurring on various time intervals at the same computational costs. An adaptive algorithm for choosing an integration method depending on the domain of the phase space is proposed. The numerical results are presented as tables and plots.     

QTT-finite-element approximation for multiscale problems I: model problems in one dimension

Tensor-compressed numerical solution of elliptic multiscale-diffusion and high frequency scattering problems is considered. For either problem class, solutions exhibit multiple length scales governed by the corresponding scale parameter: the scale of oscillations of the diffusion coefficient or smallest wavelength, respectively. As is well-known, this imposes a scale-resolution requirement on the number of degrees of freedom required to accurately represent the solutions in standard finite-element (FE) discretizations. Low-order FE methods are by now generally perceived unsuitable for high-frequency coefficients in diffusion problems and high wavenumbers in scattering problems. Accordingly, special techniques have been proposed instead (such as numerical homogenization, heterogeneous multiscale method, oversampling, etc.) which require, in some form, a-priori information on the microstructure of the solution. We analyze the approximation properties of tensor-formatted, conforming first-order FE methods for scale resolution in multiscale problems without a-priori information. The FE methods are based on the dynamic extraction of principal components from stiffness matrices, load and solution vectors by the quantized tensor train (QTT) decomposition. For prototypical model problems, we prove that this approach, by means of the QTT reparametrization of the FE space, allows to identify effective degrees of freedom to replace the degrees of freedom of a uniform “virtual” (i.e. never directly accessed) mesh, whose number may be prohibitively large to realize computationally. Precisely, solutions of model elliptic homogenization and high-frequency acoustic scattering problems are proved to admit QTT-structured approximations whose number of effective degrees of freedom required to reach a prescribed approximation error scales polylogarithmically with respect to the reciprocal of the target Sobolev-norm accuracy ε with only a mild dependence on the scale parameter. No a-priori information on the nature of the problems and intrinsic length scales of the solution is required in the numerical realization of the presently proposed QTT-structured approach. Although only univariate model multiscale problems are analyzed in the present paper, QTT structured algorithms are applicable also in several variables. Detailed numerical experiments confirm the theoretical bounds. As a corollary of our analysis, we prove that for the mentioned model problems, the Kolmogorov n-widths of solution sets are exponentially small for analytic data, independently of the problems’ scale parameters. That implies, in particular, the exponential convergence of reduced basis techniques which is scale-robust, i.e., independent of the scale parameter in the problem.     

Adaptive stochastic approximation algorithm

In this paper, stochastic approximation (SA) algorithm with a new adaptive step size scheme is proposed. New adaptive step size scheme uses a fixed number of previous noisy function values to adjust steps at every iteration. The algorithm is formulated for a general descent direction and almost sure convergence is established. The case when negative gradient is chosen as a search direction is also considered. The algorithm is tested on a set of standard test problems. Numerical results show good performance and verify efficiency of the algorithm compared to some of existing algorithms with adaptive step sizes.     

Probabilistic analysis of a differential equation for linear programming

In this paper we address the complexity of solving linear programming problems with a set of differential equations that converge to a fixed point that represents the optimal solution. Assuming a probabilistic model, where the inputs are i.i.d. Gaussian variables, we compute the distribution of the convergence rate to the attracting fixed point. Using the framework of Random Matrix Theory, we derive a simple expression for this distribution in the asymptotic limit of large problem size. In this limit, we find the surprising result that the distribution of the convergence rate is a scaling function of a single variable. This scaling variable combines the convergence rate with the problem size (i.e., the number of variables and the number of constraints). We also estimate numerically the distribution of the computation time to an approximate solution, which is the time required to reach a vicinity of the attracting fixed point. We find that it is also a scaling function. Using the problem size dependence of the distribution functions, we derive high probability bounds on the convergence rates and on the computation times to the approximate solution.     

Scheduling of multistage fast-moving consumer goods plants

Fast-moving consumer goods (FMCG) plants are required to be highly flexible due to their multiproduct nature and frequent portfolio changes with seasons or consumer preferences. The multipurpose nature of equipment units usually results in changeover activities which can increase the production scheduling model’s size significantly. The objective of this paper is to present two approaches to decrease the number of changeover activities. The first approach aims to reduce unit flexibility by reducing the allowable task to unit allocations. The second approach emphasises sequencing operations on units. By limiting the set of possible task sequences in the scheduling problem, the number of allowable activities (especially changeovers) is decreased and the optimisation procedure has a smaller search space. The results of these approaches, tested against realistically sized instances indicate their effectiveness in reducing the model size and the solution time, enabling the solution of industrial examples which previously could not be solved.