DOI: https://doi.org/10.26089/NumMet.v16r226

Solution of the Helmholtz problem using the preconditioned low-rank approximation technique

Authors

  • K.V. Voronin
  • S.A. Solovyev

Keywords:

3D Helmholtz problem
algorithms for sparse systems of linear algebraic equations
Gaussian elimination method
low-rank approximation
HSS matrix representation
BiCGStab method
iterative refinement

Abstract

An algorithm for solving the Helmholtz problem in 3D heterogeneous media using the low-rank approximation technique is proposed. This technique is applied as a preconditioner for two different iterative processes: an iterative refinement and BiCGStab. The iterative refinement approach is known to be very simple and straightforward but can suffer from the lack of convergence; BiCGStab is more stable and more sophisticated as well. A dependence of the convergence rate on low-rank approximation quality is studied for these iterative processes. For typical problems of seismic exploration, it is shown that, starting with some low-rank accuracy, the convergence rate of the iterative refinement is very similar to BiCGStab. Therefore, it is preferable to use the more efficient iterative refinement method. Numerical experiments also show that, for reasonable (from the practical standpoint) low-rank accuracy, the proposed method provides three times performance gain (for sequential code) and reduces the memory usage up to a factor of two in comparison with the Intel MKL PARDISO high performance direct solver.

New computational technologies

Downloads

Published

2015-05-24

Issue

Vol. 16 (2015): Issue 2.

Section

Section 1. Numerical methods and applications

Author Biographies

K.V. Voronin

The Institute of Computational Mathematics and Mathematical Geophysics of SB RAS (ICM&MG SB RAS)
• Engineer

S.A. Solovyev

Trofimuk Institute of Petroleum Geology and Geophysics of SB RAS
• Researcher

References

  1. N. S. Bakhvalov, Numerical Methods (Nauka, Moscow, 1973) [in Russian].
  2. M. A. Belonosov, K. Kostov, G. V. Reshetova, et al., “Parallel Computations for the Simulation of Seismic Waves on the Basis of the Additive Schwartz Method,” Vychisl. Metody Programm. 13, 525-535 (2012).
  3. K. G. Gadylshin and V. A. Tcheverda, “Nonlinear Least-Squares Full Waveform Inversion: SVD Analysis,” Vychisl. Metody Programm. 15, 499-513 (2014).
  4. A. F. Zaitseva and V. V. Lisitsa, “Influence of Perturbations in Transmission Conditions on the Convergence of the Domain Decomposition Method for the Helmholtz Equation,” Vychisl. Metody Programm. 15, 476-486 (2014).
  5. D. A. Neklyudov, I. Yu. Silvestrov, and V. A. Tcheverda, “A 3D Helmholtz Iterative Solver with a Semi-Analytical Preconditioner for Acoustic Wavefield Modeling in Seismic Exploration Problems,” Vychisl. Metody Programm. 15, 514-529 (2014).
  6. A. M. Matsokin and S. V. Nepomnyashchikh, “The Schwarz Alternation Method in a Subspace,” Izv. Vyssh. Uchebn. Zaved. Mat., No. 10, 61-66 (1985) [Russ. Math. 29 (10), 78-84 (1985)].
  7. S. A. Solovyev, “Application of the Low-Rank Approximation Technique in the Gauss Elimination Method for Sparse Linear Systems,” Vychisl. Metody Programm. 15, 441-460 (2014).
  8. R. P. Fedorenko, “A Relaxation Method for Solving Elliptic Difference Equations,” Zh. Vychisl. Mat. Mat. Fiz. 1 (5), 922-927 (1961) [USSR Comput. Math. Math. Phys. 1 (4), 1092-1096 (1962)].
  9. A. Al-Kurdi and D. R. Kincaid, “LU-Decomposition with Iterative Refinement for Solving Sparse Linear Systems,” J. Comput. Appl. Math. 185 (2), 391-403 (2006).
  10. D. N. Arnold, F. Brezzi, B. Cockburn, and L. D. Marini, “Unified Analysis of Discontinuous Galerkin Methods for Elliptic Problems,” SIAM J. Numer. Anal. 39 (5), 1749-1779 (2002).
  11. S. Asvadurov, V. Druskin, M. N. Guddati, and L. Knizhnerman, “On Optimal Finite-Difference Approximation of PML,” SAIM J. Numer. Anal. 41 (1), 287-305 (2003).
  12. S. Balay, S. Abhyankar, M. Adams, et al., PETSc Users Manual.Revision 3.5 , Technical Report ANL-95/11 (Argonne Nat. Lab., Argonne, 2015).
  13. M. A. Belonosov, C. Kostov, G. V. Reshetova, et al., “Parallel Numerical Simulation of Seismic Waves Propagation with Intel Math Kernel Library,” in Lecture Notes in Computer Science (Springer, Heidelberg, 2013), Vol. 7782, pp. 153-167.
  14. J.-P. Berenger, “A Perfectly Matched Layer for the Absorption of Electromagnetic Waves,” J. Comput. Phys. 114 (2), 185-200 (1994).
  15. R. Brossier, S. Operto, and J. Virieux, “Seismic Imaging of Complex Onshore Structures by 2D Elastic Frequency-Domain Full-Waveform Inversion,” Geophys. 74 (6), 105-118 (2009).
  16. S. Chandrasekaran, M. Gu, and T. Pals, “A Fast ULV Decomposition Solver for Hierarchically Semiseparable Representations,” SIAM J. Matrix Anal. Appl. 28 (3), 603-622 (2006).
  17. F. Collino and C. Tsogka, “Application of the Perfectly Matched Layer Absorbing Layer Model to the Linear Elastodynamic Problem in Anisotropic Heterogeneous Media,” Geophys. 66 (1), 294-307 (2001).
  18. Y. A. Erlangga, C. Vuik, and C. W. Oosterlee, “On a Class of Preconditioners for Solving the Helmholtz Equation,” Appl. Numer. Math. 50 (3-4), 409-425 (2004).
  19. O. G. Ernst and M. J. Gander, “Why it is Difficult to Solve Helmholtz Problems with Classical Iterative Methods,” in Lecture Notes in Computational Science and Engineering (Springer, Heidelberg, 2012), Vol. 83, pp. 325-363.
  20. M. J. Gander, L. Halpern, and F. Magoulès, “An Optimized Schwarz Method with Two-Sided Robin Transmission Conditions for the Helmholtz equation,” Int. J. Numer. Meth. Fluids 55 (2), 163-175 (2007).
  21. A. George, “Nested Dissection of a Regular Finite Element Mesh,” SIAM J. Numer. Anal. 10 (2), 345-363 (1973).
  22. S. A. Goreinov, E. E. Tyrtyshnikov, and N. L. Zamarashkin, “A Theory of Pseudo-Skeleton Approximations,” Linear Algebra Appl. 261 (1-3), 1-21 (1997).
  23. J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li, “Superfast Multifrontal Method for Large Structured Linear Systems of Equations,” SIAM J. Matrix Anal. Appl. 31 (3), 1382-1411 (2009).
  24. W. Hackbusch, “A Sparse Matrix Arithmetic Based on ℋ-Matrices. Part I: Introduction to H-Matrices,” Computing 62 (2), 89-108 (1999).
  25. HLIBpro.
    http://www.hlibpro.com/. Cited April 24, 2015.
  26. F. Kwok, “Optimized Additive Schwarz with Harmonic Extension as a Discretization of the Continuous Parallel Schwarz Method,” SIAM J. Numer. Anal. 49 (3), 1289-1316 (2011).
  27. V. Lisitsa, “Optimal Discretization of PML for Elasticity Problems,” Electron. Trans. Numer. Anal. 30, 258-277 (2008).
  28. S. Operto, J. Virieux, A. Ribodetti, and J. E. Anderson, “Finite-Difference Frequency-Domain Modeling of Viscoacoustic Wave Propagation in 2D Tilted Transversely Isotropic (TTI) Media,” Geophys. 2009. 74 (5), 75-95 (2009).
  29. S. Rjasanow, “Adaptive Cross Approximation of Dense Matrices,” in Proc. Int. Association for Boundary Element Methods, Austin, USA, May 28-30, 2002 (Univ. Texas at Austin, Austin, 2002), pp. 1-12.
  30. F.-H. Rouet, X. S. Li, and P. Ghysels, “A Distributed-Memory Package for Dense Hierarchically Semi-separable Matrix Computations Using Randomization,” ACM Trans. Math. Softw. 2014 (in press).
  31. Y. Saad, Iterative Methods for Sparse Linear Systems (SIAM, Philadelphia, 2003).
  32. K. Stüben, “A Review of Algebraic Multigrid,” J. Comput. Appl. Math. 128 (1-2), 281-309 (2001).
  33. S. Y. Suh, A. Yeh, B. Wang, et al., “Cluster Programming for Reverse Time Migration,” The Leading Edge 29 (1), 94-97 (2010).
  34. W. W. Symes, “Reverse Time Migration with Optimal Checkpointing,” Geophys. 72 (5), 213-221 (2007).
  35. L. L. Thompson, “A review of Finite-Element Methods for Time-Harmonic Acoustics,” J. Acoust. Soc. Am. 119 (3), 1315-1330 (2006).
  36. E. Tyrtyshnikov, “Mosaic-Skeleton Approximations,” Calcolo 33 (1-2), 47-57 (1996).
  37. H. A. van der Vorst, “Bi-CGStab: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems,” SIAM J. Sci. Stat. Comp. 13 (2), 631-644 (1992).
  38. J. Virieux, S. Operto, H. Ben-Hadj-Ali, et al., “Seismic Wave Modeling for Seismic Imaging,” The Leading Edge 28 (5), 538-544 (2009).
  39. J. Xia, “Robust and Efficient Multifrontal Solver for Large Discretized PDEs,” in High-Performance Scientific Computing (London, Springer, 2012), pp. 199-217.