Review of the Domain Decomposition Method in the Derived-Vector Space DDM-DVS and its Applicability to Nonsymmetric Matrices
Main Article Content
Abstract
This paper examines the Domain Decomposition Method in the Derived Vector Space (DDM-DVS), introduced by Herrera I. and further developed in Herrera et al., (2014), extending its applicability to nonsymmetric matrices. The DDM-DVS or DVS framework, is a domain decomposition method with non-overlapping subdomains and non-overlapping subdomains nodes, differing from standard Iterative Substructuring Methods, in which boundary nodes between subdomains are overlapping. The discretized problem is approached in an extended vector space known as the Derived Vector Space (DVS), where the system matrix is structured as a block diagonal matrix, enabling efficient high-performance parallel computing. This structure allows each processor to solve a single subdomain independently. This work contributes to the DVS framework introducing the DVS-Schur and DVS-BDDC methods, employing BiCGstab as the global solver. These methods operated in three levels: globally solving for dual nodes, globally solving for primal nodes, and locally solving for nodes inside (internal) the subdomains. It is demonstrated that the Schur complement of the system matrix is also block diagonal. The paper establishes the equivalence of the discretized problem through standard methods and within the DVS framework. The superlinear efficiency of the proposed algorithms is confirmed, with an analysis of their algorithmic complexity in relation to the ratio of dual to interior nodes. Additionally, the paper provides examples based on the general second-order differential operator, which is relevant in Earth Sciences for modeling the steady state of the transport equation. Systems with up to 100 million degrees of freedom were successfully solved using as many as 441 processors.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
References
Barney, B., & Frederick, D. (n.d.). Introduction to parallel computing tutorial. Lawrence Livermore National Laboratory.
Burden, R. L., Faires, J. D., & Burden, M. (2016). Numerical analysis (10th ed.). Cengage.
Carrillo, A. (2013). Métodos de descomposición de dominio en el espacio de vectores derivados y su implementación computacional en paralelo. [Tesis de Doctorado]. Universidad Nacional Autónoma de México.
Carrillo-Ledesma, A., Herrera, I., & de la Cruz, L. M. (2013). Parallel algorithms for computational models of geophysical systems. Geofísica Internacional, 52(3), 293–309. Doi: https://doi.org/10.1016/S0016-7169(13)71478-8
Contreras, I. (2016). Procesamiento en paralelo de sistemas de EDP’s. [Tesis de Doctorado]. Universidad Nacional Autónoma de México.
Coordinación de la Investigación Científica. (2024). Laboratorio universitario de cómputo de alto rendimiento. Coordinación de la Investigación Científica.
Cormen, T. H., Leiserson, C. Eric., Rivest, R. L. & Stein, Clifford. (2009). Introduction to algorithms. PHI Learning Private Limited.
De la Mora, A. (2021). Método de elemento finito con funciones óptimas: Caso de estudio: Ecuación de elasticidad. [Tesis de Doctorado]. Universidad Nacional Autónoma de México, Instituto de Geofísica.
Dohrmann, C. R. (2003). A Preconditioner for substructuring based on constrained energy minimization. SIAM Journal on scientific computing, 25(1), 246–258. doi: https://doi.org/10.1137/S1064827502412887
Dolean, Victorita., Jolivet, Pierre., & Nataf, F. (2015). An introduction to domain decomposition methods : algorithms, theory, and parallel implementation. Society for industrial and applied mathematics (SIAM, 3600 Market Street, Floor 6, Philadelphia, PA 19104).
Farhat, C., Lesoinne, M., LeTallec, P., Pierson, K., & Rixen, D. (2001). FETI‐DP: a dual–primal unified FETI method—part I: A faster alternative to the two‐level FETI method. International Journal for Numerical Methods in Engineering, 50(7), 1523–1544. doi: https://doi.org/10.1002/nme.76
Farhat, C., Lesoinne, M., & Pierson, K. (2000). A scalable dual-primal domain decomposition method. Numerical linear algebra with applications, 7(7–8), 687–714. doi: https://doi.org/10.1002/1099-1506(200010/12)7:7/8<687::AID-NLA219>3.0.CO;2-S
Herrera, I. (1985). Unified formulation of numerical methods. I. Green’s formulas for operators in discontinuous fields. Numerical methods for partial differential equations, 1(1), 25–44. doi: https://doi.org/10.1002/num.1690010105
Herrera, I. (2000). Trefftz method: A general theory. Numerical methods for partial differential equations, 16(6), 561–580. doi: https://doi.org/10.1002/1098-2426(200011)16:6<561::AID-NUM4>3.0.CO;2-V
Herrera, I. (2007). Theory of differential equations in discontinuous piecewise‐defined functions. Numerical methods for partial differential equations, 23(3), 597–639. doi: https://doi.org/10.1002/num.20182
Herrera, I., & Contreras, I. (2016). An innovative tool for effectively applying highly parallelized hardware to problems of elasticity. Geofísica Internacional, 55(1). doi: https://doi.org/10.22201/igeof.00167169p.2016.55.1.1710
Herrera, I., de la Cruz, L. M., & Rosas‐Medina, A. (2014). Nonoverlapping discretization methods for partial differential equations. Numerical methods for partial differential equations, 30(5), 1427–1454. doi: https://doi.org/10.1002/num.21852
Herrera, I., Keyes, D., Widlund, O., & Yates, R. (2003). Domain decomposition methods in science and engineering. Fourteenth International Conference on Domain Decomposition Methods, Cocoyoc, Mexico.
Herrera, I., & Pinder, G. F. (2012). Mathematical modeling in science and engineering. Wiley. doi: https://doi.org/10.1002/9781118207239
Herrera, I., & Rosas-Medina, A. A. (2013). The derived-vector space framework and four general purposes massively parallel DDM algorithms. Engineering analysis with boundary elements, 37(3), 646–657. doi: https://doi.org/10.1016/j.enganabound.2012.12.003
Herrera, I., & Yates, R. A. (2009). Unified multipliers‐free theory of dual‐primal domain decomposition methods. Numerical methods for partial differential equations, 25(3), 552–581. doi: https://doi.org/10.1002/num.20359
Herrera, I., & Yates, R. A. (2010). The multipliers‐free domain decomposition methods. Numerical methods for partial differential equations, 26(4), 874–905. doi: https://doi.org/10.1002/num.20462
Herrera, I., & Yates, R. A. (2011). Multipliers-free dual-primal domain decomposition methods for nonsymmetric matrices and their numerical testing. Numerical methods for partial differential equations, 27(5), 1262–1289. doi: https://doi.org/10.1002/num.20581
Herrera, I., Yates, R., & Diaz, M. (2002). General theory of domain decomposition: Indirect methods. Numerical methods for partial differential equations, 18(3), 296–322. doi: https://doi.org/10.1002/num.10008
Herrera, I., Yates, R., & Rubio, E. (2007). Collocation methods: More efficient procedures for applying collocation. Advances in engineering software, 38(10), 657–667. doi: https://doi.org/10.1016/j.advengsoft.2006.10.010
Herrera, I. (2021). The enhanced derived-vector-space Approach to domain decomposition methods. ArXiv.
Herrera‐Revilla, I. (2008). New formulation of iterative substructuring methods without Lagrange multipliers: Neumann–Neumann and FETI. Numerical methods for partial differential equations, 24(3), 845–878. doi: https://doi.org/10.1002/num.20293
Herrera-Revilla, I., Contreras, I., & S. Herrera, G. (2020). The divide-and-conquer framework: a suitable setting for domain decomposition methods of the future. Geofísica Internacional, 59(1), 27–37. doi: https://doi.org/10.22201/igeof.00167169p.2020.59.1.2078
Klawonn, A., Lanser, M., & Rheinbach, O. (2015). Toward extremely scalable nonlinear domain decomposition methods for elliptic partial differential equations. SIAM Journal on scientific computing, 37(6), C667–C696. doi: https://doi.org/10.1137/140997907
Kleinberg, Jon., & Tardos, E. (2006). Algorithm design. Pearson/Addison-Wesley.
Mandel, J. (1993). Balancing domain decomposition. Communications in numerical methods in engineering, 9(3), 233–241. doi: https://doi.org/10.1002/cnm.1640090307
Mandel, J., & Dohrmann, C. R. (2003). Convergence of a balancing domain decomposition by constraints and energy minimization. Numerical linear algebra with applications, 10(7), 639–659. doi: https://doi.org/10.1002/nla.341
Mandel, J., Dohrmann, C. R., & Tezaur, R. (2005). An algebraic theory for primal and dual substructuring methods by constraints. Applied numerical mathematics, 54(2), 167–193. doi: https://doi.org/10.1016/j.apnum.2004.09.022
Mathew, T. P. A. (2008). Domain decomposition methods for the numerical solution of partial differential equations (Vol. 61). Springer Berlin Heidelberg. doi: https://doi.org/10.1007/978-3-540-77209-5
Proceedings of Domain Decomposition Meetings. (n.d.). https://www.ddm.org/Proceedings.php
Quarteroni, Alfio., & Valli, A. (1999). Domain decomposition methods for partial differential equations. Clarendon Press.
Rubio, E. (2008). Métodos de elementos finitos con funciones óptimas. [Tesis de Doctorado]. Universidad Nacional Autónoma de México.
Saad, Y. (2003). Iterative methods for sparse linear systems. Society for industrial and applied mathematics. doi: https://doi.org/10.1137/1.9780898718003
SciPy Community. (2008). scipy.sparse.linalg.splu (Version 1.14.0).
Smith, B. F., Bjørstad, P. E., & Gropp, William. (2004). Domain decomposition : parallel multilevel methods for elliptic partial differential equations. Cambridge University Press.
Toselli, A., & Widlund, O. B. (2005). Domain decomposition methods—Algorithms and theory (Vol. 34). Springer Berlin Heidelberg. doi: https://doi.org/10.1007/b137868
Trefethen, L. N. ., & Bau, David. (1997). Numerical linear algebra. Society for industrial and applied mathematics.
Van Der Vorst, H. A. (1992). Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems. SIAM Journal on scientific and statistical computing, 13(2), 631–644. doi: https://doi.org/10.1137/0913035
Wilkinson, Barry., & Allen, C. Michael. (2005). Parallel programming: techniques and applications using networked workstations and parallel computers. Pearson/Prentice Hall.