基于SiPESC平台的线性代数方程组算法研究
|
摘要
面向大规模科学与工程计算的软件系统是进行科学研究与工程分析的重要工具,这类软件必须具有良好的开放性与通用性。然而,传统的软件设计开发方法已经不能满足科技进步对计算软件系统的要求。SiPESC (Software Integration Platform for Engineering and Scientific Computation)软件集成平台是采用面向对象设计方法与插件体系架构开发的面向大规模科学与工程计算的通用集成软件平台。本文基于SiPESC系统进行了有限元线性代数方程组求解相关算法的研究以及程序实现。
本文实现了矩阵轮廓缩减的AD(Akhras-Dhatt)与RCM(Reverse Cuthill-Mckee)排序算法,并且引入了对有限元结构节点的坐标预优序处理。经排序后,一维变带宽格式存储的有限元总体刚度矩阵的数据量降低了约1个数量级；在此基础上,基于一维变带宽存储格式的LDLT分解求解器的计算效率提高了1-2个数量级。其中,坐标预优序明显提高了AD算法的计算效率,改善了其排序效果。
为了发展内外存交换的线性代数方程组稀疏快速直接求解算法的求解器,也为当前的SiPESC.FEMS系统提供中小规模问题的求解方案,本文讨论并实现了在SiPESC架构上组集稀疏存储矩阵格式总体刚度矩阵的程序,并在此基础上集成了开放源代码的稀疏超节点Cholesky分解求解器CHOLMOD。算例表明,当问题规模允许CHOLMOD进行内存求解时,其计算速度较一维变带宽LDLT分解求解器有数量级上的提升。
本文猜想矩阵轮廓对矩阵分解计算中产生的填入元数量可能具有约束作用。算例证明了这一猜想。通过算例对比,证明在规模较小的情况下轮廓缩减算法在填入元优化中的作用不逊于高效的填入元优化程序AMD(Approximate Minimum Degree)程序包。针对这一现象,本文作了初步的分析。
As an important numerical simulation tool, massive computational software systems aiming at scientific and engineering computation should be open for functional extension and general purposes. However, the traditional method of software design no longer meets the requirements of advance computation software. By the object-orient software design method and the plugin software architecture, Software Integration Platform for Engineering and Scientific Computation (SiPESC) is developed as a generality integration platform for large-scale scientific and engineering computation. Based on SiPESC system, algorithm research on linear algebra equations and its implementation for finite element analysis are present in this thesis.
This thesis realizes AD algorithm and RCM algorithm using for matrix profile reduction, and introduce the pre-ordering program for FE structure nodal coordinates. The size of FEA global stiffness matrix storage by skyline format has been reduced about 1 order of magnitude by nodal ordering, and the computation efficiency of LDLT factorization is also improved 1-2 orders of magnitude. It shows that the pre-ordering program improve the computation efficiency significantly, and modifies its ordering quality.
In order to develop the out-of-core fast direct sparse solver of linear system, also to develop SiPESC.FEMS system for solution of medium scale problem, this thesis investigates and implements assembly program for global stiffness matrix by using compressed sparse column format. Furthermore, an open source sparse supernodal Cholesky factorization solver- CHOLMOD has been integrated. Numerical example show that the speed up of this solver over orders of magnitude than former LDLT solver if the problem could solve in-core.
This thesis made a hypothesis that the matrix profile could be the constraint of fill-in of matrix factorization. Numerical example provided the evidence of this hypothesis. Preliminary compare have been made on the effects of profile reduction program and fill-in optimization program AMD(Approximate Minimum Degree) package. It is proved that profile reduction program reduces the fill-in of small-scale matrix effectively.
本文实现了矩阵轮廓缩减的AD(Akhras-Dhatt)与RCM(Reverse Cuthill-Mckee)排序算法,并且引入了对有限元结构节点的坐标预优序处理。经排序后,一维变带宽格式存储的有限元总体刚度矩阵的数据量降低了约1个数量级；在此基础上,基于一维变带宽存储格式的LDLT分解求解器的计算效率提高了1-2个数量级。其中,坐标预优序明显提高了AD算法的计算效率,改善了其排序效果。
为了发展内外存交换的线性代数方程组稀疏快速直接求解算法的求解器,也为当前的SiPESC.FEMS系统提供中小规模问题的求解方案,本文讨论并实现了在SiPESC架构上组集稀疏存储矩阵格式总体刚度矩阵的程序,并在此基础上集成了开放源代码的稀疏超节点Cholesky分解求解器CHOLMOD。算例表明,当问题规模允许CHOLMOD进行内存求解时,其计算速度较一维变带宽LDLT分解求解器有数量级上的提升。
本文猜想矩阵轮廓对矩阵分解计算中产生的填入元数量可能具有约束作用。算例证明了这一猜想。通过算例对比,证明在规模较小的情况下轮廓缩减算法在填入元优化中的作用不逊于高效的填入元优化程序AMD(Approximate Minimum Degree)程序包。针对这一现象,本文作了初步的分析。
As an important numerical simulation tool, massive computational software systems aiming at scientific and engineering computation should be open for functional extension and general purposes. However, the traditional method of software design no longer meets the requirements of advance computation software. By the object-orient software design method and the plugin software architecture, Software Integration Platform for Engineering and Scientific Computation (SiPESC) is developed as a generality integration platform for large-scale scientific and engineering computation. Based on SiPESC system, algorithm research on linear algebra equations and its implementation for finite element analysis are present in this thesis.
This thesis realizes AD algorithm and RCM algorithm using for matrix profile reduction, and introduce the pre-ordering program for FE structure nodal coordinates. The size of FEA global stiffness matrix storage by skyline format has been reduced about 1 order of magnitude by nodal ordering, and the computation efficiency of LDLT factorization is also improved 1-2 orders of magnitude. It shows that the pre-ordering program improve the computation efficiency significantly, and modifies its ordering quality.
In order to develop the out-of-core fast direct sparse solver of linear system, also to develop SiPESC.FEMS system for solution of medium scale problem, this thesis investigates and implements assembly program for global stiffness matrix by using compressed sparse column format. Furthermore, an open source sparse supernodal Cholesky factorization solver- CHOLMOD has been integrated. Numerical example show that the speed up of this solver over orders of magnitude than former LDLT solver if the problem could solve in-core.
This thesis made a hypothesis that the matrix profile could be the constraint of fill-in of matrix factorization. Numerical example provided the evidence of this hypothesis. Preliminary compare have been made on the effects of profile reduction program and fill-in optimization program AMD(Approximate Minimum Degree) package. It is proved that profile reduction program reduces the fill-in of small-scale matrix effectively.
引文
[1]景益鹏.星系形成的超大型计算机模拟[J].天文学进展.2001,19(2)：227-230.
[2]赵崇斌,Hobbs B E, Ord A.用计算地球科学研究方法探讨地质现象的动力学机制[J].中国科学D辑：地球科学.2008,38(5)：646-652.
[3]李明明,何玉梅.利用瑞雷面波反演华北克拉通东北部边界的岩石圈结构[J].地震学报.2011,33(2)：143-155.
[4]何利,李整林,彭朝晖,等.南海北部海水声速剖面声学反演[J].中国科学G辑：物理学力学天文学.2011,41(1)：49-57.
[5]侯日立,彭建祥,经福谦.一种计算金属剪切模量的本构模型：以AI为例[J].物理学报.2009,58(9)：6413-6418.
[6]Courant R. Variational Methods for the Solution of Problems of Equilibrium and Vibrations[J]. Bulletin of the American Mathematical Society.1943,49:1-23.
[7]Turner M J, Clough R W, Martin H C, et al. Stiffness and Deflection Analysis of Complex Structures[J]. Journal of the Aeronautical Sciences.1956,23:805-823,854.
[8]Clough R W. The Finite Element Method in Plane Stress Analysis[C]. Conference on Electronic Computation, Pittsburgh,1960.
[9]胡海昌.论弹性体力学与受范性体力学中的一般变分原理[J].物理学报.1954,10(3)：259-290.
[10]Washizu K. On the Variational Principles of Elasticity and Plasticity[C]. In:MIT. Aeroelastic and Structures Research laboratory, Technical Report. Cambridge:MIT.1955.
[11]Bazeley G P, Cheung Y K, Irons B M, et al. Triangular Elements in Plate Bending Conforming and Nonconforming Solutions[C]. Proceedings of the Conference on Matrix Methods in Struc-tural Mechanics, Dayton Ohio,1965:547-576.
[12]Strang G. Variational Crimes in the Finite Element Method[C]. In:Aziz A K, ed. The Mathe-matical Foundations of the Finite Element Method. New York:Academic Press,1972:689-710.
[13]Taylor R L, Simo J C, Zienkiewicz O C, et al. The Patch Test-a Condition for Assessing FEM Convergence [J]. International Journal for Numerical Methods in Engineering.1986,22(1): 39-62.
[14]Stummel F. The Generalized Patch Test[J]. SIAM Journal on Numerical Analysis.1979,16(3): 449-471.
[15]Stummel F. The limitation of the Patch Test[J]. International Journal for Numerical Methods in Engineering.1980,15(2):177-188.
[16]徐树方.矩阵计算的理论与方法[M].北京：北京大学出版社,1995.
[17]Golub G H, Van Loan C F.矩阵计算[M].北京：人民邮电出版社,2009.
[18]吴建平,王正华,李晓梅.稀疏线性方程组的高效求解与并行计算[M].湖南：湖南科学技术出版社,2004.
[19]Saad Y. Iterative Methods for Sparse Linear Systems[M]. 北京:科学出版社,2009.
[20]孙树立,陈璞.求解多右端向量方程组的块共轭梯度法及其相关研究进展[C].第三届全国计算爆炸力学会议,山东,青岛,2006：3-10.
[21]Sala M, Heroux M A, Day D M. Trilinos Tutorial[EB/OL]. (2007,11) [2011,5,18]. http:// trilinos.sandia.gov/.
[22]Balay S, Buschelman K, Eijkhout V, et al. PETSc Users Manual [EB/OL]. (2010,3) [2011,5,18]. http://www.mcs.anl.gov/petsc/petsc-as/index.html.
[23]张相征,张云泉,王婷,等.天体大规模数值模拟软件性能优化[J].华中科技大学学报(自然科学版).2010,38：51-54.
[24]程汤培,王群.一种基于PETSc的热传导方程大规模并行求解策略[J].计算机科学.2009,36(11)：160-164.
[25]王勖成.有限单元法[M].北京：清华大学出版社,2003.
[26]Gibbs N E, Poole W G, Jr, Stockmeyer P K. An Algorithm for Reducing the Bandwidth and Profile of A Sparse Matrix[J]. SIAM Journal on Numerical Analysis.1976,13(2):236-150.
[27]江雄心,万平荣.三维有限元网格节点编号优化[J].工程图学学报.2008,4：22-26.
[28]姜涛,王安麟,朱灯林.有限元节点编号的综合带宽优化算法[J].机械设计.2005,22(11)：3-6.
[29]Papadimitriou Ch H. The NP-Completeness of the Bandwidth Minimization Problem[J]. Com-puting.1976,16(3):263-270.
[30]黄志超,包忠诩,周天瑞.有限元节点编号优化[J].南昌大学学报(理科版).2004,28(3)：281-284.
[31]张媛媛,侯华,程军,等.一种有限元网格节点编号的优化算法[J].铸造技术.2007,2(4)：541-543.
[32]邢渊,董林峰.有限元网格节点优化排序方法研究[J].计算力学学报.1999,16(3)：366-369.
[33]Cuthill E, McKee J. Reducing the Bandwidth of Sparse Symmetric Matrices[C]. ACM'69 Proceedings of the 1969 24th National Conference, New York,1969:157-172.
[34]Liu J W H, Sherman A H. Comparative Analysis of the Cuthill-McKee and the Reverse Cuthill-McKee Ordering Algorithms for Sparse Matrices[J]. SIAM Journal on Numerical Analysis.1976, 13(2):198-213.
[35]钟万勰.一个多用途的结构分析程序JIEGFEX(一)[J].大连工学院学报.1977,3：19-41.
[36]Boman E G, Hendrickson B. A Multilevel Algorithm for Reducing the Envelope of Sparse Matrices[C]. In:Standford University. Technical Report SCCM-96-14. San Francisco:Standford University,1996.
[37]Barnard S T, Pothen A, Simon H D. A Spectral Algorithm for Envelope Reduction of Sparse Matrices[C]. Supercomputing'93 Proceedings of the 1993 ACM/IEEE conference on Super-computing. New York, ACM,1993:493-502.
[38]刘长学.超大规模稀疏矩阵计算方法[M].上海：上海科学技术出版社.1991.
[39]Curtis A R, Reid J K. The Solution of Large Sparse Unsymmetric Systems of Linear Equtions[J]. IMA Journal of Applied Methematics.1971,8(3):344-353.
[40]Sherman A H. On the Efficient Solution of Sparse Systems of Linear and Nonlinear Equations[D] (Doctoral Dissertation). New Haven:Yale University,1975.
[41]陈璞,孙树立,袁明武.有限元分析快速解法[J].力学学报.2002,34(2)：216-222.
[42]Liu J W H. The Role of Elimination Trees in Sparse Factorization[J]. SIAM Journal on Matrix Analysis and Application.1990,11(1):134-172.
[43]周洪伟,吴舒,陈璞.有限元分析快速直接求解技术进展[J].力学进展.2007,37(2)：175-188.
[44]Yannakakis M. Computing the Minimun Fill-in is NP-Complete[J]. SIAM Journal Algebraic and Discrete Methods.1981,2:77-79.
[45]Markowitz H M. The Elimination Form of the Inverse and Its Application to Linear Program-ming[J]. Management Science.1957,3(3):255-269.
[46]Tinney W F, Walker J W. Direct Solutions of Sparse Network Equations by Optimally Ordered Triangular Factorization[J]. Proceeding of IEEE.1967,55(11):1801-1809.
[47]Hendrickson B, Leland R. A Multilevel Algorithm for Partitioning Graphs[C]. Supercomputing '95 Proceedings of the 1995 ACM/IEEE conference on Supercomputing. New York, ACM,1995.
[48]Alidaee B, Kochenberger G A, Amini M M. Greedy Solutions of Selection and Ordering Problems[J]. European Journal of Operational Research.2001,134(1):203-215.
[49]Amestoy P R, Davis T A, Duff I S. Algorithm 837:AMD, An Approximate Minimum Degree Ordering Algorithm [J]. ACM Transactions on Mathematical Software.2004,30(3):381-388.
[50]Davis T A. User Guide for CHOLMOD[EB/OL]. (2011,1,25) [2011,5,26]. http://www. cise.ufl.edu/research/sparse/cholmod/.
[51]钟万勰.计算结构力学微机程序设计[M].北京：水利电力出版社.1986.
[2]赵崇斌,Hobbs B E, Ord A.用计算地球科学研究方法探讨地质现象的动力学机制[J].中国科学D辑：地球科学.2008,38(5)：646-652.
[3]李明明,何玉梅.利用瑞雷面波反演华北克拉通东北部边界的岩石圈结构[J].地震学报.2011,33(2)：143-155.
[4]何利,李整林,彭朝晖,等.南海北部海水声速剖面声学反演[J].中国科学G辑：物理学力学天文学.2011,41(1)：49-57.
[5]侯日立,彭建祥,经福谦.一种计算金属剪切模量的本构模型：以AI为例[J].物理学报.2009,58(9)：6413-6418.
[6]Courant R. Variational Methods for the Solution of Problems of Equilibrium and Vibrations[J]. Bulletin of the American Mathematical Society.1943,49:1-23.
[7]Turner M J, Clough R W, Martin H C, et al. Stiffness and Deflection Analysis of Complex Structures[J]. Journal of the Aeronautical Sciences.1956,23:805-823,854.
[8]Clough R W. The Finite Element Method in Plane Stress Analysis[C]. Conference on Electronic Computation, Pittsburgh,1960.
[9]胡海昌.论弹性体力学与受范性体力学中的一般变分原理[J].物理学报.1954,10(3)：259-290.
[10]Washizu K. On the Variational Principles of Elasticity and Plasticity[C]. In:MIT. Aeroelastic and Structures Research laboratory, Technical Report. Cambridge:MIT.1955.
[11]Bazeley G P, Cheung Y K, Irons B M, et al. Triangular Elements in Plate Bending Conforming and Nonconforming Solutions[C]. Proceedings of the Conference on Matrix Methods in Struc-tural Mechanics, Dayton Ohio,1965:547-576.
[12]Strang G. Variational Crimes in the Finite Element Method[C]. In:Aziz A K, ed. The Mathe-matical Foundations of the Finite Element Method. New York:Academic Press,1972:689-710.
[13]Taylor R L, Simo J C, Zienkiewicz O C, et al. The Patch Test-a Condition for Assessing FEM Convergence [J]. International Journal for Numerical Methods in Engineering.1986,22(1): 39-62.
[14]Stummel F. The Generalized Patch Test[J]. SIAM Journal on Numerical Analysis.1979,16(3): 449-471.
[15]Stummel F. The limitation of the Patch Test[J]. International Journal for Numerical Methods in Engineering.1980,15(2):177-188.
[16]徐树方.矩阵计算的理论与方法[M].北京：北京大学出版社,1995.
[17]Golub G H, Van Loan C F.矩阵计算[M].北京：人民邮电出版社,2009.
[18]吴建平,王正华,李晓梅.稀疏线性方程组的高效求解与并行计算[M].湖南：湖南科学技术出版社,2004.
[19]Saad Y. Iterative Methods for Sparse Linear Systems[M]. 北京:科学出版社,2009.
[20]孙树立,陈璞.求解多右端向量方程组的块共轭梯度法及其相关研究进展[C].第三届全国计算爆炸力学会议,山东,青岛,2006：3-10.
[21]Sala M, Heroux M A, Day D M. Trilinos Tutorial[EB/OL]. (2007,11) [2011,5,18]. http:// trilinos.sandia.gov/.
[22]Balay S, Buschelman K, Eijkhout V, et al. PETSc Users Manual [EB/OL]. (2010,3) [2011,5,18]. http://www.mcs.anl.gov/petsc/petsc-as/index.html.
[23]张相征,张云泉,王婷,等.天体大规模数值模拟软件性能优化[J].华中科技大学学报(自然科学版).2010,38：51-54.
[24]程汤培,王群.一种基于PETSc的热传导方程大规模并行求解策略[J].计算机科学.2009,36(11)：160-164.
[25]王勖成.有限单元法[M].北京：清华大学出版社,2003.
[26]Gibbs N E, Poole W G, Jr, Stockmeyer P K. An Algorithm for Reducing the Bandwidth and Profile of A Sparse Matrix[J]. SIAM Journal on Numerical Analysis.1976,13(2):236-150.
[27]江雄心,万平荣.三维有限元网格节点编号优化[J].工程图学学报.2008,4：22-26.
[28]姜涛,王安麟,朱灯林.有限元节点编号的综合带宽优化算法[J].机械设计.2005,22(11)：3-6.
[29]Papadimitriou Ch H. The NP-Completeness of the Bandwidth Minimization Problem[J]. Com-puting.1976,16(3):263-270.
[30]黄志超,包忠诩,周天瑞.有限元节点编号优化[J].南昌大学学报(理科版).2004,28(3)：281-284.
[31]张媛媛,侯华,程军,等.一种有限元网格节点编号的优化算法[J].铸造技术.2007,2(4)：541-543.
[32]邢渊,董林峰.有限元网格节点优化排序方法研究[J].计算力学学报.1999,16(3)：366-369.
[33]Cuthill E, McKee J. Reducing the Bandwidth of Sparse Symmetric Matrices[C]. ACM'69 Proceedings of the 1969 24th National Conference, New York,1969:157-172.
[34]Liu J W H, Sherman A H. Comparative Analysis of the Cuthill-McKee and the Reverse Cuthill-McKee Ordering Algorithms for Sparse Matrices[J]. SIAM Journal on Numerical Analysis.1976, 13(2):198-213.
[35]钟万勰.一个多用途的结构分析程序JIEGFEX(一)[J].大连工学院学报.1977,3：19-41.
[36]Boman E G, Hendrickson B. A Multilevel Algorithm for Reducing the Envelope of Sparse Matrices[C]. In:Standford University. Technical Report SCCM-96-14. San Francisco:Standford University,1996.
[37]Barnard S T, Pothen A, Simon H D. A Spectral Algorithm for Envelope Reduction of Sparse Matrices[C]. Supercomputing'93 Proceedings of the 1993 ACM/IEEE conference on Super-computing. New York, ACM,1993:493-502.
[38]刘长学.超大规模稀疏矩阵计算方法[M].上海：上海科学技术出版社.1991.
[39]Curtis A R, Reid J K. The Solution of Large Sparse Unsymmetric Systems of Linear Equtions[J]. IMA Journal of Applied Methematics.1971,8(3):344-353.
[40]Sherman A H. On the Efficient Solution of Sparse Systems of Linear and Nonlinear Equations[D] (Doctoral Dissertation). New Haven:Yale University,1975.
[41]陈璞,孙树立,袁明武.有限元分析快速解法[J].力学学报.2002,34(2)：216-222.
[42]Liu J W H. The Role of Elimination Trees in Sparse Factorization[J]. SIAM Journal on Matrix Analysis and Application.1990,11(1):134-172.
[43]周洪伟,吴舒,陈璞.有限元分析快速直接求解技术进展[J].力学进展.2007,37(2)：175-188.
[44]Yannakakis M. Computing the Minimun Fill-in is NP-Complete[J]. SIAM Journal Algebraic and Discrete Methods.1981,2:77-79.
[45]Markowitz H M. The Elimination Form of the Inverse and Its Application to Linear Program-ming[J]. Management Science.1957,3(3):255-269.
[46]Tinney W F, Walker J W. Direct Solutions of Sparse Network Equations by Optimally Ordered Triangular Factorization[J]. Proceeding of IEEE.1967,55(11):1801-1809.
[47]Hendrickson B, Leland R. A Multilevel Algorithm for Partitioning Graphs[C]. Supercomputing '95 Proceedings of the 1995 ACM/IEEE conference on Supercomputing. New York, ACM,1995.
[48]Alidaee B, Kochenberger G A, Amini M M. Greedy Solutions of Selection and Ordering Problems[J]. European Journal of Operational Research.2001,134(1):203-215.
[49]Amestoy P R, Davis T A, Duff I S. Algorithm 837:AMD, An Approximate Minimum Degree Ordering Algorithm [J]. ACM Transactions on Mathematical Software.2004,30(3):381-388.
[50]Davis T A. User Guide for CHOLMOD[EB/OL]. (2011,1,25) [2011,5,26]. http://www. cise.ufl.edu/research/sparse/cholmod/.
[51]钟万勰.计算结构力学微机程序设计[M].北京：水利电力出版社.1986.