A survey on direct solvers for Galerkin methods
Tóm tắt
In this paper we describe the history, performance, and design concepts of direct solvers for algebraic systems resulting from Galerkin discretizations of partial differential equations. Popular direct solver implementations of Gaussian elimination (also known as LU factorization) are introduced and briefly analyzed. We discuss three of the most relevant aspects influencing the performance of direct solvers on this kind of algebraic systems. First, the ordering of the degrees of freedom of the algebraic system has a significant impact on the solver performance, solution speed and memory requirements. The impact of unknowns ordering for elimination is exemplified and alternative ordering algorithms are described and compared. Second, the effect of round-off error on the simulation results is discussed. We detail this effect for uniform grids where the impact of round-off error on the solution is controlled by the condition number of the matrix in terms of the element size, but is independent of the polynomial order of approximation. Additionally, we discuss the link between unknown ordering and round-off error. Third, we describe the impact of the connectivity pattern (graph) of the basis functions on the performance of direct solvers. Variations in the connectivity structure of the resulting discrete system have severe impact on performance of the solver. That is, the resources needed to factorize the system strongly depend on its connectivity graph. Less connected graphs are cheaper to solve, that is, C0 finite element discretizations are cheaper to solve with direct solvers than Cp−1 discretizations.
Tài liệu tham khảo
I Akkerman, Y Bazilevs, V M Calo, T J R Hughes, and S Hulshoff. The role of continuity in residual-based variational multiscale modeling of turbulence. Computational Mechanics, 41(3):371–378, 2007.
AMD. Approximate Minimum Degree (AMD). Webpage http://www.cise.ufl.edu/research/sparse/amd/, 2011.
P. R. Amestoy, A. Guermouche, J.-Y. L’Excellent, and S. Pralet. Hybrid scheduling for the parallel solution of linear systems. Parallel Computing, 32:136–156, 2006.
P.R. Amestoy, T.A. Davis, I.S. Duff, et al. An approximate minimum degree ordering algorithm. SIAM Journal on Matrix Analysis and Applications, 17(4):886–905, 1996.
D. N. Arnold, R. S. Falk, and R. Winther. Multigrid in H(div) and H(curl). Numer. Math., 85(2): 197–217, 2000.
F. Auricchio, M. Conti, S. Morganti, and A. Reali. Shape memory alloys: from constitutive modeling to finite element analysis of stent deployment. Computer Modeling in Engineering & Sciences, 57:225–243, 2010.
I. Babuska, A. Craig, J. Mandel, and J. Pitkaranta. Efficient preconditioning for the p-version finite element method in two dimensions. SIAM J. Numer. Anal., 28(3):624–661, 1991.
Y Bazilevs, V Calo, J Cottrell, T Hughes, A Reali, and G Scovazzi. Variational multiscale residual-based turbulence modeling for large eddy simulation of incompressible flows. Computer Methods in Applied Mechanics and Engineering, 197(1–4): 173–201, 2007.
Y Bazilevs, V M Calo, Y Zhang, and T J R Hughes. Isogeometric Fluid Structure Interaction Analysis with Applications to Arterial Blood Flow. Computational Mechanics, 38(4–5):310–322, 2006.
Y Bazilevs, V.M. Calo, J.A. Cottrell, J.A. Evans, T.J.R. Hughes, S. Lipton, M.A. Scott, and T.W. Sederberg. Isogeometric analysis using T-splines. Computer Methods in Applied Mechanics and Engineering, page 34, 2010.
Y Bazilevs, J R Gohean, T J R Hughes, R D Moser, and Y Zhang. Patient-specific isogeometric fluid-structure interaction analysis of thoracic aortic blood flow due to implantation of the Jarvik 2000 left ventricular assist device. Computer Methods in Applied Mechanics and Engineering, 198(45–46):3534–3550, 2009.
Y Bazilevs, M Hsu, I Akkerman, S Wright, K Takizawa, and B Henicke. 3D simulation of wind turbine rotors at full scale. International Journal for Numerical Methods in Fluids, (August 2010):207–235, 2011.
Y Bazilevs, C Michler, V M Calo, and T J R Hughes. Isogeometric variational multiscale modeling of wall-bounded turbulent flows with weakly enforced boundary conditions on unstretched meshes. Computer Methods in Applied Mechanics and Engineering, 199(13–16):780–790, 2010.
P. Bientinesi, V. Eijkhout, K. Kim, J. Kurtz, and R. van de Geijn. Sparse Direct Factorizations through Unassembled Hyper-Matrices. Computer Methods in Applied Mechanics and Engineering, 199:430–438, 2010.
BLAS. Basic linear algebra subprograms. http://netlib.org/blas, 2011.
J. H. Bramble. Multigrid Methods. Pitman Research Notes in Mathematics Series. 294. Harlow: Longman Scientific & Technical. viii, 161 p., 1993.
F. Brezzi and M. Fortin. Mixed and Hybrid Finite Element Methods. Springer-Verlag, Berlin, 1991.
V M Calo, N F Brasher, Y Bazilevs, and T J R Hughes. Multiphysics model for blood flow and drug transport with application to patient-specific coronary artery flow. Computational Mechanics, 43(1): 161–177, 2008.
V.M. Calo, N. O. Collier, D. Pardo, and M. Paszyński. Computational complexity and memory usage for multi-frontal direct solvers used in p finite element analysis. Procedia Computer Science, 4:1854–1861, 2011.
V.M. Calo, H. Gomez, Y. Bazilevs, G.P. Johnson, and T.J.R. Hughes. Simulation of engineering applications using isogeometric analysis. In TeraGrid08, 2008.
GF Carey and E. Barragy. Basis function selection and preconditioning high degree finite element and spectral methods. BIT Numerical Mathematics, 29(4):794–804, 1989.
P.G. Ciarlet. The finite element method for elliptic problems. North-Holland, Amsterdam, 1978.
B. Cockburn, G.E. Karniadakis, and C.-W. Shu (Eds.). In Discontinuous Galerkin Methods, Lecture Notes in Computational Science and Engineering 11. Springer, Berlin, 2000.
N. Collier, D. Pardo, L. Dalcin, M. Paszynski, and V. M. Calo. The cost of continuity: a study of the performance of isogeometric finite elements using direct solvers. Computer Methods in Applied Mechanics and Engineering, submitted 2011.
N.O. Collier, M.R D. Pardo, Paszyński, and V.M. Calo. Computational complexity and memory usage estimates for multi-frontal direct solvers for structured finite elements. Journal of Computational Science, 2011. Submitted.
J A Cottrell, A Reali, Y Bazilevs, and T J R Hughes. Isogeometric analysis of structural vibrations. Computer Methods in Applied Mechanics and Engineering, 195(41–43):5257–5296, 2006.
J. Austin Cottrell, T. J. R. Hughes, and Yuri Bazilevs. Isogeometric Analysis: Toward Unification of CAD and FEA. John Wiley and Sons, 2009.
J.A. Cottrell, T.J.R. Hughes, and A. Reali. Studies of refinement and continuity in isogeometric structural analysis. Computer Methods in Applied Mechanics and Engineering, page 23, 2007.
L Dede, T J R Hughes, and S Lipton. Isogeometric Analysis of Topology Optimization Problems Based on the Phase-Field Model Design Optimization. Optimization, 45(3):1630–1633, 2011.
Luca Dede, T J R Hughes, Scott Lipton, and V M Calo. Structural topology optimization with isogeometric analysis in a phase field approach. In USNCTAM2010, 16th US National Congree of Theoretical and Applied Mechanics, 2010.
L. Demkowicz. Computing with hp-Adaptive Finite Elements. Volume I: One and Two Dimensional Elliptic and Maxwell Problems. Chapman and Hall, 2006.
L. Demkowicz, J. Kurtz, D. Pardo, M. Paszynski, W. Rachowicz, and A. Zdunek. Computing with hp-Adaptive Finite Elements. Volume II. Frontiers: Three-Dimensional Elliptic and Maxwell Problems with Applications. Chapman and Hall, 2007. chapters 8–12.
J.J. Dongarra, L.S. Duff, D.C. Sorensen, and H.A.V. Vorst. Numerical Linear Algebra for High Performance Computers. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1998.
I. S. Duff and J. K. Reid. The multifrontal solution of indefinite sparse symmetric linear. ACM Trans. Math. Softw., 9:302–325, 1983.
I. S. Duff and J. K. Reid. The multifrontal solution of unsymmetric sets of linear systems. SIAM J. Sci. Stat. Comput., 5:633–641, 1984.
A. El maliki, M. Fortin, N. Tardieu, and A. Fortin. Iterative solvers for 3d linear and nonlinear elasticity problems: Displacement and mixed formulations. International Journal for Numerical Methods in Engineering, 83:1780–1802, 2010.
M. Ferrari. Cancer nanotechnology: opportunities and challenges. Nature Reviews Cancer, 5(3):161–171, Mar 2005.
M. Ferrari. Nanovector therapeutics. Current Opinions in Chemical Biology, 9(4):343–346, August 2005.
P. Geng, T. J. Oden, and R. A. Van de Geijn. A parallel multifrontal algorithm and its implementation. Comput. Methods in Appl. Mech. Eng., 149:289–301, 1997.
A. George. Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis, pages 345–363, 1973.
A. George and J.W.H. Liu. The evolution of the minimum degree ordering algorithm. Siam review, pages 1–19, 1989.
M. Ghommem, M.R Hajj, D.T. Mook, B.K. Stanford, P.S. Beran, R.D. Snyder, and L.T. Watson. Global optimization of apping kinematics for micro air vehicles. Journal of Fluids and Structures, 2011. Under review.
M. Ghommem, M.R. Hajj, C. L. Pettit, and P.S. Beran. Stochastic modeling of incident gust effects on aerodynamic lift. Journal of Aircraft, 47(5): 1720–1729, 2010.
L. Giraud, A. Marocco, and Rioual J.-C. Iterative versus direct parallel substructuring methods in semiconductor device modeling. Numerical Linear Algebra with Applications, 12:33–55, 2005.
G.H. Golub and C.F. Van Loan. Matrix computations (3rd ed.). Johns Hopkins University Press, Baltimore, MD, USA, 1996.
J. Gopalakrishnan and G. Kanschat. A multilevel discontinuous galerkin method. Numerische Mathematik, 95:527–550, 2003. 10.1007/s002110200392.
N.I.M. Gould, J.A. Scott, and Y. Hu. A numerical evaluation of sparse direct solvers for the solution of large sparse symmetric linear systems of equations. ACM Trans. Math. Softw., 33, June 2007.
L. Grigori, J.W. Demmel, and X.S. Li. Parallel symbolic factorization for sparse LU with static pivoting. SIAM J. Scientific Computing, 29(3):1289–1314, 2007.
W. Hackbusch, L. Grasedyck, and S. Borm. An introduction to hierarchical matrices. Math. Bohem, 127(2):229–241, 2002.
R. Hiptmair. Multigrid method for Maxwell’s equations. SIAM J. Numer. Anal. 36(1):204–225, 1998.
A.J. Hoffman, M.S. Martin, and D.J. Rose. Complexity bounds for regular finite difference and finite element grids. SIAM Journal on Numerical Analysis, pages 364–369, 1973.
S. Hossain, S.F.A. Hossainy, Y. Bazilevs amd V.M. Calo, and T.J.R. Hughes. Mathematical modeling of coupled drug and drug-encapsulated nanoparticle transport in patient-specific coronary artery walls. Computational Mechanics, doi: 10.1007/s00466-011-0633-2, 2011.
HSL. Harwell Subroutine Library. http://www.cse.scitech.ac.uk/nag/hsl/, 2008.
M.-C. Hsu, I. Akkerman, and Y Bazilevs. High-performance computing of wind turbine aerodynamics using isogeometric analysis. Computers and Fluids, 2011.
T J R Hughes, A Reali, and G Sangalli. Efficient quadrature for NURBS-based isogeometric analysis. Computer Methods in Applied Mechanics and Engineering, 199(5–8):301–313, 2010.
T.J.R. Hughes. The finite element method: Linear static and dynamic finite element analysis. Prentice Hall, Englewood Cliffs, NJ, 1987.
T.J.R. Hughes, J.A. Cottrell, and Y. Bazilevs. Isogeometric analysis: CAD, finite elements, NURBS, exact geometry, and mesh refinement. Computer Methods in Applied Mechanics and Engineering, 194:4135–4195, 2005.
B. Irons. A frontal solution program for finite-element analysis. Int. J. Num. Meth. Eng., 2:5–32, 1970.
C. Johnson. Numerical solution of partial differential equations by the finite element method. Cambridge University Press, Sweden, 1987.
I. N. Katz, A. G. Peano, and M. P. Rossow. Nodal variables for complete conforming finite elements of arbitrary polynomial order. Computers Mathematics with Applications, 4:85–112, 1978.
K. Kim. Personal Communication, 2010.
D.A. LaVan, T. McGuire, and R. Langer. Small-scale systems for in vivo drug delivery. Nature Biotechnology, 21:1184–1191, 2003.
Luc L. Lavier and Gianreto Manatschal. A mechanism to thin the continental lithosphere at magma-poor margins. Nature, 440:324–328, 2006.
L. Lin, C. Yang, J. Lu, L. Ying, and E. Weinan. A fast parallel algorithm for selected inversion of structured sparse matrices wtih application to 2D electronic structure calculations. SIAM J. Scientific Computing, 33:1329–1351, 2011.
J.W.H. Liu. The multifrontal method for sparse matrix solution: Theory and practice. Siam Review, pages 82–109, 1992.
METIS. Family of Multilevel Partitioning Algorithms. http://glaros.dtc.umn.edu/gkhome/views/metis, 2007.
MUMPS. A multifrontal massively parallel sparse direct solver. http://graal.enslyon.fr/MUMPS/, 2010.
F. Nobile, R. T. Rockafellar, C. Schwab, R. F. Tempone, and R. J-B Wets. Ima annual program year workshop, 2011, computing with uncertainty: Mathematical modeling, numerical approximation and large scale optimization of complex systems with uncertainty. http://www.ima.umn.edu/2010-2011/W10.18-22.10/, 2011.
Intergovernmental Panel on Climate Change. http://srren.ipcc-wg3.de/, 2011.
Intergovernmental Panel on Climate Change. http://www.ipcc.ch/index.htm, 2011.
NSF Blue Ribbon Panel on Simulation-Based Engineering Science. www.nsf.gov/pubs/reports/sbes_final_report.pdf, 2006.
PARDISO. Thread-safe solver of linear equations. http://www.pardiso_project.org, 2008.
D. Pardo. Integration of hp-adaptivity with a two grid solver: applications to electromagnetics. PhD thesis, The University of Texas at Austin, April 2004.
D. Pardo, V. M. Calo, C. Torres-Verdín, and M. J. Nam. Fourier series expansion in a non-orthogonal system of coordinates for simulation of 3D DC borehole resistivity measurements. Computer Methods in Applied Mechanics and Engineering, 197(1–3): 1906–1925, 2008.
D. Pardo and L. Demkowicz. Integration of hp-adaptivity with a two grid solver for elliptic problems. Computer Methods in Applied Mechanics and Engineering, 195:674–710, 2006.
D. Pardo, L. Demkowicz, and J. Gopalakrishnan. Integration of hp-adaptivity and a two grid solver for electromagnetic problems. Computer Methods in Applied Mechanics and Engineering, 195:2533–2573, 2006.
D. Pardo, M. J. Nam, C. Torres-Verdín, M. Hoversten, and I. Garay. Simulation of Marine Controlled Source Electromagnetic (CSEM) Measurements Using a Parallel Fourier hp-Finite Element Method. Computational Geosciences, 15(1):53–67, 2011.
D. Pardo, C. Torres-Verdín, M. J. Nam, M. Paszynski, and V. M. Calo. Fourier series expansion in a non-orthogonal system of coordinates for simulation of 3D alternating current borehole resistivity measurements. Computer Methods in Applied Mechanics and Engineering, 197:3836–3849, 2008.
M. Paszyński, K. Kuźnik, and V.M. Calo. Graph grammar-based multi-frontal parallel direct solver for two-dimensional isogeometric analysis. Submitted to 26th IEEE International Parallel & Distributed Processing Symposium, Shanghai, China, May 21–25, 2012.
M. Paszyński, K. Kuźnik, and V.M. Calo. Grammar-based multi-frontal solver for isogeometric analysis in 1d. Scientific Programming, 2011. Submitted.
M. Paszyński, K. Kuźnik, and V.M. Calo. Parallel multi-frontal direct solver for isogeometric analysis of 2d problems. Computer Methods in Applied Mechanics and Engineering, 2011. Submitted.
M. Paszynski, D. Pardo, C. Torres-Verdin, L. Demkowicz, and V.M. Calo. A parallel direct solver for the self-adaptive hp finite element method. Journal of Parallel and Distributed Computing, 70(3):270–281, 2010.
A. G. Peano. Hierarchies of Conforming Finite Elements. PhD thesis, Sever Institute of Technology, Washington University, St. Luis, 1975.
A. G. Peano. Hierarchies of conforming finite elements for plane elasticity and plate bending. Computers Mathematics with Applications, 2:211–224, 1976.
L. Piegl and W. Tiller. The NURBS Book (Monographs in Visual Communication), 2nd ed. Springer-Verlag, New York, 1997.
ScaLAPACK. Scalable linear algebra package. http://netlib.org/scalapack, 2011.
P. Schmitz and L. Ying. A fast direct solver for elliptic problems on Cartesian meshes in 2d, submitted, 2011. http://www.math.utexas.edu/users/lexing/publications/index.html.
P. Schmitz and L. Ying. A fast direct solver for elliptic problems on Cartesian meshes in 3d, submitted, 2011. http://www.math.utexas.edu/users/lexing/publications/index.html.
J. Schulze. Towards a tighter coupling of bottom-up and top-down sparse matrix ordering methods. BIT, 41:2001, 2001.
SCOTCH. Graph partitioning, static mapping, and sparse matrix block ordering. http://www.labri.fr/perso/pelegrin/scotch/, 2011.
A. Scott. Parallel frontal solvers for large sparse linear systems. ACM Trans. on Math. Soft., 29: 395–417, 2003.
B. F. Smith, P. Bjorstad, and Gropp W. Domain Decomposition, Parallel Multi-Level Methods for Elliptic Partial Differential Equations. Cambridge University Press, New York, 1996.
SPOOLES. SParse Object Oriented Linear Equations Solver. http://www.netlib.org/linalg/spooles/spooles.2.2.html, 2011.
G. Stadler, M. Gurnis, C. Burstedde, L. C. Wilcox, L. Alisic, and O. Ghattas. The dynamics of plate tectonics and mantle flow: From local to global scales. Science, 329:1033–1038, 2010.
Super LU. A general purpose package for solution of large sparse systems of linear equations. http://crd.lbl.gov/%7Exiaoye/SuperLU/, 2008.
B. A. Szabo and I. Babuska. Finite Element Analysis. John Wiley and Sons, Ney York, 1991.
UMFPACK. Unsymmetric Multi-Frontal Package. http://www.cise.ufl.edu/research/sparse/umfpack/, 2011.
J. Xia, S. Chandrasekaran, M. Gu, and X.S. Li. Superfast multifrontal method for large structured linear systems of equations. SIAM J. Matrix Anal. Appl, 31(3): 1382–1411, 2009.