Review of the Domain Decomposition Method in the Derived-Vector Space DDM-DVS and its Applicability to Nonsymmetric Matrices
Contenido principal del artículo
Resumen
En este trabajo se hace una revisión del Método de Descomposición de Dominio en el Espacio de Vectores Derivados DDM-DVS, propuesto por Herrera I. y desarrollado en (Herrera et al., 2014), extendiendo su aplicabilidad a matrices no simétricas. DDM-DVS o DVS framework es un DDM con subdominios sin traslape y sin nodos traslapados, diferenciándose de los Métodos Iterativos de Subestructuración estándares cuyos nodos de las fronteras entre subdominios están traslapados. Entonces el problema discretizado se resuelve en un espacio vectorial ampliado denominado Espacio Vectorial de Vectores Derivados (DVS). En este espacio, la matriz del sistema de ecuaciones es una matriz diagonal por bloques, lo cual da ventajas significativas para la implementación de algoritmos utilizando cómputo en paralelo de alto desempeño. Lo anterior permite que cada procesador resuelva independientemente un único subdominio. Las aportaciones de este trabajo al DVS-framework son el desarrollo de los métodos DVS-Schur y DVS-BDDC utilizando como resolvedor global BiCGstab. Estos métodos se estructuran en tres niveles: el primero para resolver globalmente nodos duales, el segundo para resolver globalmente nodos primales y el tercero para resolver localmente nodos del interior de subdominios. Se muestra que el complemento de Schur de la matriz del sistema de ecuaciones también es una matriz diagonal por bloques. Se demuestra la equivalencia del problema discretizado de forma estándar y utilizando DVS-framework. Se corrobora la superlinealidad de estos algoritmos y se explica mediante su complejidad algorítmica, estableciendo regiones de operación según la razón entre el número de nodos duales y de nodos de interior. Se muestran ejemplos con el operador diferencial general de segundo orden. La ecuación diferencial relacionada con este operador es relevante en Ciencias de la Tierra ya que representa el estado estacionario de la ecuación de transporte. Se logró resolver sistemas con 100,000,000 de grados de libertad, utilizando hasta 441 procesadores disponibles.
Publication Facts
Reviewer profiles N/D
Author statements
- Editor & editorial board
- profiles
- Academic society
- Geofísica Internacional
Para obtener más información sobre un dato, haga clic
PF is maintained by the Public Knowledge Project
Detalles del artículo
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
Citas
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 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 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). DOI: https://doi.org/10.1137/1.9781611974065
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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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. DOI: https://doi.org/10.1093/oso/9780198501787.001.0001
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 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 DOI: https://doi.org/10.1007/b137868
Trefethen, L. N. ., & Bau, David. (1997). Numerical linear algebra. Society for industrial and applied mathematics. DOI: https://doi.org/10.1137/1.9780898719574
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 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.