HYPERGRAMMAR BASED PARALLEL MULTI-FRONTAL SOLVER FOR GRIDS WITH POINT SINGULARITIES

Piotr Gurgul; Maciej Paszynski; Anna Paszynska

doi:10.7494/csci.2015.16.1.75

Authors

Piotr Gurgul
Maciej Paszynski AGH University of Science and Technology
Anna Paszynska

DOI:

https://doi.org/10.7494/csci.2015.16.1.75

Abstract

This paper describes the application of hypergraph grammars to drive linear computationalcost solver for grids with point singularities. Such graph grammar productions are the rstmathematical formalism used to describe solver algorithm and each of them indicates thesmallest atomic task that can be executed in parallel, which is very useful in case of parallelexecution. In particular the partial order of execution of graph grammar productions can befound, and the sets of independent graph grammar productions can be localized. They canbe scheduled set by set into shared memory parallel machine. The graph grammar basedsolver has been implemented with NIVIDIA CUDA for GPU. Graph grammar productionsare accompanied by numerical results for 2D case. We show that our graph grammar basedsolver with GPU accelerator is order of magnitude faster than state of the art MUMPSsolver.

Downloads

Download data is not yet available.

References

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.

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.

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.

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.

Cottrel J. A., Hughes T. J. R., Bazilevs J.: Isogeometric Analysis. Toward Integration of CAD and FEA. Wiley, 2009.

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.

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.

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.

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.

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.

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.

Grabska E.: Theoretical Concepts of Graphical Modeling. Part Two: CP-Graph Grammars and Languages. Machine Graphics and Vision, vol. 2, pp. 149–178, 1993.

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.

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.

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.

Habel A., Kreowski H. J.: May we introduce to you: Hyperedge replacement. Lecture Notes in Computer Science, vol. 291, pp. 5–26, 1987.

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.

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.

Irons B.: A frontal solution program for finite-element analysis. International Journal of Numerical Methods in Engineering, vol. 2, pp. 5–32, 1970.

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.

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.

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.

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.

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.

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.

Rozenberg G.: Handbook of graph grammars and computing by graph transformation, vol I: Foundations. World Scientific, vol. 1997.

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.

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.

Ślusarczyk G., Paszyńska A.: Hypergraph grammars in hp-adaptive finite element method. Procedia Computer Science, pp. 1545–1554.

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.