天然地震走时反演矩阵顺序三角化算法的优化和并行化

英文篇名：The optimization and parallelization of sequential orthogonal triangularization algorithms used in seismic tomography
中文刊名：地球物理学进展
英文刊名：Progress In Geophysics
作者：刘劲松 ; 刘福田 ; 刘俊 ; 郝天珧
英文作者：LIU Jing-song~(1) ; LIU Fu-tian~(1) ; LIU Jun~(2) ; HAO Tian-yao~(1) (1.Institute of Geology and Geophysics ; Chinese Academy of Sciences ; Beijing 100029 ; China ; 2.Supercomputing Center of network center ; Chinese Academy of Sciences ; Beijing 100083 ; China)
中文关键词：地震层析成像 ; 走时反演 ; QR分解 ; Givens变换 ; 顺序正交三角化 ; 并行计算
英文关键词：seismic tomography ; traveltime inversion ; QR factorization ; Givens Transform ; parallel computation
出版日期：2005-12-30
机构：中国科学院地质与地球物理研究所,中国科学院地质与地球物理研究所,中国科学院网络中心高性能计算中心,中国科学院地质与地球物理研究所北京100029,北京100029,北京100083,北京100029
年：2005
期：04
出版单位：地球物理学进展

摘要

本文讨论了用于天然地震层析成像的矩阵顺序三角化算法,揭示了偏导数矩阵中非零元素的分布规律,在分析算法特点的基础上提出了对程序的几点优化措施,包括:采用合理的存储结构和计算次序以节省内存寻址时间;以一个一维数组存储上三角方阵以节省出一半的内存;对关键的Givens变换子程序进行优化和矢量化等,最终使程序的运行效率提高了数十倍.同时结合算法特点研究了矩阵顺序三角化的并行化方法,提出了两种并行化方案,在联想深腾6800超级计算机上实现了这两种并行算法;对计算量均衡等问题进行了讨论.
This paper addresses the sequential orthogonal triangularization(SOT) algorithms used in seismic tomography.We reveal the distribution feature of none-zero values in partial derivative matrix.Several measures about data structure,computational sequences and vectorization are presented,these measures make the speed increased by tens of times.Two set of parallelization designs for the SOT algorithms are also presented and tested.

引文

[1]刘福田,李强,吴华,胡戈,刘建华,用于速度图象重建的层析成象法[J].地球物理学报,1989,32(3):281~290.
    [2]戈卢布G H,范洛恩C F,著,袁亚湘,等译.矩阵计算[M].科学出版社,2002.
    [3]都志辉.高性能计算之并行编程技术-MPI并行程序设计[M].清华大学出版社,2001.
    [4]Schutter B D,Moor B D.The QR decomposition and the sin-gular value decomposition in the symmetrized max-plus algebra[J].SIAM Journal on Matrix Analysis and Applications,1998,19(2):378~406.
    [5]Kratzer S G.Sparse QR Factorization on a Massively ParallelComputer[J].The Journal of Supercomputiong,1992,6(1):237~255.
    [6]Juan Tourino,Ramon Doallo,Zapata E L.Sparse Givens QRFactorization on a Multiprocessor[J].Tec.Report.
    [7]张文生,张关泉,宋海斌.高精度混合法叠前深度偏移及其并行实现[J].地球物理学报,2001,44(4):542~550.
    [8]朱振宇,刘洪,李幼铭.波动方程叠前深度偏移及并行计算在南黄海地区的应用[J].地球物理学进展,2003,18(2):302~305.
    [9]王真理,李幼铭.细胞自动机地震波模拟的并行化算法[J].地球物理学报,1999,42(3):410~413.