GRAMMAR BASED MULTI-FRONTAL SOLVER FOR ISOGEOMETRIC ANALYSIS IN 1D
AbstractIn this paper we present multi-frontal direct solver for one dimensional isogeometric ﬁniteelement method. The solver implementation is based on graph-grammar (GG) model. TheGG model allows to express the entire solver algorithm, including generation of frontalmatrices, maerging and eliminations, as a set of basic undividable tasks called graph grammarproductions. Having the solver algorithm expressed as GG productions we can ﬁnd thepartial order of execution, and create the dependency graph allowing for scheduling of tasksinto shared memory parallel machine. We focus on the implementation of the solver withNVIDIA CUDA on the graphic processing unit (GPU). The solver has been tested for linear,quadratic, cubic and higher ordere B-splines, resulting in logarithmic scalability.
P. R. Amestoy, I. S. Duﬀ and J.-Y. L’Excellent, Multifrontal parallel distributed symmetric and unsymmetric solvers, in Comput. Methods in Appl. Mech. Eng. 184 (2000) 501-520.
P. R. Amestoy, I. S. Duﬀ, J. Koster and J.-Y. L’Excellent, A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM Journal of Matrix Analysis and Applications, 23, 1 (2001) 15-41.
P. R. Amestoy and A. Guermouche and J.-Y. L’Excellent and S. Pralet, Hybrid scheduling for the parallel solution of linear systems. Accepted to Parallel Computing (2005).
J. A.Cottrel, T. J. R. Hughes, Y. Bazilevs Isogeometric Analysis. Toward Integration of CAD and FEA, Wiley, 2009.
L. Demkowicz, 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.
L. Demkowicz, J. Kurtz, D. Pardo, M. Paszyński, W. Rachowicz, A. Zdunek Computing with hp-Adaptive Finite Element Method. Vol. II. Frontiers: Three Dimen-
sional Elliptic and Maxwell Problems. Chapmann & Hall / CRC Applied Mathematics & Nonlinear Science, 2007.
I. S. Duﬀ, J. K. Reid, The multifrontal solution of indeﬁnite sparse symmetric linear systems. ACM Transactions on Mathematical Software. 9, 1983; p. 302–325.
I. S. Duﬀ, J. K. Reid The multifrontal solution of unsymmetric sets of linear systems, SIAM Journal on Scientiﬁc and Statistical Computing, vol. 5, 1984; p.633–641.
S. Fialko, A block sparse shared-memory multifrontal ﬁnite element solver for problems of structural mechanics. Computer Assisted Mechanics and Engineering Sciences, 16, 2009; p. 117-131.
S. Fialko, The block subtracture multifrontal method for solution of large ﬁnite element equation sets. Technical Transactions, 1-NP, 8, 2009; p. 175–188.
S. Fialko, PARFES: A method for solving ﬁnite element linear equations on multicore computers. Advances in Engineering Software, 40, 12, 2010; p. 1256–1265.
P. Geng, T. J. Oden, R. A. van de Geijn; A Parallel Multifrontal Algorithm and Its Implementation, Computer Methods in Applied Mechanics and Engineering,
vol. 149, 2006; p.289–301.
L. Giraud, A. Marocco, J.-C. Rioual, Iterative versus direct parallel substructuring methods in semiconductor device modeling. Numerical Linear Algebra with Applications, 12, 1, 2005; p. 33–55.
B. Irons, A frontal solution program for ﬁnite-element analysis. International Journal of Numerical Methods in Engineering, 2, 1970; p. 5–32.
P. Obrok, P. Pierzchala, A. Szymczak, M. Paszyński Graph grammar-based multi thread multi-frontal parallel solver with trace theory-based scheduler, Proceedia
Computer Science, vol. 1 iss. 1, 2010; p.1993–2001.
A. Paszyńska, M. Paszyński, E. Grabska Graph transformations for modeling hp-adaptive Finite Element Method with mixed triangular and rectangular elements.
Lecture Notes in Computer Science vol. 5545, 2009; 875-884.
A. Paszyńska, M. Paszyński, E. Grabska Graph transformations for modeling hp-adaptive Finite Element Method with triangular elements. Lecture Notes in
Computer Science vol. 5103, 2008; 604–613.
M. Paszyński, A. Paszyńska, Graph transformations for modeling parallel hp-adaptive Finite Element Method . Lecture Notes in Computer Science vol. 4967,
M. Paszyński, D. Pardo, C. Torres-Verdin, L. Demkowicz, V. Calo A Parallel Direct Solver for Self-Adaptive hp Finite Element Method. Journal of Parall and Distributed Computing vol.70, 2010; p. 270–281.
M. Paszyński, D. Pardo, A. Paszyńska, Parallel multi-frontal solver for p adaptive ﬁnite element modeling of multi-physics computational problems. Journal of Computational Science 1, 2010; p. 48–54.
M. Paszyński, R. Schaefer Graph grammar driven partial diﬀerential eqautions solver. Concurrency and Computations: Practise and Experience vol.22 iss.9. 2010;p. 1063–1097.
J. A. Scott, Parallel Frontal Solvers for Large Sparse Linear Systems, ACM Trans. on Math. Soft., 29, 4 (2003) 395-417.
B. F. Smith, P. Bjørstad, W. Gropp, Domain decomposition, Parallel Multi-Level Methods for Elliptic Partial Diﬀerential Equations, Cambridge University Press,
New York, 1st ed. 1996.
A. Szymczak, M. Paszyński Graph grammar based Petri net controlled direct sovler algorithm. Computer Science vol.11, 2010; p.65–79.