Abstract: This review study gives a widespread overview of the solutions of several engineering problems based on some multidimensional partial differential equations like parabolic, hyperbolic, elliptic, AGE, IADE equations. Different analytical methods of treatment as well as those of numerical methods are presented in this paper. Finally, some evaluation phases of several experiments in order to solve some current engineering problems and recommendations are demonstrated.
INTRODUCTION
Many researchers have taken interests in developing finite difference methods that could approximate the solution of a one dimensional parabolic diffusion equation. Classical methods, however, have their own restrictions. Explicit methods are simple but generally suffer the disadvantage of conditional stability and low accuracy. Implicit methods, on the other hand, may possess unconditional stability and higher accuracy. Their features, however, are less amenable to parallelism (Smith, 1978).
Over the years, many highly refined iterative and alternating schemes have been developed, in which many of them not only exhibit superior properties in terms of stability, accuracy and rate of convergence, but they are also suitable for parallel computing. One of the schemes which have been cited often is the Alternating Group Explicit (AGE) method introduced by Evans and Sahimi (1989c). It employs the fractional splitting strategy applied alternately at intermediate time step on tridiagonal systems of the difference scheme. The approach, which is second-order accurate in both time and space, has been found to be stable, convergent and parallelizable.
Based on the AGE method, many new alternating schemes have been developed. Baolina and Wenzhib (1994) presented the Alternating Segment Crank-Nicolson method for the diffusion equation. The method is unconditionally stable and has the obvious property of parallelism. Zhu and Zhao (2007) designed a set of New Alternating Segment Explicit-Implicit (NASEI) schemes that alternate between explicit and implicit segments at any two consecutive time levels. The schemes are proven to be stable under reasonable conditions, have truncation errors of third order in space and capable of parallel computation. Zhen et al. (1994) developed a class of Hopscotch algorithms for the finite difference solution of the diffusion equation under consideration. The algorithm is convergent and efficient with regards to parallel computing. Feng (2009) presented a class of alternating group explicit iterative parallel method (AGI) by using an unconditionally stable symmetry six-point implicit scheme of high accuracy. Zhu et al. (2004) designed an explicit implicit scheme for parabolic equations with discontinuous coefficients. The method is intrinsically parallel. Baolina (1991) developed a class of alternating schemes in three time levels, which are the unconditionally stable AGE and the ASE-I (alternating segment explicit-implicit) methods. In the design of these two methods, Saul’yev asymmetric schemes (Saul’yev, 1964) have been used. Tavakoli and Davami (2006) applied a method which is based on domain decomposition concept and used the asymmetric Saul’yev schemes for internal nodes of each sub-domain and alternating group explicit method for sub-domain’s interfacial nodes. The approach is fully explicit, unconditionally stable and has merit in terms of accuracy.
Sahimi et al. (1993, 2001) proposed an alternative to the AGE method, which is the Iterative Alternating Decomposition Explicit (IADE) method. To approximate the solution of the diffusion equation, the IADE scheme employs the fractional splitting of either the Mitchell Fairweather (IADE-MF) variant (Mitchell and Fairweather, 1964) or the D’Yakonov (IADE-DY) variant (D’Yakonov, 1963) for a fixed acceleration parameter r>0 . Each variant is second-order accurate in time and fourth-order accurate in space. By analyzing the results of some numerical experiments based on the chosen variant for the IADE method, Sahimi et al. (2001) concluded that the two-stage IADE procedure has merit as an alternative iterative method with respect to stability, accuracy and rate of convergence. As the method is fully explicit, its feature can be fully utilized for parallelization.
The finite difference method is a well-established and conceptually simple method that requires a point-wise approximation to the governing equations. While the finite volume method is a further refined version of the finite differences method and has become popular in computational fluid dynamics. The vertex-centered finite volume technique is very similar to the linear finite element method (Lewis et al., 2004). The basis concept of the finite element method is that any solution domain can be divided into several simple subdomains known as finite elements. Thus, the approximate solution of the problem in the complete domain can be determined by assuming a simple form of solution in each finite element (Rao, 2002; Gutpa and Meek, 2003).
In Alias et al. (2009a), they focused on the application of this method in solving the initial stages of crack propagation problem which means the deformation due to the stress and strain of a material. Propagation problems refer to time-dependent, transient and unsteady-state phenomenon. The method was applied to evaluate the stress intensity factors for plates of arbitrary shape using conventional finite elements (Cheung et al., 1996). Fracture mechanics (Bui, 2006) was used to investigate the failure of brittle materials, which was to study material behavior and design against brittle failure and fatigue. The engineering study of fracture mechanics (Stanley, 1977) does not emphasize how a crack is initiated; the goal is to develop methods of predicting how a crack propagates.
In Alias et al. (2010a), the researchers discussed the solution of two dimensional Partial Differential Equations (PDEs) using some parallel numerical methods namely Gauss Seidel and Red Black Gauss Seidel. The selected two-dimensional PDEs in order to solve the problem were parabolic and elliptic type. Parallel Virtual Machine (PVM) is used in support of the communication among all microprocessors of Parallel Computing System.
It is abundantly clear that many important scientific problems are governed by partial differential equations according to Alias et al. (2009a). The difficulty in obtaining exact solution arises from the governing partial differential equations and the complexities of the geometrical configuration of physical problems (Alias et al., 2003a, b, 2008a, b). For example, imagine a metal rod insulated along its length with no heat can escape for its surface. If the temperature along the rod is not constant, then heat conduction takes place. In such situations, the numerical method is used to obtain the numerical solutions (Smith, 1965). These partial differential equations may have boundary value problems as well as initial value problems. In general, the transient particle diffusion or heat conduction is Partial Differential Equations (PDE) of the parabolic type and Laplace’s equation for temperature, diffusion, electrostatic conduction is elliptic and wave equation or transport equation is the PDE of hyperbolic type (Alias et al., 2008a, 2009b; Evans, 1995). The parabolic partial differential equations are normally used in such fields like molecular diffusion, heat transfer, nuclear reactor analysis and fluid flow (Nakamura, 1993; Smith, 1985).
In Alias et al. (2009b), New Iterative Alternating Group Explicit (NAGE) was introduced which is a powerful parallel numerical algorithm for multidimensional temperature prediction. The discretization was based on finite difference method of Partial Differential Equation (PDE) with parabolic type. The critical 3-Dimensional temperature visualization involves large scale of computational complexity. This computational challenge inspired the authors to utilize the power of advanced high performance computing resources.
Incomplete blow-up is a condition under the quasilinear heat equation (Alias et al., 2010b). The Porous Medium Equation (PME) with power source are admitting incomplete blow-up. It is used as one of the filtration process in the industry. Authors proposed a new variance of the Alternating Group Explicit Scheme (AGE) algorithms to solve incomplete blow-up problem through High Performance Computing (HPC).
Mizoguchi (2005) presented multiple blow-ups to solve a semilinear heat equation problem. Natalini et al. (1996) presented an incomplete blowup of entropy solutions to first-order quasilinear hyperbolic balance laws. They specified a general procedure to continue solutions beyond the blowup time, which made use of monotonicity methods. The continuations thus obtained were possibly unbounded and satisfied suitable generalized entropy and Rankine-Hugoniot conditions. Then they proved the uniqueness of continuations satisfying such conditions as well. Arrieta and Bernal (2004) showed that blow-up occurred only on the boundary while they analyzed the existence of solutions that blow-up in finite time for a reaction-diffusion equation. Mizoguchi and Vazquez (2007) demonstrated multiple blow-ups for semilinear heat equations at different places and different times and also solutions for a semilinear heat equations II described by Mizoguchi (2006). Nonlinear Volterra integral equations of the second kind with solutions that blow-up or quench had analyzed by Roberts (2007).
SOME PROBLEM DEFINITIONS IN BRIEF
Here, some engineering and bioscience problems are explained briefly which were focused to solve through partial differential equations in many studies by the researchers:
Thermal control process on PCB: In the context of thermal control system design, there are two major design approaches, that is, the system is either passive or active controlled. When there is a need to deal with more sophisticated system which requires high performance temperature controlling, the active thermal control system design is better suited. In electronic engineering, complex semiconductor devices are subjected to a number of tests during the manufacturing process to determine device functionality and to insure future reliability. The first test is usually at the wafer level. During this test the individual die on the wafer are probed to determine die integrity and die parametric properties. This quick test allows rejection of bad die and sorting of die for further testing (Gardell, 1995). Then, burn-in test will follow after the wafer level. The test thermally and electrically stresses the parts to accelerate early life, or infant mortality, failures. The device junction temperatures are typically held between 100 to 140°C to accelerate stress. Because the parts are also subjected to higher than normal voltages, the power dissipation levels can be very high, significantly higher than in normal operation (Tustaniwskyj and Babcock, 2004). So, Ghaffar et al. (2008) just focused on this part, where the problem under consideration is peak junction temperature of semiconductor devices estimation.
Brain tumor growth: A brain tumor is a growth of abnormal cells or normal cells in an inappropriate place in the brain. A primary brain tumor is one that starts in the brain, rather than cancer in another part of the body that has spread to the brain. Primary tumors can be grouped into non-cancerous (benign) and cancerous (malignant). Malignant brain tumors are commonly called brain cancer and they are usually invasive and life-threatening. Brain tumors also may be metastatic or secondary brain tumors. These tumors are formed from cancer cells that begin growing elsewhere in the body and travel to the brain, usually through the bloodstream. The study of (Alias et al., 2009b) was to visualize or capture the growth of brain tumor in three-dimensional space and to develop or identify the three-dimensional brain tumor growth. The aim was to identify the discretization of the mathematical models which will be converted to standard form and to implement the algorithm to perform the iterative methods from the discretization of the mathematical model. Angelis and Preziosi (2000) described the evolution of tumor in vivo and related to the boundary problem.
Breast cancer growth: Breast cancer is the most general disease among women, except for non-melanoma skin cancers. Due to early detection and increased awareness, resulting deaths have been decreasing recently. The second leading reason of cancer death in women is breast cancer. The possibility that breast cancer will be responsible for a woman’s death is about 1 in 33. Early detection is the key to successful treatment. Alternative methods for tumor recognition have been researched to couple with Thermal Simulation (Gonzalez, 2007), Microwave Imaging system through Space Time beamformer (Bond et al., 2003; Gunnarsson, 2007) and 2D Finite-Difference Time Domain (FDTD). So, the mathematical modeling could be advantage solutions in terms of insights and predictions. The research of the Alias et al. (2009b) focused on the study of elliptic equations, particularly Helmholtz’s wave equation and hyperbolic equations to monitor or predict the cancer cell growth through computational modeling.
Temperature behavior of rubber materials: Heat transfer process occurs due to the polymer flow as convection. The motion of fluid transfers an energy along its flow path and thus convects heat during mould filling (Davis et al., 2003). To predict the temperature behavior on rubber material involving phase change processes, this prediction solving by the mathematical simulation. A mathematical model was presented for the prediction of temperature profiles and heat transfer rates during the blow moulding process (Edwards et al., 1981). Darwis et al. (2009) focused on the research to study the influence of operating conditions on cooling time. The experimental attention to be focused on to using a chilled mould and gas circulation to give enhanced cooling rates. Analytical data obtained on a small laboratory at Lembaga Getah Malaysia as an exact solution and limited to testing on an industrial production line for the manufacturing of large barrels have been confirmed the validity of theoretical approach.
Food drying for preservation: It is very necessary to dry the tropical fruits to a certain level after harvest. Drying processes are widely used in food production especially fruits, but a scientific approach has not so widely been applied, so rather empiric rules are often used to set up industrial production, particularly in small-medium firms. The main objective of food drying process is water removal up to particular moisture content in order to prevent food from microbial spoilage and deterioration reactions and to increase the product shelf life (Curcio, 2006). Drying is a process involving simultaneous heat and mass transfer phenomena. Formulation of adequate mathematical models to describe the transfer phenomena during dehydration fruit is very important to optimize the process-leading in improvement product quality and reduction process cost. Simulation results and information of drying kinetics of fruit material such as time-temperature-moisture content distributions, as well as theoretical approaches to moisture movement, is very essential for the prevention of quality degradation and for the achievement of fast and effective drying. Such information will be very useful to optimize production processes of tropical fruits dried. Hence, the authors’ contribution of the study (Alias et al., 2009b) is successful modified the mathematical simulation in representing the actual process of dehydration in commercial foodstuff industry in terms of heat and mass transfer inside tropical fruits material.
PARTIAL DIFFERENTIAL EQUATIONS TOWARD SOLUTIONS
Numerical methods/Parallel algorithms are utilized for solving large sparse problems which are based on domain decomposition methods. They are straight forward parallel implementation with fine grain approaches and highly convergent and accurate and also, well suited to implement on distributed, shared and hybrid memory architecture. Numerical methods/Parallel algorithms can able to solve grand challenge application for multidimensional problem. Here, the most implemented partial differential equations are elucidated which lead to solve many engineering problems as those presented in the previous section. In this review study, it can be seen that multi-dimensional partial differential equation had been considered for the application of numerical methods in several studies.
One- dimensional parabolic equation: Equation 1 shows the one-dimensional parabolic equation.
| (1) |
subject to initial condition,
and boundary condition
The finite difference discretization of Eq. 1 results in
Two-dimensional parabolic equation:
| (2) |
this is subject to the initial condition,
and U(x, y, t) subject to the boundary Ω which is ∂R with condition
The region R is a rectangle defines by:
The finite difference discretization of Eq. 2 results in,
Three-dimensional parabolic equation: Equation 3 shows the three dimensional parabolic equation:
| (3) |
which subject to the initial condition below
Additionally, U(x, y, z, t) is subject to boundary Ω which is ∂R with boundary condition,
and the discretization of Eq. 3 is as follows:
Formulation of IADE and AGE families
IADE methods: Six strategies of parallel algorithms are implemented to exploit
the convergence of IADE (Alias et al., 2003a;
Evans and Sahimi, 1989a, b).
In the domain decomposition strategy the IADE Michell-Fairweather which is fully
explicit is derived to produce the approximation of grid-i and not totally dependent
on the grid (i-1) and (i+1). In IADE Red Black and IADE SOR strategies, the
domain is decomposed into two different subdomains. The concept of multidomain
is observed in the IADE Multicoloring method. The decomposition of domain split
into several different groups of domain. On the vector iteration strategy, parallel
IADE is run in two sections (Alias et al., 2003a;
Hageman and Young, 1981). This method converges if the
inner convergence criterion is achieved for each section.
The objectives of the parallel algorithms are to minimize the communication cost and computational complexity (Fig. 1a, b).
The sequential algorithm for IADE shown that the approximation solution for grid ui is depend on ui-1 and the approximation solution for um+1–i is depend on um+2–i. To avoid dependently situation, some parallel strategies is developed to create the non-overlapping subdomains.
IADE-New: On the strategy of incomplete block LU preconditioners on slightly non-overlapping subdomains, the domain is decomposed into p processors with incomplete subdomain (Alias et al., 2003a). This strategy implemented the incomplete factorization with parameter of algebraic boundary condition as follows,
| • | At time level k+1/2 |
| (4) |
| • | At time level k+1 |
| (5) |
Alternating Group Explicit(AGE) method: Based on the Douglas-Rachford formula (Evans and Sahimi, 1989a, b), the AGE fractional scheme involves the splitting of matrix A from system of linear equations Au = f (Alias et al., 2003a, b). A is split into the sum of its constituent symmetric and positive definite matrices G1, G2, G3, where,
and
| Fig. 1: | (a, b) IADE Algorithm to minimize the communication cost and computational complexity |
with diag(G1+G2) = diag(G3+G4) = 1/2diag(A).
The AGE fractional scheme is based on four intermediate levels, (k+1/4), (k+1/2), (k+3/4) and (k+1). Using explicit (2x2) blocks for matrices (G1+G2) and (G3+G4), we have a group of (2x2) block systems which can be made explicit as follows:
AGE BRIAN method: BRIAN method is based on the AGE algorithm with Douglas- Rachford variant and linear interpolation (BRIAN) concepts using the fractional strategy (Douglas et al., 2003; Evans and Sahimi, 1988). BRIAN algorithm (Alias et al., 2003b) has been developed as an alternative to the parallel and sequential algorithm of DOUGLAS method (Evans and Sahimi, 1989b). The formula for BRIAN method for 2-dimensional problem leads to five intermediate levels is as follows:
| (6) |
and with linear interpolation, we obtain,
AGE DOUGLAS algorithms: DOUGLAS Algorithms is based on the Douglas-Rachford formula for AGE fractional scheme (Sahimi and Muda, 1989) takes the form:
| (7) |
where, A is the sum of its constituent symmetric and positive define matrices G1, G2, G3 and G4,
Parabolic equation:
| (8) |
where, a<0, c≥0 and b2–4ac = 0. The PDE is said to be parabolic if det(Z) = 0. The heat conduction equation and other diffusion equation are examples. The heat equation is:
where, K is a constant. Initial-boundary conditions are used to give.
where ux x = f (ux, uy, u, x, y) holds in Ω.
Hyperbolic equation:
| (9) |
where, b2–4ac>0. The PDE is said to be hyperbolic if det(Z)<0. The wave equation is an example of a hyperbolic partial differential equation. The wave equation is:
where, β is a constant. Initial-boundary conditions are used to give:
u (x, y, t) = g(x, y, t) for x ∈ ∂ Ω,
t >0
u (x, y, 0) = v0 (x, y) in Ω
ut (x, y, 0) = v1 (x, y) in Ω |
where, ux y = f (ux, ut, x, y) holds in Ω.
Elliptic equation:
| (10) |
where, b2–4ac > 0. The PDE is said to be elliptic if Z is
a positive definite matrix with det(Z) = 0. Laplace’s equation and Poisson’s
equation are examples. The Laplace’s equation is:
EVALUATION PHASES OF EXPERIMENTAL SOLUTIONS
Partial differential equations occur from a variety of physical and engineering problems and assume a huge diversity of forms. Normally these forms are very complex, with nonlinearities, variable coefficients, high dimensionality, coupled equations of mixed type and irregular boundaries. Numerous constructive algorithms have been developed for solving these problems; nevertheless, the time and space complexities high and the class of problems to which all applies are limited. It has been seen in the previous sections that there exist some necessary conditions such that partial differential equations can be applied for solving those problems. Below are some phases that were implemented in order to evaluate the efficiency of those parallel experiments.
There are a master task and a number of worker tasks in the PVM implementation of the modeling codes. Master task is responsible to divide the model domain into sub domains and distribute them to worker tasks. Then, the worker tasks perform time marching and communicate after each time step. Time execution, speedup, efficiency, effectiveness and temporal performance were analyzed by looking at the performance of the parallel algorithm (Islam and Alias, 2010a, b).
Increasing number of processors significantly reduces the ratio but all the methods that experimentally performed, represent the ability in maintaining the condition where time for computation is always more than time consumed for communication. This reflects the beneficial ability of the blends of methods used with parallel algorithm that had been developed (Sahimi et al., 1993; Foster, 1995). As more problems need to be solved, each method results in higher time consumed for computation rather than communication. The ratio between computation and communication is known as granularity. High granularity reflects that computational cost dominating the overall execution time. However, too high granularity will lead to loss parallelism characteristics where the algorithm developed involved large size of data passing between processors. Thus, best combination of parallel algorithm and method being used will lead to better parallel performance evaluation where there is balance between computation and communication cost.
The following definitions are used to measure the parallel strategies, speed up, efficiency, effectiveness and temporal performance. Where T1 is the execution time on one processor, Tp is the execution time on p processors and the unit of Lp is work done per micro second.
| (11) |
| (12) |
| (13) |
| (14) |
The execution time: Execution time is the amount of time needed for a complete run of a computer program routine. The time required for a computer to decode and perform a compiled instruction.
The Speedup: The Amdahl’s law states that the speed of a program is the time to execute the program while speedup is defined as the time it takes to complete an algorithm with one processor divided by the time it takes to complete the same algorithm with N processors. The formula of speedup for a parallel application is given:
| Time (1) | = | Execution time for a single processor and |
| Time (p) | = | Execution time using p parallel processors |
The efficiency: The efficiency of a parallel program is a measure of processor utilization. Efficiency is defined as the speed-up with N processors divided by the number of processors N. An efficiency of 100% means that all of the processors are being fully used all the time.
| p | = | No. of processors |
The effectiveness: Effectiveness is used to calculate the speedup and the efficiency. The effectiveness is:
| p | = | No. of processors |
| Time(t) | = | Execution time using p parallel processors |
The temporal performance: Temporal performance is a parameter to measure the performance of a parallel algorithm which is:
| Time (t) | = | Execution time using p parallel processors |
Computation time and communication time ratio: Parallel execution time, tpara is divided into two parts, computational time, tcomp and communication time, tcomm. The tcomp is the time to compute the arithmetic operations such as multiplication and addition operations in the parallel algorithm. As all the processors doing the operation at the same speed, calculation for the tcomm is depending upon for the size of the message. The cost of communication comes from the two major phases in sending a message: the start-up phase and the data transmission phase (Becker et al., 2003). The total time to send K units of data for a given system can be written as:
| (15) |
where, tcomm is time needed to communicate a message of K bytes, tstartup is sometimes referred as the network latency time. Tstartup is also referred to time to send a message with no data. It includes time to pack the message at source and unpack the message at the destination and to start a point-to-point communication.
The tdata is time to transmit units of information. It is also the transmission time to send one bytes of data. The tstartup and tdata are assumed as constants and measured in bits sec-1. Tidle is the time for message latency and time to wait for all the processors to complete the works. The evaluation of these communication costs via simple codes that time the send/recv messages.
The research focus on,
tpara = Time for parallel execution
tcomm1 = αtdata + βtstartup
|
Where:
α and β dependents on m and L.
Here, tcomm1 is the Communication time 1 which is obtained from the subtraction of idle time from communication time.
Communication cost for parallel processing is,
| (16) |
| m | = | Units of data that sending across processor |
| L | = | No. of step overall the execution |
Granularity analysis: Many metrics are used throughout the performance evaluation of parallel programs (Bahi et al., 2008; Cosnard and Trystan, 1995; Kwiatkowski, 1999). Perhaps the simplest and most intuitive metric of parallel performance is the parallel runtime. It is the time from the moment when computation starts to the moment when the last processor finishes its execution. The parallel run time is composed as an average of three different components: computation time, communication time and idle time (Kwiatkowski, 2006). The computation time (Tcomp) is the time spent on performing computation by all processors, communication time (Tcomm) is the time spent on sending and receiving messages by all processors, the idle time (Tidle) is when processors stay idle. The problem with parallel runtime is that it does not account for the resources used to achieve the execution time. Specifically, if one were to indicate that the parallel runtime of a program, which took 10s on a serial processor, is 2s, we would have no way of knowing whether the parallel program (and associated algorithm) performs well or not. The second metric is scalability. The property of a program to adapt automatically to a given number of processors is called scalability (Douglas et al., 2003). Scalability is more sought after than efficiency (i.e., gain of computing time by parallelism) on any specific architecture/topology. Another one is speedup. Speedup is the ratio of the running time on a single processor to the parallel running time on p processors (Douglas et al., 2003; Alias et al., 1998, 2009b). In other word, the ratio of two program execution times, particularly when times are from execution on 1 and p nodes of the same computer.
CONCLUSIONS
We have presented a lengthy study review for parallel algorithms for solving multidimensional partial differential problems in different fields of engineering and physics. Some partial differential equations which lead to solutions have been illustrated. Also, various numerical and analytical methods of solution have been demonstrated briefly. And finally some phases that are implemented for solving the problems are presented.
For this review, we have not been concerned greatly with the outcomes found in those different researches in which partial differential equations were used to compare and analyze algorithms. The varied and composite problems’ natures in partial differential equations create this job mainly difficult and at this phase no commonly adequate measures of analytic or efficient techniques have been defined. This problem of methods and measurements have addressed and established a diversity of hopeful advances by numerous authors cited here.
We consider that significant appraisal of the comparative effectiveness of a variety of methods can only be prepared in the context of a universally established meaning of efficiency. Besides, significant analyses of classes of algorithms depend upon the aptitude to illustrate these classes theoretically. Outcomes from researches in which classes of algorithms are represented by a small number of haphazardly chosen members are of little value.