Grammar based multi-frontal solver for isogeometric analysis in 1d

• Autorzy: Kuźnik K. , Paszyński M , Calo V.
• Języki publikacji: EN

Abstrakty

EN

In this paper, we present a multi-frontal direct solver for one-dimensional iso-geometric finite element method. The solver implementation is based on the graph grammar (GG) model. The GG model allows us to express the entire solver algorithm, including generation of frontal matrices, merging, and eliminations as a set of basic undividable tasks called graph grammar productions. Having the solver algorithm expressed as GG productions, we can find the partial order of execution and create a dependency graph, allowing for scheduling of tasks into shared memory parallel machine. We focus on the implementation of the solver with NVIDIA CUDA on the graphic processing unit (GPU). The solver has been tested for linear, quadratic, cubic, and higher-order B-splines, resulting in logarithmic scalability.

Słowa kluczowe

EN

graph grammar; direct solver; isogeometric finite element method; NVIDIA CUDA GPU

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2013
• Tom: Vol. 14 (4)
• Strony: 589--613
• Opis fizyczny: Bibliogr. 26 poz., rys., wykr., tab.

Twórcy

autor

Kuźnik K.

• AGH University of Science and Technology, Department of Computer Sciences, Krakow, Poland

autor

Paszyński M

• AGH University of Science and Technology, Department of Computer Sciences, Krakow, Poland

autor

Calo V.

• King Abdullah University of Science and Technology, Thuwal, Saudi Arabia

Bibliografia

• [1] Amestoy P. R., Duff I. S., L’Excellent J.-Y.: Multifrontal parallel distributed symmetric and unsymmetric solvers. Computer Methods in Applied Mechancs and Engineering, 184, pp. 501–520, 2000.
• [2] Amestoy P. R., Duff I. S., Koster J., L’Excellent J.-Y.: A fully asynchronous multifrontal solver using distributed dynamic scheduling. SIAM Journal of Matrix Analysis and Applications, 23, 1, pp. 15–41, 2001
• [3] Amestoy P. R., Guermouche A., L’Excellent J.-Y., Pralet S.: Hybrid scheduling for the parallel solution of linear systems. Parallel Computing, 32, pp. 136–156, 2005.
• [4] Calo V., Gao L., Paszyński M.: Fast algorithms for explicit dynamics, In: 10th World Congress on Computational Mechanics, WCCM 2012, Sao Paolo, Brasil, 8–13 July, 2012.
• [5] Cottrel J. A., Hughes T. J. R., Bazilevs Y.: Isogeometric Analysis. Toward Integration of CAD and FEA, Wiley, 2009.
• [6] Demkowicz L.: Computing with hp-Adaptive Finite Element Method. Vol. I. One and Two Dimensional Elliptic and Maxwell Problems. Chapmann & Hall / CRC Applied Mathematics & Nonlinear Science, 2006.
• [7] Demkowicz L., Kurtz J., Pardo D., Paszyński M., Rachowicz W., Zdunek A.: Computing with hp-Adaptive Finite Element Method. Vol. II. Frontiers: Three Dimensional Elliptic and Maxwell Problems. Chapmann & Hall / CRC Applied & Nonlinear Science, 2007.
• [8] Duff I. S., Reid J. K.: The multifrontal solution of indefinite sparse symmetric linear systems. ACM Transactions on Mathematical Software, 9, pp. 302–325,1983.
• [9] Duff I. S., Reid J. K.: The multifrontal solution of unsymmetric sets of linear systems. SIAM Journal on Scientific and Statistical Computing , 5, pp. 633–641,1984.
• [10] Fialko S.: A block sparse shared-memory multifrontal finite element solver for problems of structural mechanics. Computer Assisted Mechanics and Engineering Sciences, 16, pp. 117–131, 2009.
• [11] Fialko S.: The block subtracture multifrontal method for solution of large finite element equation sets. Technical Transactions , 1-NP, 8, pp. 175–188, 2009.
• [12] Fialko S.: PARFES: A method for solving finite element linear equations on multi-core computers. Advances in Engineering Software, 40, 12, pp. 1256–1265, 2010.
• [13] Geng P., Oden T. J., van de Geijn R. A.: A Parallel Multifrontal Algorithm and Its Implementation. Computer Methods in Applied Mechanics and Engineering,149, pp. 289–301, 2006.
• [14] Giraud L., Marocco A., Rioual J.-C: Iterative versus direct parallel substructuring methods in semiconductor device modeling. Numerical Linear Algebra with Applications, 12: 1, pp. 33–55, 2005.
• [15] Irons B.: A frontal solution program for finite-element analysis. International Journal of Numerical Methods in Engineering, 2, pp. 5–32, 1970.
• [16] Kuźnik K., Paszyński M., Calo V.: Graph Grammar-Based Multi-Frontal Parallel Direct Solver for Two-Dimensional Isogeometric Analysis. Procedia Computer Science, 9, pp. 1454-1463, 2012.
• [17] Obrok P., Pierzchala P., Szymczak A., Paszyński M.: Graph grammar-based multi-thread multi-frontal parallel solver with trace theory-based scheduler, Proceedia Computer Science, 1, 1, pp. 1993–2001, 2010.
• [18] 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, 5545, pp. 875–884, 2009.
• [19] Paszyńska A., Paszyński M., Grabska E.: Graph transformations for modeling hp-adaptive Finite Element Method with triangular elements. Lecture Notes in Computer Science , 5103, pp. 604–613, 2008.
• [20] Paszyński M., Paszyńska A.: Graph transformations for modeling parallel hp-adaptive Finite Element Method. Lecture Notes in Computer Science, 4967, pp. 1313–1322, 2008.
• [21] Paszyński M., Pardo D., Torres-Verdin C., Demkowicz L., Calo V.: A Parallel Direct Solver for Self-Adaptive hp Finite Element Method.Journal of Parall and Distributed Computing, 70, pp. 270–281, 2010.
• [22] Paszyński M., Pardo D., Paszyńska A.: Parallel multi-frontal solver for p adaptive finite element modeling of multi-physics computational problems.Journal of Computational Science, 1, pp. 48–54, 2010.
• [23] Paszyński M., Schaefer R.: Graph grammar driven partial differential eqautions solver. Concurrency and Computations: Practise and Experience, 22, 9, pp. 1063–1097, 2010.
• [24] Scott J. A.: Parallel Frontal Solvers for Large Sparse Linear Systems. ACM Transaction on Mathematical Software, 29, 4, pp. 395-417, 2003.
• [25] Smith B. F., Bjørstad P., Gropp W.:Domain Decomposition, Parallel Multi-Level Methods for Elliptic Partial Differential Equations. Cambridge University Press, New York, 1st ed. 1996.
• [26] Szymczak A., Paszyński M.: Graph grammar based Petri net controlled direct sovler algorithm. Computer Science , 11, pp. 65–79, 2010.