1
$\begingroup$

In Finite Element Analysis, one requires to approximate the solution in terms of basis functions. My questions is, which method in general is better? by 'better', I mean which involves less number of unknowns to yield a certain accuracy? Let the solution of the problem be continuous and smooth in the domain of interest. I know this depends on the function which is to be approximated, But in general one of the methods should be superior. My guess is that B-splines require less number of unknowns because they do not require the all higher derivatives of the approximation be continuous as opposed to spectral elements. See e.g.

https://web.njit.edu/~vb82/Teaching/SPRING2016/MATH340Lab/Lab7/html/Lab7Solution_withfuncs.html

$\endgroup$
14
  • $\begingroup$ The least number of unknowns is for constant elements (one per element), which is essentially finite volumes or discontinuous galerkin. However the asymptotic convergence of those is not very good. Higher order polynomials have more degrees of freedom (e.g. in 2D: 1, 3, 6, 10, 15) and thus result in more unknowns, but at the same time they offer better convergence as the size of the elements decreases. So there is no "best", it depends on your setting. $\endgroup$
    – lightxbulb
    Aug 23, 2023 at 10:36
  • $\begingroup$ @lightxbulb I mean, the total number of unknowns in the whole domain, not the number of unknowns per element. $\endgroup$ Aug 23, 2023 at 12:01
  • 3
    $\begingroup$ Just counting DoFs is not a useful metric. If that's your goal, use a global Fourier basis. What matters more is how long it actually takes you to compute something with the basis you choose. $\endgroup$ Aug 23, 2023 at 19:38
  • 1
    $\begingroup$ @HoseinJavanmardi Choosing basis functions that aren't (as) almost-orthogonal (e.g. for higher order continuity) would make a tangent matrix more dense, which increases the computational effort to solve the system even if the the number of unknowns are unchanged. This is just to say that your definition of "better/superior" by just counting DOFs isn't typically what anyone else would care about, but rather how long it takes to solve. $\endgroup$ Aug 23, 2023 at 22:27
  • 1
    $\begingroup$ For a steady-state linear problem that discretizes to a system $Ax=b$, solving a $1{,}000\times1{,}000$ dense system will take far more time than even a $10{,}000\times10{,}000$ system that is very sparse. This is because the typical algorithms for solving these systems in PDE applications rely only on computing the matrix-vector products $Av$ instead of constructing $A^{-1}$ directly, so the biggest bottleneck is how fast you can compute $Av$, which is faster if $A$ is sparse. $\endgroup$
    – whpowell96
    Aug 24, 2023 at 15:19

1 Answer 1

3
$\begingroup$

Based on the comments below your post you may reach the conclusion that # DOFs and speed have no correlation whatsoever - this is not true. Keeping all other things fixed and increasing the number of unknowns it is clear that you would need to access more memory and perform more arithmetic operations. You don't need to trust me on that - you can test linear vs quadratic triangular elements where you have fixed the number of elements to be the same. The latter results in a slightly denser matrix and has more unknowns (# of vertices + # of edges versus just # of vertices for linear).

However the reason for choosing higher order polynomials is to get a better decrease rate of the error with the decrease of the size of the elements, so the goal for choosing higher order elements is slightly different. A fairer comparison there would be to compare linear elements on a mesh with $n$ vertices vs quadratic element on a mesh where the number of vertices plus edges sums up to $n$. Then you would expect the latter to get closer to the true solution as you decrease the element size.

In FEM if you have $m$ Dirichlet nodes and $(n-m)$ independent nodes, you get $n-m$ unknowns, and a (sparse) matrix that is $(n-m)\times (n-m)$. While you can grow the number of unknowns in order to get a better approximation, this generally also makes the solving process slower. If $m\ll n$ then you may opt to use Green's functions for the solution instead, which result in systems of size $m\times m$. These systems are typically dense, but as long as $m$ is small enough you can use a direct solver on those. The main practical issue there is whether you can construct the Green's functions efficiently. For example one can do so for the Poisson equation on a rectangular domain with a regular grid and with zero Dirichlet, reflecting, or periodic boundary conditions at the rectangle's boundaries, by using respectively the discrete sine, cosine, or Fourier transform (then the resulting solution strategy is typically termed fast Poisson solver. In the general case one has to compute columns of the generalised inverse of the non-reduced FDM/FEM/FVM matrix in order to get the Green's functions, so this can be more expensive than just running an iterative solver on the sparse formulation.

Discretisations based on the Green's function formulation are typically termed BEM or RBF based solutions in case you want to look those up. Typically a closed form solution for the Green's functions is not known for arbitrary meshings over arbitrary geometry however.

$\endgroup$
4
  • $\begingroup$ Thank you for sharing your knowledge. I understand that the number of unknowns is not the only measure of computational complexity. I am also aware of the benefits of sparse matrix (which is not the case of integral equation methods as you already mentioned). But If one is not able to make the matrix sparse, then the only choice to reduce computational time is to reduce the number of unknowns, Is that correct? $\endgroup$ Aug 24, 2023 at 16:44
  • 2
    $\begingroup$ @HoseinJavanmardi Beyond chaging the hardware or the solver yes, your problem scales in terms of the numbers of unknowns. In fact often as the matrix grows the condition number also grows, so iterative solvers becomes slower to converge. You can of course try to port your code to the GPU or use better solvers (e.g. multigrid, preconditioners, etc). $\endgroup$
    – lightxbulb
    Aug 24, 2023 at 19:06
  • $\begingroup$ I am scheduling to use BEM for 2-d potential problems. According to my reference articles, it is a promising work compared to FEM on PDE. That is why I need to use the basis functions which requires the least number of unknowns for a given accuracy. Thus far I doubt whether to use spectral elements or B-splines or the classic hat(tent) functions. Can you edit your answer based on my requirements? $\endgroup$ Aug 24, 2023 at 21:45
  • $\begingroup$ @HoseinJavanmardi You should probably make a separate question with all of the details concerning your problem: the PDE you're trying to solve, the discretisation of said problem, the hardware you plan to use (CPU or GPU), otherwise it's way too vague for anyone to say anything with certainty. What I can say about BEM, is that provided you know a fast way to compute the Green's functions, then you can take the best discretisation you can think of, since your matrix will be dense anyways. Also note that this is faster or even feasible only for a small enough number of Dirichlet nodes. $\endgroup$
    – lightxbulb
    Aug 25, 2023 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.