Research On The Parallel Domain Decomposition Algorithm In American Option Simulation And Optimization Problems

The rapid development and popularization of parallel computers make the long-time span and high-resolution numerical simulations possible.Because of the complexity,massive scale and long-time span of the system to be solved,its com-putation is often time-consuming,and it would be necessary to develop scalable solvers to reduce the computing time and achieve high-performance numerical sim-ulations.For many large-scale scientific computations,the success of the numerical simulations highly depends on the sparse linear system,since it takes much com-puting time during the solving process.Highly ill-conditioned linear systems are difficult to solve.Traditional iterative algorithms usually lead to slow convergence or even divergence when solving such problems.Designing efficient and robust preconditioners is an essential way to improve the convergence of corresponding iterative algorithms.The domain decomposition methods are easy to parallelize and have good parallel performances.These methods are widely applied in sci-entific and engineering computations as strategies of parallelization and have the potential to enhance the scalability of iterative algorithms.This dissertation inte-grates the overlapping additive Schwarz preconditioners and the Krylov iterative methods,and focuses on the applications of this combined method in three fields,including the optimization problems constrained by the partial differential equa-tions,the American option pricing and the time fractional diffusion equations.The main contents are given as follows:1.In large scale numerical simulations,the parallel Lagrange active-set reduced-space method is proposed to solve the optimization problems governed by the par-tial differential equations with inequality constraints.By treating the discretized partial differential equations as equality constraints and the control constraints as inequality constraints,we derive a mixed complementarity problem after using the Karush-Kuhn-Tucker(KKT)conditions.The Lagrange active-set reduced-space method simplifies the mixed complementarity problem into a system of nonlinear equations.During the solving process of this nonlinear system,the search direction is given at first as the solution of a reduced linear system.The projected operator is then introduced to ensure that the iterates are still within the variable bounds.In order to accelerate the numerical simulations and enhance the scalabilities of the solvers,we consider the domain decomposition method to construct a family of overlapping additive Schwarz preconditioners.Numerical results of large-scale two-dimensional and three-dimensional tests demonstrate good scalabilities of the proposed Lagrange active-set reduced-space method.2.A class of parallel semismooth Newton algorithms is developed for the American option problems under the Black-Scholes-Merton pricing framework.For the complementarity problem derived by discretizing the pricing model,a non-linear complementarity problem function is considered to transform the original problem into a nonlinear system.A generalized Newton method with the over-lapping additive Schwarz preconditioners is then applied to solve this nonlinear system.Moreover,an adaptive time step strategy,which adjusts the time step sizes according to the initial residuals of the Newton iterations-is employed to improve the performance of the proposed method.Numerical experiments show that the proposed semismooth Newton method has good accuracy and scalability.3.The domain decomposition type preconditioners are applied to solve the time fractional diffusion equations,and the accuracy of the corresponding algo-rithm is improved by the application of the adaptive time step strategy.Since solutions of the time fractional diffusion equations have a weak singularity at the initial time,the accuracy of the solution decreases when discretizing the Caputo derivative on a uniform time mesh.To solve this problem,the nonuniform mesh formed by the adaptive time step strategy is combined with the direct method and the fast method respectively to improve the solution accuracy around the ini-tial time.Numerical tests prove that both the direct method and the fast method help to achieve ideal convergence rate in combination use of the adaptive time step strategy.Numerical experiments indicate that the fast method has high scalability.