Search

This paper is concerned with fast, parallel and numerically accurate pricing of two-asset American options under the Merton jump-diffusion model, which gives rise to a two-dimensional partial integro-differential complementarity problem (PIDCP) with a nonlocal two-dimensional integral term. Following method-of-lines approach, the solution to the PIDCP can be computed quite accurately by a robust numerical technique that combines Ikonen–Toivanen splitting with an alternating direction implicit scheme. However, we observed that computing the numerical solution with this technique becomes extremely time consuming, mainly due to the handling of the integral term. In this paper we parallelize this technique by applying a parallel fast Fourier transformation algorithm to all matrix-vector multiplications involving the huge and dense integral approximation matrix by exploiting its block Toeplitz with Toeplitz block structure. We also parallelize other computationally intensive steps of this technique by applying a recently developed parallel cyclic reduction algorithm for pentadiagonal systems. Our solutions computed on a graphics processing unit (GPU) using CUDA® platform are compared for accuracy with those available in the literature. It is observed that by solving the PIDCP parallelly we could bring down the computational times from several hours to a few seconds in certain cases in our experiments.

When written in MATLAB the finite element method (FEM) can be implemented quickly and with significantly fewer lines, when compared to compiled code. MATLAB is also an attractive environment for generating bespoke routines for scientific computation as it contains a library of easily accessible inbuilt functions, effective debugging tools and a simple syntax for generating scripts. However, there is a general view that MATLAB is too inefficient for the analysis of large problems. Here this preconception is challenged by detailing a vectorised and blocked algorithm for the global stiffness matrix computation of the symmetric interior penalty discontinuous Galerkin (SIPG) FEM. The major difference between the computation of the global stiffness matrix for SIPG and conventional continuous Galerkin approximations is the requirement to evaluate inter-element face terms, this significantly increases the computational effort. This paper focuses on the face integrals as they dominate the computation time and have not been addressed in the existing literature. Unlike existing optimised finite element algorithms available in the literature the paper makes use of only native MATLAB functionality and is compatible with GNU Octave. The algorithm is primarily described for 2D analysis for meshes with homogeneous element type and polynomial order. The same structure is also applied to, and results presented for, a 3D analysis. For problem sizes of 106 degrees of freedom (DOF), 2D computations of the local stiffness matrices were at least ≈24 times faster, with 13.7 times improvement from vectorisation and a further 1.8 times improvement from blocking. The speed up from blocking and vectorisation is dependent on the computer architecture, with the range of potential improvements shown for two architectures in this paper.

This paper describes iterative methods for the high frequency electromagnetic analysis using the finite element method of Maxwell equations including displacement current. The conjugate orthogonal conjugate gradient method has been widely used to solve a complex symmetric system. However, the conventional method suffers from oscillating convergence histories in large-scale analysis. In this paper, to solve large-scale complex symmetric systems arising from the formulation of the E method, an iterative substructuring method like the minimal residual method is presented, and the performance of the convergence of the method is evaluated by numerical results. As the result, the proposed method shows a stable convergence behavior and a fast convergence rate compared to other iterative methods.

Sensitivity analysis is an important issue in large-scale mathematical modelling. We developed a novel 3-stage method for global sensitivity analysis of the Unified Danish Eulerian Model (UNI-DEM). This is a powerful large-scale air pollution model with an up-to-date high-performance software implementation. There is a number of uncertain internal parameters, especially in the chemistry-emission submodel, which are subject to our quantitative sensitivity study. Efficient Monte Carlo and quasi-Monte Carlo algorithms based on Sobol sequences are used in this study.A large number of numerical experiments with some special modifications of the model must be carried out in order to collect the necessary input data for the particular sensitivity study. For this purpose we created an efficient high performance implementation SA-DEM, based on the MPI version of the package UNI-DEM. A vast number of numerical experiments were carried out with SA-DEM on an IBM Blue Gene/P, the most powerful parallel supercomputer, at the time of the write-up of this paper, in Bulgaria. Even this powerful machine has some problems with the storage when SA-DEM is to be run with the refined (480×480) version of the mesh. The code was implemented with some enhancements on the IBM MareNostrum III at BSC - Barcelona, the most powerful parallel supercomputer in Spain. This implementation appears to be quite efficient for that challenging computational problem, as our experiments show. Some numerical results and performance analysis of these results will be presented in the paper.

The paper presents a compact Matlab implementation of a finite element code performing dual analysis of heat conduction problems. After a short presentation of the concerned variational principles, the conductivity matrices of the dual models are developed explicitly. In the next step, a Matlab procedure is written. It shows in 66 statements how it is possible to perform the dual analysis using the unique formalism based on a global conductivity matrix. This fully general method allows using the same finite element code to run the dual analyses. After showing the convergence properties, a second application is developed in order to show how easily the code can be modified. The last part of the paper, addressed to skilled readers, provides useful comments on the heat problem formulation. The Matlab procedure is proposed as a free code for educational purposes and can be extracted directly from the document using the standard copy and paste function.

In this paper, by constructing an objective function and using the gradient search, full-rank and reduced-rank gradient-based algorithms are suggested for solving generalized coupled Sylvester matrix equations. It is proved that the reduced-rank iterative algorithm is convergent for proper initial iterative values. By analyzing the spectral radius of the related matrices, the convergence properties are studied and the optimal convergence factor of the reduced-rank algorithm is determined. The relationship between the reduced-rank algorithm and the full-rank algorithm is discussed. Consequently, the computation load can be reduced greatly for solving a class of matrix equation. A numerical example is provided to illustrate the effectiveness of the proposed algorithms and testify the conclusions suggested in this paper.

In this paper, a numerical analysis of two velocity-two pressure models for flows of solid particles and fluids is presented. First, a formal exploitation of the weak formulation of such models asserts that they are amenable to integration via projection methods. The challenging issues in the algorithm development for these models are then documented and suitable numerical methodologies for their remedy are devised. Subsequently, an algorithm for the integration of the models of interest is proposed. This is a two-phase projection method on collocated grids that utilizes a fractional-step time-marching scheme. It is further endowed with an interface detection-and-treatment methodology to properly account for the stiffness induced by the presence of moving and deforming material interfaces. The efficiency and robustness of the proposed numerical method are assessed in a series of numerical experiments that are delineated in the last part of this paper.

In the paper a procedure for solving the two-dimensional inverse Stefan problem is presented. In considered problem the heat transfer coefficient is identified with the aid of known measurements of temperature in selected points of the region as the additional information. Direct Stefan problem is solved by using the alternating phase truncation method. Goal of the paper is to compare two swarm intelligence algorithms-the Ant Colony Optimization algorithm and the Artificial Bee Colony algorithm-applied for minimizing a functional expressing the error of approximate solution.

For solving nonsymmetric linear systems, we attempt to establish symmetric structures in nonsymmetric systems and handle them through the methods devised for symmetric cases. A Biconjugate A-Orthogonal Residual method based on Biconjugate A-Orthonormalization Procedure has been proposed and nominated as BiCOR in [Y.-F. Jing, T.-Z. Huang, Y. Zhang, L. Li, G.-H. Cheng, Z.-G. Ren, Y. Duan, T. Sogabe, B. Carpentieri, Lanczos-type variants of the COCR method for complex nonsymmetric linear systems, J. Comput. Phys. 228 (2009) 6376-6394.]. As many similar characteristics exist between BiCOR and BiCG, the strategies of improved variants of BiCG, such as CGS and BiCGSTAB, can be utilized to enhance the algorithm for BiCOR. Making use of the product of residual polynomials of BiCOR and other polynomials, CORS and BiCORSTAB have been proposed along the same ideas of CGS and BiCGSTAB, respectively in the above-mentioned paper. In this paper, a unified generalized framework of product-type BiCOR, which is epitomized by the product of residual polynomials and other polynomials, is proposed. Numerical examples are selected from the blurring signal cases and the effect of the generalized product-type BiCOR method is prominent in signal deconvolution.

The paper deals with symbolic regression of deterministic chaos systems using a GPA-ES system. A Lorenz attractor, Rossler attractor, Rabinovich-Fabrikant equations and a van der Pol oscillator are used as examples of deterministic chaos systems to demonstrate significant differences in the efficiency of the symbolic regression of systems described by equations of similar complexity. Within the paper, the source of this behavior is identified in presence of structures which are hard to be discovered during the evolutionary process due to the low probability of their occurrence in the initial population and by the low chance to produce them by standard evolutionary operators given by small probability to form them in a single step and low fitness function magnitudes of inter-steps when GPA tries to form them in more steps. This low magnitude of fitness function for particular solutions tends to eliminate them, thus increasing the number of needed evolutionary steps. As the solution of identified problems, modification of terminals and related crossover and mutation operators are suggested.

In this paper, the utilization of chaos pseudorandom number generators based on three different chaotic maps to alter the behavior and overall performance of PSO algorithm is proposed. This paper presents results of testing the performance and behavior of the proposed algorithm on typical benchmark functions that represent unimodal and multimodal problems. The promising results are analyzed and discussed.

Quasi-Newton (QN) methods are generally held to be the most efficient minimization methods for solving unconstrained optimization problems. Among the QN methods, symmetric rank-one (SR1) is one of the very competitive formulas. In the present paper, we propose a new SR1 method. The new technique attempts to improve the quality of the SR1 Hessian by employing the scaling of the identity in a certain sense. However, since at some iterations these updates might be singular, indefinite or undefined, this paper proposes an updates criterion based on the eigenvalues of the SR1 update to measure this quality. Hence, the new method is employed only to improve the approximation of the SR1 Hessian. It is shown that the numerical results support the theoretical considerations for the usefulness of this criterion and show that the proposed method improves the performance of the SR1 update substantially.

Constrained matrix games with payoffs of triangular fuzzy numbers (TFNs) are a type of matrix games with payoffs expressed by TFNs and sets of players’ strategies which are constrained. So far as we know, no study have yet been attempted for constrained matrix games with payoffs of TFNs since there is no effective way to simultaneously incorporate the payoffs’ fuzziness and strategies’ constraints into classical and/or fuzzy matrix game methods. The aim of this paper is to develop an effective methodology for solving constrained matrix games with payoffs of TFNs. In this methodology, we introduce the concepts of Alpha-constrained matrix games for constrained matrix games with payoffs of TFNs and the values. By the duality theorem of linear programming, it is proven that players’ gain-floor and loss-ceiling always have a common interval-type value and hereby any Alpha-constrained matrix game has an interval-type value. Moreover, using the representation theorem for the fuzzy set, it is proven that any constrained matrix game with payoffs of TFNs always has a TFN-type fuzzy value. The auxiliary linear programming models are derived to compute the lower and upper bounds of the interval-type value and optimal strategies of players for any Alpha-constrained matrix game. In particular, the mean and the lower and upper limits of the TFN-type fuzzy value of any constrained matrix game with payoffs of TFNs can be directly obtained through solving the derived three linear programming models with data taken from only 1-cut and 0-cut of payoffs. Hereby the TFN-type fuzzy value of any constrained matrix game with payoffs of TFNs are easily computed. The proposed method in this paper is compared with other methods and its validity and applicability are illustrated with a numerical example.

This paper studies a group of basic state reduction based dynamic programming (DP) algorithms for the multi-objective 0–1 knapsack problem (MKP), which are related to the backward reduced-state DP space (BRDS) and forward reduced-state DP space (FRDS). The BRDS is widely ignored in the literature because it imposes disadvantage for the single objective knapsack problem (KP) in terms of memory requirements. The FRDS based DP algorithm in a general sense is related to state dominance checking, which can be time consuming for the MKP while it can be done efficiently for the KP. Consequently, no algorithm purely based on the FRDS with state dominance checking has ever been developed for the MKP. In this paper, we attempt to get some insights into the state reduction techniques efficient to the MKP. We first propose an FRDS based algorithm with a local state dominance checking for the MKP. Then we evaluate the relative advantage of the BRDS and FRDS based algorithms by analyzing their computational time and memory requirements for the MKP. Finally different combinations of the BRDS and FRDS based algorithms are developed on this basis. Numerical experiments based on the bi-objective KP instances are conducted to compare systematically between these algorithms and the recently developed BRDS based DP algorithm as well as the existing FRDS based DP algorithm without state dominance checking.

Uniform resampling is the easiest to apply and is a general recipe for all problems, but it may require a large replication size B. To save computational effort in uniform resampling, balanced bootstrap resampling is proposed to change the bootstrap resampling plan. This resampling plan is effective for approximating the center of the bootstrap distribution. Therefore, this paper applies it to neural model selection. Numerical experiments indicate that it is possible to considerably reduce the replication size B. Moreover, the efficiency of balanced bootstrap resampling is also discussed in this paper.

This paper introduces a new system of extended generalized nonlinear mixed quasi-variational inclusions involving A-maximal m-relaxed η-accretive (so called (A,η)-accretive (Lan et al. (2006) [37])) mappings in q-uniformly smooth Banach spaces. By using the resolvent operator technique for A-maximal m-relaxed η-accretive mappings due to Lan et al., we establish the existence and uniqueness of solution for this system of extended generalized nonlinear mixed quasi-variational inclusions and construct a new perturbed N-step iterative algorithm with mixed errors for solving the mentioned system. We also prove the convergence of the sequences generated by our algorithms in q-uniformly smooth Banach spaces. The results presented in this paper extend and improve some known results in the literature.

In this paper, we consider the problem of underdetermined blind source separation (UBSS), i.e., there are more sources than mixtures. By exploiting the time-frequency (TF) sparsity of the source signals, some TF-UBSS algorithms have recently been proposed in the literature. These algorithms require that the number of active sources at any TF point should not exceed one or be strictly less than the number of mixtures. In this paper, we show that if the number of sources is greater than the number of mixtures by one, the sparsity assumption can be further relaxed. Especially, it is allowed to have as many sources as mixtures at any TF point in this case. Then we propose a new TF-UBSS method to recover the sources. The relaxation on the maximum number of active sources at TF points ensures that the TF-based methods can be used in a wider range of applications.

The original exploiting modification direction (EMD) method proposed by Zhang and Wang is a novel data hiding technique which can achieve large embedding capacity with less distortion. The original EMD method can hide (2n+1)-ary numbers by modifying at most one least-significant bit (LSB) of n pixel values. The proposed methods in this paper, 2-EMD and EMD-2, modify at most two pixels of the LSB values. Efficiency of the proposed methods is shown theoretically and through experiments. The 2-EMD and EMD-2 can hide even larger numbers than the EMD with similar distortion under the same conditions. This paper shows that the EMD-2 is much better than the EMD, and slightly better than 2-EMD when n is 3, 4 and 5. The way to generate basis vector can be used for the generalization of the n-EMD and EMD-n where n>1.

In this paper, we propose an ordinal optimization (OO) theory-based algorithm to solve the yet to be explored distributed state estimation with continuous and discrete variables problems (DSECDP) of large distributed power systems. The proposed algorithm copes with a huge amount of computational complexity problem in large distributed systems and obtains a satisfactory solution with high probability based on the OO theory. There are two contributions made in this paper. First, we have developed an OO theory-based algorithm for DSECDP in a deregulated environment. Second, the proposed algorithm is implemented in a distributed power system to select a good enough discrete variable solution. We have tested the proposed algorithm for numerous examples on the IEEE 118-bus and 244-bus with four subsystems using a 4-PC network and compared the results with other competing approaches: Genetic Algorithm, Tabu Search, Ant Colony System and Simulated Annealing methods. The test results demonstrate the validity, robustness and excellent computational efficiency of the proposed algorithm in obtaining a good enough feasible solution.

In this paper we introduce and study a new system of nonlinear variational inclusions with (A,@h)-accretive mappings in Banach spaces. By using the resolvent operator associated with (A,@h)-accretive mappings, we construct some new iterative algorithms for approximating the solution of this system of variational inclusions. We also prove the existence of solutions and the convergence of the sequences generated by the algorithm in Banach spaces. The results presented in this paper extend and improve some known results in the literature.

This paper analyzes a discrete-time multiserver finite-buffer queueing system with batch renewal arrivals in which inter-batch time of batches and service times of customers are, respectively, arbitrarily and geometrically distributed. Each customer gets service from only one server. Using the supplementary variable and the imbedded Markov chain techniques, we obtain the state probabilities at prearrival, arbitrary and outside observer's observation epochs for partial- and total-batch rejection policies. The blocking probability of the first-, an arbitrary- and the last-customer in a batch, and other performance measures along with some numerical results have been discussed. The analysis of actual waiting-time distributions measured in slots of the first-, an arbitrary- and the last-customer in an accepted batch has also been investigated. Finally, it is shown that in the limiting case the results obtained in this paper tend to the continuous-time counterpart.

The aim of this paper is to establish the equivalence of convergence for H-monotone mappings of variational inclusions between the one-step iteration algorithm of the paper [Y.P. Fang, N.J. Huang, H-monotone opertor and resolvent operator technique for variational inclusions, Appl. Math. Comput. 145 (2003) 795-803] and the two-step iteration algorithm of the paper [L.C. Zeng, S.M. Guu, J.C. Yao, Characterization of H-monotone operators with applications to variational inclusions, Comput. Math. Appl. 50 (2005) 329-337]. It is clear from this paper that the one-step iteration algorithm with easy implement and small computational workload has more advantages than the two-step iteration algorithm.

In this paper, we introduce and study a new system of generalized nonlinear mixed quasi-variational inclusions in q-uniformly smooth Banach spaces. We prove the existence and uniqueness of solutions for this system of generalized nonlinear mixed quasi-variational inclusions. We also prove the convergence of several new two-step iterative algorithms with or without errors for this system of generalized nonlinear mixed quasi-variational inclusions. The results in this paper extend and improve some known results in the literature.

In this paper, we study a new kind of vector equilibrium problem and we proved the existence of solutions for this kind of equilibrium problem by using the section theorem and Fan KKM theorem. Then we generalize this kind of vector equilibrium problem to a more general case. Equilibrium problems with lower and upper bounds was an open problem proposed by Isac, Sehgal and Singh in 1999. J. Li, O. Chadli, Y. Chiang and J.C. Yao, Zhang Cong-jun derived some results of the equilibrium problems with lower and upper bounds under certain conditions. In this paper we derive more results of this open problem under certain conditions, constructs an iteration algorithm, and discuses the convergence of the algorithm.

When semiexplicit differential-algebraic equations are solved with implicit Runge-Kutta methods (RK), the computational effort is dominated by the cost of solving the nonlinear systems, and therefore it is important to have good starting values to begin the iterations. For semiexplicit index-2 DAEs, starting algorithms without additional cost for RK methods with regular matrix coefficient were studied in a previous paper. However, the regularity condition on the matrix coefficient excludes some interesting methods like Lobatto IIIa and ESDIRK methods. In this paper, we study starting algorithms, without additional computational cost, for a class of Runge-Kutta methods in the case of index-2 DAEs.

The problem of locating centers of graphs has a variety of applications in the areasof transportation and communication in distributed systems. In this paper, we design and prove the correctness of a self-stabilizing algorithm which finds the center(s) for a distributed system with a tree topology. The computational model employed in this paper was introduced by Dolev et al., which assumes the read/write separate atomicity.

This paper presents modelling and analysis of discrete-time multiserver finite-buffer queue with general interarrival and geometric service time. Using the supplementary variable technique, and considering the remaining interarrival time as a supplementary variable, two variants of this model, namely the late arrival system with delayed access (LAS-DA) and early arrival system (EAS), have been examined. For both the cases, steady-state system length distributions at arbitrary, prearrival, and outside observer's observation epochs have been obtained. Further, the waiting time distribution in the queue is also discussed. Various performance measures such as probability of loss, average number of busy servers and average waiting time in the queue etc. have been presented. It is hoped that the results obtained in this paper may provide useful information to designers of telecommunication systems, practitioners, and others.

The aim of this paper is to consider parallel iteration schemes for a general class of pseudo two-step Runge-Kutta-Nystrom (RKN) methods of arbitrary high order for solving nonstiff initial-value problems y″( t ) = f(y( t )), y( t 0 ) = y 0 , y′( t 0 ) = y 0 on parallel computers. Starting with an s -stage pseudo two-step RKN method of order p ∗ with w implicit stages, we apply the highly parallel PC iteration process in P ( EC ) m E mode. The resulting PIPTRKN method (parallel-iterated pseudo two-step RKN method) uses an optimal number of processors equal to w ≤ p ∗/2. By a number of numerical experiments, we show the superiority of the PIPTRKN methods proposed in this paper over both sequential and parallel methods available in the literature.

Based on two-grid discretization and domain decomposition approach, this paper presents and studies two local and parallel finite element algorithms for the 2D/3D steady Stokes equations with nonlinear damping term. Starting point of the algorithms is that for a solution of the Stokes equations with damping, we first approximate the low-frequency component on a relatively coarse grid, and then compute the high-frequency component on a locally fine grid via some local and parallel procedures. The proposed algorithms are easy to implement and have low communication complexity. With the use of the technical tool of local a priori estimate for finite element solution, we derive error estimates of the approximate solutions from the proposed algorithms. Some numerical results are provided to test the validity of the present algorithms.

In this paper, we design a self-stabilizing algorithm which finds a 2-center for a distributed system with a tree topology. Our algorithm is based on the algorithm in [1–3]. The latter enables us to find the center (or centers) for the tree. If we sever the tree at the center (or centers), we obtain two subtrees. One of the major works in this paper is to show that if we pick a center from each subtree, the two picked centers will constitute a 2-center for the original tree. With this in mind, we design our algorithm so that it is equipped with the ability of “sensing” the two subtrees and then finding a center in each of them.

Terminal-pair reliability (TR) in network management determines the probabilistic reliability between two nodes (the source and sink) of a network, given failure probabilities of all links. It has been shown that TR can be effectively computed by means of the network reduction technique. Existing reduction axioms, unfortunately, are limited to trivial rules such as valueless link removal and series-parallel link reduction. In this paper, we propose a novel reduction axiom, referred to as triangle reduction . The triangle reduction axiom transforms a graph containing a triangle subgraph to that excluding the base of the triangle. The computational complexity of the transformation is as low as O (1). With triangle reduction, the number of subproblems generated by partition-based TR algorithms, for simplified grid networks, can be reduced to O(( (1 + √5) 2 ) n ) . The paper further provides an assessment of the effectiveness of triangle reduction on partition-based TR algorithms with respect to the number of subproblems and computation time through experimenting on published benchmarks and random networks. Experimental results demonstrate that, incorporating triangle reduction, the path-based (cut-based) partition TR algorithm yields a substantially reduced number of subproblems and computation time for all (most of the) benchmarks and random networks.

The aim of this paper is to investigate a general class of explicit pseudo two-step Runge-Kutta-Nystrom methods (RKN methods) of arbitrarily high order for nonstiff problems for systems of special second-order differential equations y″( t ) = f(y( t )). Order and stability considerations show that we can obtain for any given p , a stable p th -order explicit pseudo two-step RKN method requiring p − 2 right-hand side evaluations per step of which each evaluation can be obtained in parallel. Consequently, on a multiprocessor computer, only one sequential right-hand side evaluation per step is required. By a few widely-used test problems, we show the superiority of the methods considered in this paper over both sequential and parallel methods available in the literature.

Protocol testing leads to the synchronization problem should test sequences be applied to multiple distanced testers, namely under the multiparty configuration. This paper presents a novel synchronization paradigm which seamlessly unifies two synchronization techniques, self-synchroniable sequences and external synchronization operations, by means of the state expansion transformation . In the paradigm, the protocol specification is first transformed into a state expansion digraph with two pieces of datum augmented. They are: 1. (a) a zero cost assigned to each synchronization-problem-free crossing from one transition to another transition, and 2. (b) a weighted cost assigned to each external synchronization operation whenever the synchronization is deemed necessary. On the basis of the state expansion transformation, synchronizable, optimal sequences for testing can be efficiently derived. To demonstrate the viability of the proposed paradigm, we present the generations of two synchronizable sequences, namely the synchronizable preamble and the synchronizable distinguishing sequence, which have previously been used for the testing of the correctness of a protocol's transition. The paper also shows that the complexities of the two sequences generations are also polynomial-bounded, i.e., O (( np 2 ) log( np )) and O (( n 2 p 2 ) log( np )), respectively, where n and p are the numbers of states and input symbols of the protocol specification.

In this paper, a second-order local and parallel space-time algorithm is proposed and analyzed for the heat equation. This scheme is based on the parareal with spectral deferred correction method in time and the expandable local and parallel finite element method in space. It realizes the parallelism both in the temporal as well as in the spatial direction. We prove its stability and the optimal error estimation in L 2 -norm. At last, several numerical experiments are presented to demonstrate the effectiveness of our parallel scheme.

For facilitating images under nonlinear transformations, the splitting-shooting method, the splitting-integrating method, and their combinations are presented in [1], which do not require nonlinear solutions, but have the low convergence rate O( 1 N ) of sequential pixel (or voxel) greyness, where N is the division number to split a 3D image voxel into N3 subvoxels. In this paper, new partition techniques of 3D subregions are proposed to evaluate carefully overlaps between a cube and the distorted subvoxel region and then applied to the splitting-shooting method, the splitting-integrating method, and their combinations. Error analysis is made to prove that the convergence rate O( 1 N 2 ) can be achieved, and numerical experiments are carried out to confirm the theoretical analysis mode. A remarkable advantage of the new discrete techniques is that no solutions of nonlinear equations are required either. The discrete techniques in this paper are well suited not only to solid objects but also to surfaces and curves in three dimensions, thus to benefit the study in many topics in computer science, such as computer vision, image processing, and pattern recognition.

In 1984, Gaffney [1] carried out a survey of codes for the numerical solution of the stiff oscillatory problem. This was prompted by a desire to derive an efficient method of lines algorithm for the reduced resistive MHD equations. His main conclusion was that none of the codes available at that time was entirely satisfactory for dealing with this problem. In the present paper, we outline the considerable progress that has been made since Gaffney's survey and show that there now exist much more satisfactory codes for dealing with these problems. Two of the three FORTRAN codes that we recommend are both freely available from NETLIB, as well as from certain web pages, and so it is straightforward to reproduce all the numerical results given in the present paper.

In the past, Cellular Automata based models and machines [1] have been proposed for simulation of physical systems without any analytical insight into the behaviour of the underlying simulation machine. This paper makes a significant departure from this traditional approach. An elegant mathematical model using simple matrix algebra is reported in this paper for characterizing the behaviour of two-dimensional nearest neighbourhood linear cellular automata with null and periodic boundary conditions. Based on this mathematical model, a VLSI architecture of a Cellular Automata Machine (CAM) has been proposed. Interesting applications of CAM in the fields of image analysis and fractal image generation are also reported.

The aim of this paper is to design a class of two-step Runge-Kutta-Nystrom methods of arbitrarily high order for the special second-order equation y″(t) = f(y(t)), for use on parallel computers. Starting with an s-stage implicit two-step Runge-Kutta-Nystrom method of order p with k = p 2 implicit stages, we apply the highly parallel predictor-corrector iteration process in P(EC)mE mode. In this way, we obtain an explicit two-step Runge-Kutta-Nystrom method that has order p for all m and that requires k(m + 1) right-hand side evaluations per step of which each k evaluation can be computed in parallel. By a number of numerical experiments, we show the superiority of the parallel predictor-corrector methods proposed in this paper over both sequential and parallel methods available in the literature.

For the parallel integration of stiff initial value problems, three types of parallelism can be employed: “parallelism across the problem,” “parallelism across the method” and “parallelism across the steps.” Recently, methods based on Runge-Kutta schemes that use parallelism across the method have been proposed in [1,2]. These methods solve implicit Runge-Kutta schemes by means of the so-called diagonally iteration scheme and are called PDIRK methods. The experiments described in [1], show that the speedup factor of certain high-order PDIRK methods, is about 2 with respect to a good sequential code. However, a disadvantage of the high-order PDIRK methods is, that a relatively large number of iterations is needed for each step. This disadvantage can be compensated by employing step-parallelism. Step-parallel methods are methods in which a number of steps are treated simultaneously. This form of parallelism can be applied to any predictor-corrector method. A common feature of this approach is their poor convergence behaviour, unless the various strategies are carefully designed. In this paper, we describe two strategies for the PDIRK across the steps method. Example problems tested in this paper show for the best strategy, a speed-up factor ranging from 4 to 7 with respect to the best sequential codes.