The fast sweeping method is an efficient iterative method for hyperbolic problems. It combines Gauss-Seidel iterations with alternating sweeping orderings. In this paper several parallel implementations of the fast sw...The fast sweeping method is an efficient iterative method for hyperbolic problems. It combines Gauss-Seidel iterations with alternating sweeping orderings. In this paper several parallel implementations of the fast sweeping method are presented. These parallel algorithms are simple and efficient due to the causality of the underlying partial different equations. Numerical examples are used to verify our algorithms.展开更多
Richards方程常用于非饱和土渗流问题,并且应用广泛。在数值求解中,对Richards方程线性化,进而采用有限差分法进行数值离散以及迭代计算。其中传统的迭代法比如Jacobi迭代、Gauss-Seidel迭代法(GS)和连续超松驰迭代法(successive over-r...Richards方程常用于非饱和土渗流问题,并且应用广泛。在数值求解中,对Richards方程线性化,进而采用有限差分法进行数值离散以及迭代计算。其中传统的迭代法比如Jacobi迭代、Gauss-Seidel迭代法(GS)和连续超松驰迭代法(successive over-relaxation method,简称SOR)迭代收敛率较慢,尤其在离散空间步长较小以及离散时间步长较大时。因此,采用整体校正法以及多步预处理法对传统迭代法进行改进,提出一种基于整体校正法的多步预处理Gauss-Seidel迭代法(improved Gauss-Seidel iterative method with multistep preconditioner based on the integral correction method,简称ICMP(m)-GS)求解Richards方程导出的线性方程组。通过非饱和渗流算例,并与传统迭代法和解析解对比,对改进算法的收敛率和加速效果进行了验证。结果表明,提出的ICMP(m)-GS可以很大程度地改善线性方程组的病态性,相较于常规方法GS,SOR以及单一改进方法,ICMP(m)-GS具有更快的收敛率,更高的计算效率和计算精度。该方法可以为非饱和土渗流的数值模拟提供一定参考。展开更多
In this paper, Aitken’s extrapolation normally applied to convergent fixed point iteration is extended to extrapolate the solution of a divergent iteration. In addition, higher order Aitken extrapolation is introduce...In this paper, Aitken’s extrapolation normally applied to convergent fixed point iteration is extended to extrapolate the solution of a divergent iteration. In addition, higher order Aitken extrapolation is introduced that enables successive decomposition of high Eigen values of the iteration matrix to enable convergence. While extrapolation of a convergent fixed point iteration using a geometric series sum is a known form of Aitken acceleration, it is shown that in this paper, the same formula can be used to estimate the solution of sets of linear equations from diverging Gauss-Seidel iterations. In both convergent and divergent iterations, the ratios of differences among the consecutive values of iteration eventually form a convergent (divergent) series with a factor equal to the largest Eigen value of the iteration matrix. Higher order Aitken extrapolation is shown to eliminate the influence of dominant Eigen values of the iteration matrix in successive order until the iteration is determined by the lowest possible Eigen values. For the convergent part of the Gauss-Seidel iteration, further acceleration is made possible by coupling of the extrapolation technique with the successive over relaxation (SOR) method. Application examples from both convergent and divergent iterations have been provided. Coupling of the extrapolation with the SOR technique is also illustrated for a steady state two dimensional heat flow problem which was solved using MATLAB programming.展开更多
基金This work is partially supported by Sloan FoundationNSF DMS0513073+1 种基金ONR grant N00014-02-1-0090DARPA grant N00014-02-1-0603
文摘The fast sweeping method is an efficient iterative method for hyperbolic problems. It combines Gauss-Seidel iterations with alternating sweeping orderings. In this paper several parallel implementations of the fast sweeping method are presented. These parallel algorithms are simple and efficient due to the causality of the underlying partial different equations. Numerical examples are used to verify our algorithms.
文摘Richards方程常用于非饱和土渗流问题,并且应用广泛。在数值求解中,对Richards方程线性化,进而采用有限差分法进行数值离散以及迭代计算。其中传统的迭代法比如Jacobi迭代、Gauss-Seidel迭代法(GS)和连续超松驰迭代法(successive over-relaxation method,简称SOR)迭代收敛率较慢,尤其在离散空间步长较小以及离散时间步长较大时。因此,采用整体校正法以及多步预处理法对传统迭代法进行改进,提出一种基于整体校正法的多步预处理Gauss-Seidel迭代法(improved Gauss-Seidel iterative method with multistep preconditioner based on the integral correction method,简称ICMP(m)-GS)求解Richards方程导出的线性方程组。通过非饱和渗流算例,并与传统迭代法和解析解对比,对改进算法的收敛率和加速效果进行了验证。结果表明,提出的ICMP(m)-GS可以很大程度地改善线性方程组的病态性,相较于常规方法GS,SOR以及单一改进方法,ICMP(m)-GS具有更快的收敛率,更高的计算效率和计算精度。该方法可以为非饱和土渗流的数值模拟提供一定参考。
文摘In this paper, Aitken’s extrapolation normally applied to convergent fixed point iteration is extended to extrapolate the solution of a divergent iteration. In addition, higher order Aitken extrapolation is introduced that enables successive decomposition of high Eigen values of the iteration matrix to enable convergence. While extrapolation of a convergent fixed point iteration using a geometric series sum is a known form of Aitken acceleration, it is shown that in this paper, the same formula can be used to estimate the solution of sets of linear equations from diverging Gauss-Seidel iterations. In both convergent and divergent iterations, the ratios of differences among the consecutive values of iteration eventually form a convergent (divergent) series with a factor equal to the largest Eigen value of the iteration matrix. Higher order Aitken extrapolation is shown to eliminate the influence of dominant Eigen values of the iteration matrix in successive order until the iteration is determined by the lowest possible Eigen values. For the convergent part of the Gauss-Seidel iteration, further acceleration is made possible by coupling of the extrapolation technique with the successive over relaxation (SOR) method. Application examples from both convergent and divergent iterations have been provided. Coupling of the extrapolation with the SOR technique is also illustrated for a steady state two dimensional heat flow problem which was solved using MATLAB programming.
