高精度曲面建模的一种快速算法
收稿日期: 2011-11-07
修回日期: 2012-04-18
网络出版日期: 2012-06-25
基金资助
国家杰出青年科学基金项目(40825003);全球变化研究国家重大科学研究计划项目课题(2010CB950904);国家自然科学基金重点项目(41023010)。
Fast Methods for High Accuracy Surface Moldeling
Received date: 2011-11-07
Revised date: 2012-04-18
Online published: 2012-06-25
Supported by
null
高精度曲面建模(HASM)是一种全新的曲面建模方法,其整个过程可分为偏微分方程的离散、采样方程建立和代数方程组求解3个阶段。目前所采用的求解对称正定方程组的方法主要是共轭梯度法。为了解决HASM的计算速度问题,本文给出了2种新的预处理共轭梯度算法,分别为不完全Cholesky分解共轭梯度法和对称逐步超松弛预处理共轭梯度法。实验表明,不完全Cholesky分解共轭梯度法收敛速度最快,且这2种预处理方法均比其他方法具有更快的收敛速度。
关键词: 不完全cholesky分解; HASM; 预处理共轭梯度法; 对称逐步超松弛算法
赵娜, 岳天祥 . 高精度曲面建模的一种快速算法[J]. 地球信息科学学报, 2012 , 14(3) : 281 -285 . DOI: 10.3724/SP.J.1047.2012.00281
As a novel surface modeling method, the whole computing process of HASM can be divided into three parts: deriving finite difference approximations to differential equations, establishing the sampling point equations and solving the algebra equations. The well known conjugate gradient method has been used extensively to solve this symmetric positive definite system instead of Gaussian's elimination based direct methods, especially for very large systems when parallel solution environment is preferred. However, a difficulty associated with the method of conjugate gradients is that it works well on matrices that are either well conditioned or have just a few distinct eigenvalues and the coefficient matrix of the algebra equation in HASM is ill-conditioned. In this paper, we show how to preprocess a linear system so that the matrix of coefficients assumes one of these nice forms. We give two other preconditioners, i.e. incomplete Cholesky decomposition conjugate gradient method (ICCG) and symmetric successive over relaxation-preconditioned conjugate gradient method (SSORCG), so as to improve the convergence rate of HASM. Furthermore, we give adequate consideration in storage scheme of the large sparse matrix and optimize the performance of sparse matrix-vector multiplication. The cost of the computation is also considered in each iteration. We implement and test the proposed method on a Dell OptiPlex 990MT machine. Numerical tests show that ICCG has the fastest convergence rate of HASM. We also find that both ICCG and SSORCG have much faster convergence rates than others.
[1] 岳天祥,杜正平,刘纪远. 高精度曲面建模与误差分析[J]. 自然科学进展, 2004, 14(2): 83-89.
[2] 岳天祥,杜正平. 高精度曲面建模与经典模型的误差比较分析[J]. 自然科学进展, 2007, 16(8): 986-991.
[3] 岳天祥,杜正平. 高精度曲面建模最佳表达形式的数值实验分析[J]. 地球信息科学, 2006, 8(3): 83-87.
[4] Yue T X. Surface modeling: High accuracy and high speed methods[J]. CRC Press, 2010,39-63.
[5] Davis T J. Direct methods for Sparse Linear Systems[J]. SIAM Philadelphia. 2006,85-94.
[6] Hestenes M R, Stiefel E F. Methods of conjugate gradients for solving linear systems[J]. J.Res. Nat.Bur. Stand. 1952, 49: 409-436.
[7] Golub G H, Van Loan C F. Matrix computations[J]. Posts & Telecompress. 2009,530-535.
[8] Meijerink J A, Vorst van der H A. An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix[J]. Math. Comp. 1977(31):148-162.
[9] 陈传法,岳天祥,张照杰.高精度曲面模型的解算[J]. 武汉大学学报(信息科学版), 2010,35(3):365-368.
[10] Evans D J, Forrington C V D. An iterative process for optimizing symmetric successive over-relaxation[J]. The Computer Journal, 1963, 6(3): 271-273.
[11] Helfenstein R, Koko J. Parallel preconditioned conjugate gradient algorithm on GPU[J]. Journal of Computational and Applied Mathematics,2012,236(15):3584-3590.
/
〈 | 〉 |