Hypergrammar-based parallel multi-frontal solver for grids with point singularities

• Autorzy: Gurgul P. , Paszyński M. , Paszyńska A.

Identyfikatory

DOI

10.7494/csci.2015.16.1.75

• Języki publikacji: EN

Abstrakty

EN

This paper describes the application of hypergraph grammars to drive a linear computational cost solver for grids with point singularities. Such graph grammar productions are the first mathematical formalisms used to describe solver algorithms, and each indicates the smallest atomic task that can be executed in parallel, which is very useful in the case of parallel execution. In particular,the partial order of execution of graph grammar productions can be found, and the sets of independent graph grammar productions can be localized. They can be scheduled set by set into a shared memory parallel machine. The graph-grammar-based solver has been implemented with NVIDIA CUDA for GPU. Graph grammar productions are accompanied by numerical results for a 2D case. We show that our graph-grammar-based solver with a GPU accelerator is, by order of magnitude, faster than the state-of-the-art MUMPS solver.

Słowa kluczowe

EN

hypergraph grammar; direct solver; h-adaptive finite element method; NVIDIA CUDA GPU

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2015
• Tom: Vol. 16 (1)
• Strony: 75--102
• Opis fizyczny: Bibliogr. 30 poz., rys., wykr.

Twórcy

autor

Gurgul P.

• AGH University of Science and Technology, Krakow, Poland

autor

Paszyński M.

• AGH University of Science and Technology, Krakow, Poland

autor

Paszyńska A.

• Jagiellonian University, Krakow, Poland

Bibliografia

• [1] Albers B., Savidis S., Tasan E., von Estorff O., Gehlken M.: BEM and FEM results of displacements in a poroelastic column. Journal of Applied Mathematics and Computer Science, vol. 22(4), pp. 883–896, 2012.
• [2] Barboteu M., Bartosz K., Kalita P.: An analytical and numerical approach to a bilateral contact problem with nonmonotone friction. Journal of Applied Mathematics and Computer Science, vol. 23(2), pp. 263–276, 2013.
• [3] Bazilevs Y., da Veiga L. B., Cottrell J. A., Hughes T. J. R., Sangalli G.: Isogeometric analysis: Approximation, stability and error estimates for h-refined meshes. Mathematical Methods and Models in Applied Sciences, vol. 16, pp. 1031–1090, 2006.
• [4] Colier N., Pardo D., Dalcin L., Calo V. M.: The cost of continuity: A study of the performance of isogeometric finite elements using direct solvers. Computer Methods in Applied Mechanics and Engineering, vol. 213, pp. 353–361, 2012.
• [5] Cottrel J. A., Hughes T. J. R., Bazilevs J.: Isogeometric Analysis. Toward Integration of CAD and FEA. Wiley, 2009.
• [6] David A., Hager W.: Dynamic supernodes in sparse cholesky update / downdate and triangular solves. ACM Transactions on Mathematical Software, vol. 35(4), pp. 1–23, 2009.
• [7] Demkowicz L.: Computing with hp-Adaptive Finite Elements, Vol. I. One and Two Dimensional Elliptic and Maxwell Problems. Chapman and Hall/Crc Applied Mathematics and Nonlinear Science, 2006.
• [8] Demkowicz L., Kurtz J., Pardo D., Paszyński M., Rachowicz W., Zdunek A.: Computing with hp-Adaptive Finite Elements, Vol. II. Frontiers: Three Dimensional Elliptic and Maxwell Problems with Applications. Chapman and Hall/Crc Applied Mathematics and Nonlinear Science, 2007.
• [9] Duff I. S., Reid J. K.: The multifrontal solution of indefinite sparse symmetric linear systems. ACM Transactions on Mathematical Software, vol. 9, pp. 302–325, 1983.
• [10] Duff I. S., Reid J. K.: The multifrontal solution of unsymmetric sets of linear systems. SIAM Journal on Scientific and Statistical Computing, vol. 5, pp. 633–641, 1984.
• [11] Flasiński M., Schaefer R.: Quasi context sensitive graph grammars as a formal model of FE mesh generation. Computer-Assisted Mechanics and Engineering Science, vol. 3, pp. 191–203, 1996.
• [12] Grabska E.: Theoretical Concepts of Graphical Modeling. Part Two: CP-Graph Grammars and Languages. Machine Graphics and Vision, vol. 2, pp. 149–178, 1993.
• [13] Gupta A.: Recent advances in direct methods for solving unsymmetric sparse systems of linear equations. ACM Transactions on Mathematical Software, vol. 28, pp. 301–324, 2002.
• [14] Gupta A., Gustavson F. G., Toledo J.: The design, implementation, and evaluation of a symmetric banded linear solver for distributed-memory parallel computers. ACM Transactions on Mathematical Software, vol. 24(1), pp. 74–101, 1998.
• [15] Gupta A., Karypis V., Kumar V.: Highly scalable parallel algorithms for sparse matrix factorization. IEEE Transactions on Parallel and Distributed Systems, vol. 8(5), pp. 502–520, 1997.
• [16] Habel A., Kreowski H. J.: May we introduce to you: Hyperedge replacement. Lecture Notes in Computer Science, vol. 291, pp. 5–26, 1987.
• [17] Habel A., Kreowski H. J.: Some structural aspects of hypergraph languages generated by hyperedge replacement. Lecture Notes in Computer Science, vol. 247, pp. 207–219, 1987.
• [18] Hild P.: A sign preserving mixed finite element approximation for contact problems. Journal of Applied Mathematics and Computer Science, vol. 21(3), pp. 487–498, 2011.
• [19] Irons B.: A frontal solution program for finite-element analysis. International Journal of Numerical Methods in Engineering, vol. 2, pp. 5–32, 1970.
• [20] Paszyńska A., Grabska E., Paszyński M.: A Graph Grammar Model of the hp Adaptive Three Dimensional Finite Element Method. Part I. Fundamenta Informaticae, vol. 114(2), pp. 149–182, 2012.
• [21] Paszynska A., Grabska E., Paszynski M.: A Graph Grammar Model of the hp Adaptive Three Dimensional Finite Element Method. Part II. Fundamenta Informaticae, vol. 114(2), pp. 183–201, 2012.
• [22] Paszyńska A., Paszyński M., Grabska E.: Graph Transformations for Modeling hp-Adaptive Finite Element Method with Mixed Triangular and Rectangular Elements. Lecture Notes in Computer Science, vol. 5545, pp. 875–884, 2009.
• [23] Paszyński M.: On the Parallelization of Self-Adaptive hp-Finite Element Methods Part I. Composite Programmable Graph GrammarModel. Fundamenta Informaticae, vol. 93(4), pp. 411–434, 2009.
• [24] Paszyński M., Pardo D., Calo V.: A direct solver with reutilization of LU factorizations for h-adaptive finite element grids with point singularities. Computers & Mathematics with Applications, vol. 65(8), pp. 1140–1151, 2013.
• [25] Paszyński M., Schaefer R.: Graph grammar-driven parallel partial differential equation solver. Concurrency and Computation: Practice and Experience, vol. 22(9), pp. 1063–1097, 2010.
• [26] Rozenberg G.: Handbook of graph grammars and computing by graph transformation, vol I: Foundations. World Scientific, vol. 1997.
• [27] Schmitz P., Ying L.: A fast direct solver for elliptic problems on general meshes in 2d. Journal of Computational Physics, vol. 231, pp. 1314–1338, 2012.
• [28] Sieniek M., Gurgul P., Magiera K., Skotniczny P.: Agent-oriented image processing with the hp-adaptive projection-based interpolation operator. Journal of Computational Science, vol. 4, pp. 1844–1853, 2011.
• [29] Ślusarczyk G., Paszyńska A.: Hypergraph grammars in hp-adaptive finite element method. Procedia Computer Science, pp. 1545–1554.
• [30] Szymczak A., Paszyńska A., Gurgul P., Paszyński M., Calo V.: Graph Grammar Based Direct Solver for hp-adaptive Finite Element Method with Point Singularities. Procedia Computer Science, vol. 18, pp. 1594–1603, 2013.