A parallel ETD algorithm for large-scale rate theory simulation

Rate theory (RT) is a commonly used method to simulate the evolution of material defects. A promising numerical method, exponential time difference (ETD), can reduce the stiff RT equations to explicit ordinary differential equations (ODEs). Previous implementations of ETD on the “Sunway TaihuLight” supercomputer suffer from high computation cost and poor parallel efficiency while solving a large amount of ODEs. This paper improves the algorithm with hybrid MPI+SIMD and additional instruction-level optimizations by taking advantage of the architecture of “Sunway TaihuLight”. The execution time of a single iteration is reduced by about 40%. Scaling from 64 to 4096 processes, the parallel efficiency of the new algorithm achieves 33.5% and 50.6% in strong and weak scalability, which corresponds to 21.4 and 32.4 in speedup, respectively.

     

A full multigrid method for the Steklov eigenvalue problem

ABSTRACT

This paper introduces a kind of parallel multigrid method for solving Steklov eigenvalue problem based on the multilevel correction method. Instead of the common costly way of directly solving the Steklov eigenvalue problem on some fine space, the new method contains some boundary value problems on a series of multilevel finite element spaces and some steps of solving Steklov eigenvalue problems on a very low dimensional space. The linear boundary value problems are solved by some multigrid iteration steps. We will prove that the computational work of this new scheme is truly optimal, the same as solving the corresponding linear boundary value problem. Besides, this multigrid scheme has a good scalability by using parallel computing technique. Some numerical experiments are presented to validate our theoretical analysis.     

Regression-based weight generation algorithm in neural network for solution of initial and boundary value problems

This paper introduces a new algorithm for solving ordinary differential equations (ODEs) with initial or boundary conditions. In our proposed method, the trial solution of differential equation has been used in the regression-based neural network (RBNN) model for single input and single output system. The artificial neural network (ANN) trial solution of ODE is written as sum of two terms, first one satisfies initial/boundary conditions and contains no adjustable parameters. The second part involves a RBNN model containing adjustable parameters. Network has been trained using the initial weights generated by the coefficients of regression fitting. We have used feed-forward neural network and error back propagation algorithm for minimizing error function. Proposed model has been tested for first, second and fourth-order ODEs. We also compare the results of proposed algorithm with the traditional ANN algorithm. The idea may very well be extended to other complicated differential equations.     

A Maple package to find first order differential invariants of 2ODEs via a Darboux approach

Here we present an implementation of a semi-algorithm to find elementary first order differential invariants (elementary first integrals) of a class of rational second order ordinary differential equations (rational 2ODEs). The algorithm was developed in Duarte and da Mota (2009)  [18]; it is based on a Darboux-type procedure, and it is an attempt to construct an analog (generalization) of the method built by Prelle and Singer (1983)  [6] for rational first order ordinary differential equations (rational 1ODEs). to deal, this time, with 2ODEs. The FiOrDi package presents a set of software routines in Maple for dealing with rational 2ODEs. The package presents commands permitting research investigations of some algebraic properties of the ODE that is being studied.     

Parallel adaptive wavefront algorithms solving Lyapunov equations for the Cholesky factor on message passing multiprocessors

The order of the matrices involved in several algebraic problems decreases during the solution process. In these cases, parallel algorithms which use adaptive solving block sizes offer better performance results than the ones obtained on parallel algorithms using traditional constant block sizes. Recently, new parallel wavefront algorithms solving the Lyapunov equations for the Cholesky factor using Hammarling's method on message passing multiprocessors systems have been designed. In this paper, new parallel adaptive versions of these parallel algorithms are described, and experimental results obtained on an SGI Power Challenge and a SUN UltraSparc cluster are presented. Copyright © 1999 John Wiley & Sons, Ltd.     

Numerical simulation for the two-dimensional and three-dimensional Riesz space fractional diffusion equations with delay and a nonlinear reaction term

ABSTRACT

In this research, we consider the alternating direction implicit method for solving the two-dimensional and three-dimensional Riesz space fractional diffusion equations with delay and a nonlinear reaction term. The corresponding theoretical results including stability and convergence are provided. Moreover, the convergence order of the proposed method is improved by using the Richardson extrapolation method. The numerical results are presented to show the robustness and effectiveness of the numerical method.     

The numerical solution of fractional differential equations using the Volterra integral equation method based on thin plate splines

Finding the approximate solution of differential equations, including non-integer order derivatives, is one of the most important problems in numerical fractional calculus. The main idea of the current paper is to obtain a numerical scheme for solving fractional differential equations of the second order. To handle the method, we first convert these types of differential equations to linear fractional Volterra integral equations of the second kind. Afterward, the solutions of the mentioned Volterra integral equations are estimated using the discrete collocation method together with thin plate splines as a type of free-shape parameter radial basis functions. Since the scheme does not need any background meshes, it can be recognized as a meshless method. The proposed approach has a simple and computationally attractive algorithm. Error analysis is also studied for the presented method. Finally, the reliability and efficiency of the new technique are tested over several fractional differential equations and obtained results confirm the theoretical error estimates.

     

A Nonlinear Multigrid Method for Total Variation Minimization from Image Restoration

Image restoration has been an active research topic and variational formulations are particularly effective in high quality recovery. Although there exist many modelling and theoretical results, available iterative solvers are not yet robust in solving such modeling equations. Recent attempts on developing optimisation multigrid methods have been based on first order conditions. Different from this idea, this paper proposes to use piecewise linear function spanned subspace correction to design a multilevel method for directly solving the total variation minimisation. Our method appears to be more robust than the primal-dual method (Chan et al., SIAM J. Sci. Comput. 20(6), 1964–1977, 1999) previously found reliable. Supporting numerical results are presented.     

PARALLEL PSEUDOSPECTRAL SOLUTION OF FINANCIAL PARTIAL DIFFERENTIAL EQUATIONS

Abstract

We apply the Pseudospectral method to two fundamental financial equations: the Black-Scholes equation and the Cox Ingersoil Ross model of the term structure of interest rates. The former is used to price a European Call Option and the latter to price a zero coupon bond. Chebyshev polynomials are used as the basis functions and Chebyshev collocation points for the space discretisation. The Crank-Nicolson scheme is used for the time differencing. We have developed a C++ program to solve general second order linear parabolic equations, A parallel quasi-minimal residual version of the Bi-Conjugate Gradient stabilised algorithm is applied to solve the linear system on the AP3000, a parallel computer. The regular space domain and the smooth solutions often encountered in finance suggest the suitability of using this higher order technique.     

Explicit semi-direct methods based on approximate inverse matrix techniques for solving boundary-value problems on parallel processors

Generalized approximate inverse matrix techniques and sparse Gauss-Jordan elimination procedures based on the concept of sparse product form of the inverse are introduced for calculating explicitly approximate inverses of large sparse unsymmetric (n × n) matrices. Explicit first and second order semi-direct methods in conjunction with the derived approximate inverse matrix techniques are presented for solving Parabolic and Elliptic difference equations on parallel processors. Application of the new methods on a 2D-model problem is discussed and numerical results are given.     

A Multigrid Method of the Second Kind for Solving Linear Systems of Odes Discretized by Continuous Runge-Kutta Methods

A Waveform Relaxation method as applied to a linear system of ODEs is the Picard iteration for a linear Volterra integral equation of the second kind ({\cal I} - {\cal K})y = b \eqno (1) called Waveform Relaxation second kind equation. A corresponding Waveform Relaxation Runge-Kutta method is the Picard iteration for a discretized version ({\cal I} - {\cal K}_l )y_l = b_l \eqno (2) of the integral equation (1), where y l is the continuous solution of the original linear system of ODE provided by the so called limit method. We consider a W-cycle multigrid method, with Picard iteration as smoothing step, for iteratively computing y l . This multigrid method belongs to the class of multigrid methods of the second kind as described in Hackbusch [3, chapter 16]. In the paper we prove that the truncation error after one iteration is of the same order of the discretization error y l @ y of the limit method and the truncation error after two iterations has order larger than the discretization error. Thus we can see the multigrid method as a new numerical method for solving the original linear system of ODE which provides, after one iteration, a continuous solution of the same order of the solution of the limit method, and after two iterations, a solution with asymptotically the same error of the solution of the limit method. On the other hand the computational cost of the multigrid method is considerably smaller than the limit method.     

A conservative flux for the continuous Galerkin method based on discontinuous enrichment

Abstract In this paper we develop techniques for computing elementwise conservative approximations of the flux on element boundaries for the continuous Galerkin method. The technique is based on computing a correction of the average normal flux on an edge or face. The correction is a jump in a piecewise constant or linear function. We derive a basic algorithm which is based on solving a global system of equations and a parallel algorithm based on solving local problems on stars. The methods work on meshes with different element types and hanging nodes. We prove existence, uniqueness, and optimal order error estimates. Lastly, we illustrate our results by a few numerical examples.     

Comparison of model reduction techniques for large mechanical systems

Model reduction is a necessary procedure for simulating large elastic systems, which are mostly modeled by the Finite Element Method (FEM). In order to reduce the system’s large dimension, various techniques have been developed during the last decades, many of which share some common characteristics (Guyan, Dynamic, CMS, IRS, SEREP). A fact remains that many reduction approaches do not succeed in reducing the system’s dimension without damaging the dynamical properties of the model. The mathematical field of control theory offers alternative reduction methods, which can be applied to second order Ordinary Differential Equations (ODEs), derived by the FE-discretization of large elastic Multi Body Systems (MBS), e.g., Krylov subspace method or balanced truncation. In this paper, some of these methods are applied to the elastic piston rod. The validity of the reduced models is checked by applying Modal Correlation Criteria (MCC), since only the eigenfrequency comparison is not sufficient. Diagonal Perturbation is proposed as an efficient method for iteratively solving ill-conditioned large sparse linear systems (A x=b, A: ill-conditioned) when direct methods fail due to memory capacity problems. This is the case of FE-discretized systems, when tolerance failure occurs during the discretization procedure.     

Unsupervised kernel least mean square algorithm for solving ordinary differential equations

In this paper a novel method is introduced based on the use of an unsupervised version of kernel least mean square (KLMS) algorithm for solving ordinary differential equations (ODEs). The algorithm is unsupervised because here no desired signal needs to be determined by user and the output of the model is generated by iterating the algorithm progressively. However, there are several new approaches in literature to solve ODEs but the new approach has more advantages such as simple implementation, fast convergence and also little error. Furthermore, it is also a KLMS with obvious characteristics. In this paper the ability of KLMS is used to estimate the answer of ODE. First a trial solution of ODE is written as a sum of two parts, the first part satisfies the initial condition and the second part is trained using the KLMS algorithm so as the trial solution solves the ODE. The accuracy of the method is illustrated by solving several problems. Also the sensitivity of the convergence is analyzed by changing the step size parameters and kernel functions. Finally, the proposed method is compared with neuro-fuzzy [21] approach.     

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.     

Parallel methods for ordinary differential equations

Remarkably few methods have been proposed for the parallel integration of ordinary differential equations (ODEs). In part this is because the problems do not have much natural parallelism (unless they are virtually uncoupled systems of equations, in which case the method is obvious). In part it is because the subproblems arising in the solution of ODEs (for example, the solution of linear equations) are the ones that have provided the challenges for parallelism. This paper surveys some of the methods that have been proposed, and suggests some additional methods that are suitable for special cases, such as linear problems. It then looks at the possible application of large-scale parallelism, particularly across the method. If efficiency is of no concern (that is, if there is an arbitrary number of proceessors) there are some ways in which the solution of stiff equations can be done more rapidly; in fact, a speed up from a parallel time of 0(N ²) to 0(logN) forN equations might be possible if communication time is ignored. This is obtained by trying to perform as much as possible of the matrix arithmetic associated with the solution of the linear equations at each step in advance of that step and in parallel with the integration of earlier steps.     

The parametric solution of underdetermined linear ODEs

The purpose of this paper is twofold. An immediate practical use of the presented algorithm is its applicability to the parametric solution of underdetermined linear ordinary differential equations (ODEs) with coefficients that are arbitrary analytic functions in the independent variable. A second conceptual aim is to present an algorithm that is in some sense dual to the fundamental Euclids algorithm, and thus an alternative to the special case of a Gröbner basis algorithm as it is used for solving linear ODE-systems. In the paper Euclids algorithm and the new “dual version” are compared and their complementary strengths are analysed on the task of solving underdetermined ODEs. An implementation of the described algorithm is interactively accessible under [7].     

A New Class Of Adams-Bashforth Schemes For Odes

We consider a new class of Adams-Bashforth schemes for solving first order differential equations. The method of collocation was used. In the process of the derivation, we observed that it is possible to obtain the discrete scheme from the continuous scheme by collocating at a given point. Also, it is noticed that the discrete solutions and continuous solution are the same at the grid points.     

Metaheuristic algorithms for approximate solution to ordinary differential equations of longitudinal fins having various profiles

Differential equations play a noticeable role in engineering, physics, economics, and other disciplines. Approximate approaches have been utilized when obtaining analytical (exact) solutions requires substantial computational effort and often is not an attainable task. Hence, the importance of approximation methods, particularly, metaheuristic algorithms are understood. In this paper, a novel approach is suggested for solving engineering ordinary differential equations (ODEs). With the aid of certain fundamental concepts of mathematics, Fourier series expansion, and metaheuristic methods, ODEs can be represented as an optimization problem. The target is to minimize the weighted residual function (error function) of the ODEs. The boundary and initial values of ODEs are considered as constraints for the optimization model. Generational distance and inverted generational distance metrics are used for evaluation and assessment of the approximate solutions versus the exact (numerical) solutions. Longitudinal fins having rectangular, trapezoidal, and concave parabolic profiles are considered as studied ODEs. The optimization task is carried out using three different optimizers, including the genetic algorithm, the particle swarm optimization, and the harmony search. The approximate solutions obtained are compared with the differential transformation method (DTM) and exact (numerical) solutions. The optimization results obtained show that the suggested approach can be successfully applied for approximate solving of engineering ODEs. Providing acceptable accuracy of the proposed technique is considered as its important advantage against other approximate methods and may be an alternative approach for approximate solving of ODEs.