Решение уравнения Гельмгольца с использованием метода малоранговой аппроксимации в качестве предобусловливателя

Авторы

  • К.В. Воронин Институт вычислительной математики и математической геофизики СО РАН (ИВМиМГ СО РАН)
  • С.А. Соловьев Институт нефтегазовой геологии и геофизики имени А.А. Трофимука СО РАН

DOI:

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

Ключевые слова:

уравнение Гельмгольца, алгоритмы решения разреженных линейных систем, метод Гаусса, аппроксимация матрицами малого ранга, HSS-формат матриц, метод BCGStab, итерационное уточнение

Аннотация

Предложен алгоритм решения задачи Гельмгольца в трехмерных неоднородных средах с использованием метода аппроксимации матрицами малого ранга. Рассматриваемый метод применяется в качестве предобусловливателя для двух итерационных процессов. Первый — простой в реализации и экономичный метод итерационного уточнения, второй — метод BiCGStab крыловского типа. Скорость сходимости обоих методов исследуется относительно качества предобусловливателя, которое определяется точностью малоранговой аппроксимации. Показано, что для типичных задач сейсморазведки скорость сходимости двух рассматриваемых методов примерно одинакова начиная с некоторой точности малоранговой аппроксимации. Вычислительные эксперименты показали, что при точности, достаточной для решения практических задач, предложенный метод более чем в 2 раза экономнее по использованию памяти и в 3 раза производительнее, чем прямой метод PARDISO библиотеки Intel MKL.

Авторы

К.В. Воронин

С.А. Соловьев

Институт нефтегазовой геологии и геофизики имени А.А. Трофимука СО РАН
проспект Академика Коптюга, 3, 630090, Новосибирск
• научный сотрудник

Библиографические ссылки

  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.

Загрузки

Опубликован

24-05-2015

Как цитировать

Воронин К., Соловьев С. Решение уравнения Гельмгольца с использованием метода малоранговой аппроксимации в качестве предобусловливателя // Вычислительные методы и программирование. 2015. 16. 268-280. doi 10.26089/NumMet.v16r226

Выпуск

Раздел

Раздел 1. Вычислительные методы и приложения