1887
  1. Home
  2. A-Z Publications
  3. Geophysical Prospecting
  4. Volume 59, Issue 5
  5. Article
Modelling Methods for Geophysical Imaging: Trends and Perspectives
  • E-ISSN: 1365-2478

Abstract

ABSTRACT

We consider the modeling of (polarized) seismic wave propagation on a rectangular domain via the discretization and solution of the inhomogeneous Helmholtz equation in 3D, by exploiting a parallel multifrontal sparse direct solver equipped with Hierarchically Semi‐Separable (HSS) structure to reduce the computational complexity and storage. In particular, we are concerned with solving this equation on a large domain, for a large number of different forcing terms in the context of seismic problems in general, and modeling in particular. We resort to a parsimonious mixed grid finite differences scheme for discretizing the Helmholtz operator and Perfect Matched Layer boundaries, resulting in a non‐Hermitian matrix. We make use of a nested dissection based domain decomposition, and introduce an approximate direct solver by developing a parallel HSS matrix compression, factorization, and solution approach. We cast our massive parallelization in the framework of the multifrontal method. The assembly tree is partitioned into local trees and a global tree. The local trees are eliminated independently in each processor, while the global tree is eliminated through massive communication. The solver for the inhomogeneous equation is a parallel hybrid between multifrontal and HSS structure. The computational complexity associated with the factorization is almost linear in the size, say, of the matrix, viz. between ( log ) and (4/3 log ), while the storage is almost linear as well, between () and ( log ). We exploit the use of a regular (Cartesian) mesh common in many seismic applications.

© 2011 European Association of Geoscientists & Engineers
Loading

Article metrics loading...

/content/journals/10.1111/j.1365-2478.2011.00982.x
2011-08-22
2024-04-27

  • From This Site

    /content/journals/10.1111/j.1365-2478.2011.00982.x
    dcterms_title,dcterms_subject,pub_keyword
    -contentType:Journal -contentType:Contributor -contentType:Concept -contentType:Institution
    10
    5
Loading full text...

Full text loading...

References

  1. AgulloE., GuermoucheA. and L'ExcellentJ.2008. A parallel out‐of‐core multifrontal method: Storage of factors on disk and analysis of models for an out‐of‐core active memory. Parallel Computing34, 296–317.
    [Google Scholar]
  2. BaiZ., DemmelJ., DongarraJ., RuheA. and Van den VorstH.2000. Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide . SIAM.
    [Google Scholar]
  3. BebendorfM.2005. Efficient inversion of galerkin matrices of general second‐order elliptic differential operators with nonsmooth coefficients. Mathematics of Computation74, 1179–1199.
    [Google Scholar]
  4. BebendorfM. and HackbuschW.2003. Existence of ‐matrix approximants to the inverse FE‐matrix of elliptic operators with L ∞ coefficients. Numerical Mathematics95, 1–28.
    [Google Scholar]
  5. BörmS., GrasedyckL. and HackbuschW.2003. Introduction to hierarchical matrices with applications. Engineering Analysis with Boundary Elements27, 405–422.
    [Google Scholar]
  6. BörmS. and HackbuschW., Data‐sparse approximation by adaptive ‐matrices. Technical Report, Max Planck Institute for Mathematics.
  7. ChandrasekaranS., DewildeP., GuM. and SomasunderamN.2010. On the numerical rank of the off‐diagonal blocks of schur complements of discretized elliptic pdes. SIAM Journal on Matrix Analysis and Applications31, 2261–2290.
    [Google Scholar]
  8. ChandrasekaranS., DewildeP., GuM., LyonsW. and PalsT.2006. A fast solver for HSS representations via sparse matrices. SIAM Journal on Matrix Analysis and Applications29, 67–81.
    [Google Scholar]
  9. ChandrasekaranS., DewildeP., GuM., PalsT., SunX., van der VeenA. and WhiteD.2005. Some fast algorithms for sequentially semiseparable representations. SIAM Journal on Matrix Analysis and Applications27, 341–364.
    [Google Scholar]
  10. ChandrasekaranS., GuM. and PalsT.2006. A fast ULV decomposition solver for hierarchically semiseparable representations. SIAM Journal on Matrix Analysis and Applications28, 603–622.
    [Google Scholar]
  11. DuffI. and ReidJ.1983. The multifrontal solution of indefinite sparse symmetric linear equations. ACM Transactions on Mathematical Software9, 302–325.
    [Google Scholar]
  12. EidelmanY. and GohbergI.1999. On a new class of structured matrices. Integral Equations Operator Theory34, 293–324.
    [Google Scholar]
  13. EisenstatS. and LiuJ.2005. The theory of elimination trees for sparse unsymmetric matrices. SIAM Journal on Matrix Analysis and Applications26, 686–705.
    [Google Scholar]
  14. EngquistB. and YingL. Sweeping preconditioner for the helmholtz equation: hierarchical matrix representation. Communications in Pure and Applied Mathematics, to appear. http://www.math.utexas.edu/users/lexing/publications/sweephmf.pdf.
  15. ErlanggaY., OosterleeC. and VuikC.2006. A novel multigrid based preconditioner for heterogeneous Helmholtz problems. SIAM Journal on Scientific Computing27, 1471–1492.
    [Google Scholar]
  16. FuttermanW.1962. Dispersive body waves. Journal of Geophysical Research67, 5279–5291.
    [Google Scholar]
  17. GeorgeJ.1973. Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis10, 345–363.
    [Google Scholar]
  18. GilbertE.N.J.R.1993. Predicting Structure in Nonsymmetric Sparse Matrix Factorizations: Graph Theory and Sparse Matrix Computation . Springer‐Verlag.
    [Google Scholar]
  19. HackbuschW.2011. A sparse matrix arithmetic based on ‐matrices. Part I: Introduction to ‐matrices. Computing62, 89–108.
    [Google Scholar]
  20. HackbuschL.G.W. and BörmS.2002. An introduction to hierarchical matrices. Math. Bohem.127, 229–241.
    [Google Scholar]
  21. HackbuschW. and KhoromskijB.N.2000. A sparse ‐matrix arithmetic. Part‐II: Application to multi‐dimensional problems. Computing64, 21–47.
    [Google Scholar]
  22. HackbuschB.K.W. and SauterS.A.2003. On ‐matrices, Lectures on Applied Mathematics. Springer.
    [Google Scholar]
  23. HoffmanA., MartinM. and RoseD.1973. Complexity bounds for regular finite difference and finite element grids. SIAM Journal on Numerical Analysis10, 364–369.
    [Google Scholar]
  24. HustedtB., OpertoS. and VirieuxJ.2004. Mixed‐grid and staggered‐grid finite‐difference methods for frequency‐domain acoustic wave modeling. Geophysical Journal International157, 1269–1296.
    [Google Scholar]
  25. KjartanssonE.1979. Constant q‐wave propagation and attenuation. Journal of Geophysical Research84, 4737–4748.
    [Google Scholar]
  26. LiptonD.J.R.R.J. and TarjanR.E.1979. Generalized nested dissection, SIAM Journal on Numerical Analysis16, 346–358.
    [Google Scholar]
  27. LiuJ.1990. The role of elimination trees in sparse factorization. SIAM Journal on Matrix Analysis and Applications18, 134–172.
    [Google Scholar]
  28. LiuJ.1992. The multifrontal method for sparse matrix solution: Theory and practice. SIAM Review34, 82–109.
    [Google Scholar]
  29. OpertoS., VirieuxJ., AmestoyP., L'ExcellentJ., GiraudL. and HadjH.2007. Ali, 3D finite‐difference frequency‐domain modeling of visco‐acoustic wave propagation using a massively parallel direct solver: A feasibility study. Geophysics72, SM195–SM211.
    [Google Scholar]
  30. OpertoS., VirieuxJ., RibodettiA. and AndersonJ.2009. Finite‐difference frequency‐domain modeling of viscoacoustic wave propagation in 2D tilted transversely isotropic (TTI) media. Geophysics74, T75–T95.
    [Google Scholar]
  31. PlessixR.‐E.2007. A Helmholtz iterative solver for 3D seismic imaging problems. Geophysics72, SM185–SM194.
    [Google Scholar]
  32. RiyantiC., ErlanggaY., PlessixR.‐E., MulderW., VuikC. and OosterleeC.2006. A new iterative solver for the time‐harmonic wave equation. Geophysics71, E57–E63.
    [Google Scholar]
  33. RiyantiC., KononovA., ErlanggaY., VuikC., OosterleeC., PlessixR.‐E. and MulderW.2007. A parallel multigrid‐based preconditioner for the 3D heterogeneous high‐frequency Helmholtz equation. Journal of Computational Physics224, 431–448.
    [Google Scholar]
  34. TengS.1997. Fast nested dissection for finite element meshes. SIAM Journal on Matrix Analysis and Applications18, 552–565.
    [Google Scholar]
  35. TurkelE. and YefetA.1998. Absorbing PML boundary layers for wave‐like equations. Applied Numerical Mathematics27, 533–557.
    [Google Scholar]
  36. UrsinB. and ToverudT.2002. Comments on comparison of seismic dispersion and attenuation models by ursin b. and toverud, t. Studia Geophysica et Geodetica46, 293–320.
    [Google Scholar]
  37. WangS., de HoopM. and XiaJ.2010. Seismic inverse scattering via Helmholtz operator factorization and optimization. Journal of Computational Physics229, 8445–8462.
    [Google Scholar]
  38. XiaJ., ChandrasekaranS., GuM. and LiX.2010. Superfast multifrontal method for large structured linear systems of equations. SIAM Journal on Matrix Analysis and Applications31, 1382–1411.
    [Google Scholar]
  39. XiaJ., ChandrasekaranS., GuM. and LiX.2010. Fast algorithms for hierarchically semiseparable matrices. Numerical Linear Algebra Applications17, 953–976.
    [Google Scholar]
  40. XiaJ. Efficient structured multifrontal factorization for large sparse matrices, preprint, http://www.math.purdue.edu/~xiaj/work/mfhss.pdf.
http://instance.metastore.ingenta.com/content/journals/10.1111/j.1365-2478.2011.00982.x
Loading
On 3D modeling of seismic wave propagation via a structured parallel multifrontal direct Helmholtz solver
Geophysical Prospecting 59, 857 (2011); https://doi.org/10.1111/j.1365-2478.2011.00982.x
/content/journals/10.1111/j.1365-2478.2011.00982.x
/content/journals/10.1111/j.1365-2478.2011.00982.x
Loading

Data & Media loading...

  • Article Type: Research Article
Keyword(s): Helmholtz; HSS structure; massively parallel; modeling; multifrontal; rectangular domain

Most Cited This Month Most Cited RSS feed

This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error