An optimal time–space algorithm for dense stereo matching

The increasing demand for higher resolution images and higher frame rate videos will always pose a challenge to computational power when real-time performance is required to solve the stereo-matching problem in 3D reconstruction applications. Therefore, the use of asymptotic analysis is necessary to measure the time and space performance of stereo-matching algorithms regardless of the size of the input and of the computational power available. In this paper, we survey several classic stereo-matching algorithms with regard to time–space complexity. We also report running time experiments for several algorithms that are consistent with our complexity analysis. We present a new dense stereo-matching algorithm based on a greedy heuristic path computation in disparity space. A procedure which improves disparity maps in depth discontinuity regions is introduced. This procedure works as a post-processing step for any technique that solves the dense stereo-matching problem. We prove that our algorithm and post-processing procedure have optimal O(n) time–space complexity, where n is the size of a stereo image. Our algorithm performs only a constant number of computations per pixel since it avoids a brute force search over the disparity range. Hence, our algorithm is faster than “real-time” techniques while producing comparable results when evaluated with ground-truth benchmarks. The correctness of our algorithm is demonstrated with experiments in real and synthetic data.     

The EM algorithm in a distributed computing environment for modelling environmental space–time data

Statistical models for spatio-temporal data are increasingly used in environmetrics, climate change, epidemiology, remote sensing and dynamical risk mapping. Due to the complexity of the relationships among the involved variables and dimensionality of the parameter set to be estimated, techniques for model definition and estimation which can be worked out stepwise are welcome. In this context, hierarchical models are a suitable solution since they make it possible to define the joint dynamics and the full likelihood starting from simpler conditional submodels. Moreover, for a large class of hierarchical models, the maximum likelihood estimation procedure can be simplified using the Expectation–Maximization (EM) algorithm.In this paper, we define the EM algorithm for a rather general three-stage spatio-temporal hierarchical model, which includes also spatio-temporal covariates. In particular, we show that most of the parameters are updated using closed forms and this guarantees stability of the algorithm unlike the classical optimization techniques of the Newton–Raphson type for maximizing the full likelihood function. Moreover, we illustrate how the EM algorithm can be combined with a spatio-temporal parametric bootstrap for evaluating the parameter accuracy through standard errors and non-Gaussian confidence intervals.To do this a new software library in form of a standard R package has been developed. Moreover, realistic simulations on a distributed computing environment allow us to discuss the algorithm properties and performance also in terms of convergence iterations and computing times.     

Decomposition based hybrid VNS–TS algorithm for distributed parallel factories scheduling with virtual corporation

The main purpose of this paper is to develop a decomposition based hybrid variable neighborhood search/tabu search (DVT) algorithm for multi-factory production network scheduling problem where a number of different individual factories collaborate despite their different objectives. It is assumed some of the network's factories are interested in total processing cost minimization whereas the remaining factories are interested in the production profits maximization. It is also assumed that jobs can migrate from their original factory to other factories but a transportation time is incurred. Our proposed algorithm comprises of a tabu search and a variable neighborhood search with several local search algorithms. In this hybridization, to improve the search ability of the algorithm, we make use of guiding principles with ordering of neighborhood structures by mixed integer linear programming relaxation. In the proposed algorithm, the parallel search strategy is designed for a scalar bi-objective. Multiple objectives are combined with L₁-metric technique then each sub-search procedure evolves separately until a good approximation of the Pareto-front is obtained. The non-dominated sets obtained from our algorithm and original heuristic (algorithm without ordering concept) are compared using three different indices. Furthermore, the problem is modeled as a mixed integer linear programming and solved by improved ϵ-constraint approach (IEA) with CPLEX solver. The results of comparisons between IEA and DVT algorithm showed the proposed algorithm yielded most of the solutions in the net non-dominated front.     

A fast algorithm for solving the space–time fractional diffusion equation

In this paper, we propose a fast algorithm for efficient and accurate solution of the space–time fractional diffusion equations defined in a rectangular domain. The spatial discretization is done by using the central finite difference scheme and matrix transfer technique. Due to its nonlocality, numerical discretization of the spectral fractional Laplacian ${(?\Delta )}_s^{\alpha /2}$ results in a large dense matrix. This causes considerable challenges not only for storing the matrix but also for computing matrix–vector products in practice. By utilizing the compact structure of the discrete system and the discrete sine transform, our algorithm avoids to store the large matrix from discretizing the nonlocal operator and also significantly reduces the computational costs. We then use the Laplace transform method for time integration of the semi-discretized system and a weighted trapezoidal method to numerically compute the convolutions needed in the resulting scheme. Various experiments are presented to demonstrate the efficiency and accuracy of our method.     

A BSS-based space–time multi-channel algorithm for complex-jamming suppression

This paper considers the problem of suppressing complex-jamming, which contains sidelobe blanket jammings (SLJs), multiple near-mainlobe blanket jammings (multiple-NMLJs) and self-defensive false target jamming (SDJ). We propose a blind source separation (BSS)-based space–time multi-channel algorithm for complex-jamming suppression. The space–time multi-channel consists of spatial multiple beams and temporal multiple adjacent pulse repetition intervals (PRIs). The source signals can be separated by the BSS, owing to their statistical independence. The real target and SDJ can then be obtained by the pulse compression approach, distinguished by echo identification simultaneously. A remarkable feature of the proposed approach is that it does not require prior knowledge about real target or jammings, and it is easy to implement for engineering applications.     

An iterative algorithm for simulation error based identification of polynomial input–output models using multi-step prediction

Effective identification of polynomial input–output models for applications requiring long-range prediction or simulation performance relies on both careful model selection and accurate parameter estimation. The simulation error minimisation (SEM) approach has been shown to provide significant advantages in the model selection phase by ruling out candidate models with good short-term prediction capabilities but unsuitable long-term dynamics. However, SEM-based parameter estimation has been generally avoided due to excessive computational effort. This article extends to the nonlinear case a computationally efficient approach for this task, that was previously developed for linear models, based on the iterative estimation of predictors with increasing prediction horizon. Conditions for the applicability of the approach to various model classes are also discussed. Finally, some examples are provided to show the effectiveness and computational convenience of the proposed algorithm for polynomial input–output identification, as well as the improvements achievable by enforcing SEM parameter estimation. A benchmark for nonlinear identification is also analysed, with encouraging results.     

Modeling of distributed parameter systems for applications—A synthesized review from time–space separation

Many industrial processes belong to distributed parameter systems (DPS) that have strong spatial–temporal dynamics. Modeling of DPS is difficult but essential to simulation, control and optimization. The first-principle modeling for known DPS often leads to the partial differential equation (PDE). Because it is an infinite-dimensional system, the model reduction (MR) is very necessary for real implementation. The model reduction often works with selection of basis functions (BF). Combination of different BF and MR results in different approaches. For unknown DPS, system identification is usually used to figure out unknown structure and parameters. Using various methods, different approaches are developed. Finally, a novel kernel-based approach is proposed for the complex DPS. This paper provides a brief review of different DPS modeling methods and categorizes them from the view of time–space separation.     

An analysis of the time integration algorithms for the finite element solutions of incompressible Navier–Stokes equations based on a stabilised formulation

This work is concerned with the analysis of time integration procedures for the stabilised finite element formulation of unsteady incompressible fluid flows governed by the Navier–Stokes equations. The stabilisation technique is combined with several different implicit time integration procedures including both finite difference and finite element schemes. Particular attention is given to the generalised-α method and the linear discontinuous in time finite element scheme. The time integration schemes are first applied to two model problems, represented by a first order differential equation in time and the one dimensional advection–diffusion equation, and subjected to a detailed mathematical analysis based on the Fourier series expansion. In order to establish the accuracy and efficiency of the time integration schemes for the Navier–Stokes equations, a detailed computational study is performed of two standard numerical examples: unsteady flow around a cylinder and flow across a backward facing step. It is concluded that the semi-discrete generalised-α method provides a viable alternative to the more sophisticated and expensive space–time methods for simulations of unsteady flows of incompressible fluids governed by the Navier–Stokes equations.     

An extended inner–outer factorisation algorithm based on the structure of a transfer function matrix inverse

In this paper, the structure feature of the inverse of a multi-input/multi-output square transfer function matrix is explored. Instead of complicated advanced mathematical tools, we only use basic results of complex analysis in the analysing procedure. By employing the Laurent expression, an elegant structure form of the expansion is obtained for the transfer function matrix inverse. This expansion form is the key of deriving an analytical solution to the inner–outer factorisation for both stable plants and unstable plants. Different from other computation algorithm, the obtained inner–outer factorisation is given in an analytical form. The solution is exact and without approximation. Numerical examples are provided to verify the correctness of the obtained results.     

Development of universal environment for constructing 5-axis virtual machine tool based on modified D–H notation and OpenGL

For construction of a universal 5-axis virtual machine simulation system, a new methodology is proposed in this paper. The OpenGL library is used to render the virtual environment and to display all motions of the virtual machine tool. In order to achieve the universal construction procedures, the D–H notation is adopted. The user interfaces are developed to help users to select the configuration of machine tool. Once the configuration is decided, the motion directions between adjacent links are known and the kinematic parameters are described by D–H notation. Then the post-processor is derived by D–H notation. Finally, the motion control simulation of the virtual machine tool is executed by D–H transformation matrix. This new methodology can assist developers in constructing the simulation system for the universal 5-axis virtual machine tool efficiently and effectively.     

Error estimates of the space–time spectral method for parabolic control problems

This work is devoted to investigate the spectral approximation of optimal control of parabolic problems. The space–time method is used to boost high-order accuracy by applying dual Petrov–Galerkin spectral scheme in time and spectral method in space. The optimality conditions are derived, and the a priori error estimates indicate the convergence of the proposed method. Numerical tests confirm the theoretical results, and show the efficiency of the method.     

A heterogeneous parallel implementation of the Markov clustering algorithm for large-scale biological networks on distributed CPU–GPU clusters

The Journal of Supercomputing - Biological interaction databases accommodate information about interacted proteins or genes. Clustering on the networks formed by the interaction information for...     

An analytic solution for the space–time fractional advection–dispersion equation using the optimal homotopy asymptotic method

We present an analytic algorithm to solve the space–time fractional advection–dispersion equation (FADE) based on the optimal homotopy asymptotic method (OHAM), which has the advantage of controlling the region and rate of convergence of the solution series via several auxiliary parameters over the traditional homotopy analysis method (HAM) having only one auxiliary parameter. Furthermore, our proposed algorithm gives better results compared to the Adomian decomposition method (ADM) and the homotopy perturbation method (HPM) in the sense that fewer iterations are required to get a sufficiently accurate solution and the solution has a greater radius of convergence. We find that the iterations obtained by the proposed method converge to the numerical/exact solution of the ADE as the fractional orders $\alpha ,\beta ,\gamma$ tend to their integral values. Numerical examples are given to illustrate the proposed algorithm. The figures and tables show the superiority of the OHAM over the HAM.     

An efficient hybrid learning algorithm for neural network–based speech recognition systems on FPGA chip

This paper implemented an artificial neural network (ANN) on a field programmable gate array (FPGA) chip for Mandarin speech measurement and recognition of nonspecific speaker. A three-layer hybrid learning algorithm (HLA), which combines genetic algorithm (GA) and steepest descent method, was proposed to fulfill a faster global search of optimal weights in ANN. Some other popular evolutionary algorithms, such as differential evolution, particle swarm optimization and improve GA, were compared to the proposed HLA. It can be seen that the proposed HLA algorithm outperforms the other algorithms. Finally, the designed system was implemented on an FPGA chip with an SOC architecture to measure and recognize the speech signals.     

An algorithm for the improvement of linear separation†

A method is presented for the improvement of linear separation. The characteristic vector is modified using the required distance of the boundary from the nearest pattern. Using this modified characteristic vector the weight vector is adjusted.     

An efficient numerical technique based on the extended cubic B-spline functions for solving time fractional Black–Scholes model

Financial theory could introduce a fractional differential equation (FDE) that presents new theoretical research concepts, methods and practical implementations. Due to the memory factor of fractional derivatives, physical pathways with storage and inherited properties can be best represented by FDEs. For that purpose, reliable and effective techniques are required for solving FDEs. Our objective is to generalize the collocation method for solving time fractional Black–Scholes European option pricing model using the extended cubic B-spline. The key feature of the strategy is that it turns these type of problems into a system of algebraic equations which can be appropriate for computer programming. This is not only streamlines the problems but speed up the computations as well. The Fourier stability and convergence analysis of the scheme are examined. A proposed numerical scheme having second-order accuracy via spatial direction is also constructed. The numerical and graphical results indicate that the suggested approach for the European option prices agree well with the analytical solutions.

     

Numerical algorithm for the standard pairing problem based on the Heine–Stieltjes correspondence and the polynomial approach

We present a detailed study of the computational complexity of a numerical algorithm based on the Heine–Stieltjes correspondence following the new approach we proposed recently for solving the Bethe ansatz (Gaudin–Richardson) equations of the standard pairing problem. For k$k$ pairs of valence nucleons in n$n$ non-degenerate single-particle energy levels, the approach utilizes that solutions of the Bethe ansatz equations can be obtained from two matrices of dimensions (k+1)×(k+1)$(k+1)\times (k+1)$ and (n−1)×(k+1)$(n-1)\times (k+1)$, which are associated with the extended Heine–Stieltjes and Van Vleck polynomials, respectively. Since the coefficients in these polynomials are free from divergence with variations in contrast to the original Bethe ansatz equations, the approach provides an efficient and systematic way to solve the problem. The method reduces to solving a system of k$k$ polynomial equations, which can be efficiently implemented by the fast Newton–Raphson algorithm with a Monte Carlo sampling procedure for the initial guesses. By extension, the present algorithm can also be used to solve a large class of Gaudin-type quantum many-body problems, including an efficient angular momentum projection method for multi-particle systems.