Back to Search Start Over

A survey on direct solvers for Galerkin methods

A survey on direct solvers for Galerkin methods

Authors :
Pardo, David
Paszynski, Maciej
Collier, Nathan
Alvarez, Julen
Dalcin, Lisandro
Calo, Victor
Source :
SeMA Journal; January 2012, Vol. 57 Issue: 1 p107-134, 28p
Publication Year :
2012

Abstract

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, C0finite element discretizations are cheaper to solve with direct solvers than Cp-1discretizations.

Details

Language :
English
ISSN :
22543902
Volume :
57
Issue :
1
Database :
Supplemental Index
Journal :
SeMA Journal
Publication Type :
Periodical
Accession number :
ejs31069885
Full Text :
https://doi.org/10.1007/BF03322602