Given a one-dimensional function (let's say infinitely differentiable) and a prescribed accuracy of an L2 (or H1) norm, what is the optimal mesh and (in general arbitrary) polynomial orders on each element so that the approximation has the least degrees of freedom? (For example if I have three elements, of orders $p_1=2$, $p_2=4$ and $p_3=10$, then there are $p_1+p_2+p_3+1=2+4+10+1=17$ degrees of freedom.)

The answer are the polynomial orders and coordinates of the mesh.

In particular, does the most efficient representation have equal polynomial orders on all elements or not?

What is the algorithm to find this optimal representation?

Naive algorithm

For each total number of elements N=1, 2, 3, ..., we pick all combinations of polynomial orders $p_i$ (e.g. for N=3, we have (1, 1, 1), (2, 1, 1), (1, 2, 1), (1, 1, 2), (2, 2, 1), ..., (100, 1, 1), ...) and we optimize the coordinates of the mesh in order to minimize the L1 norm. A candidate is such a combination of mesh+orders, that has a lower L1 norm than prescribed. We only keep the candidate with the lowest degrees of freedom. We skip combinations of N and $p_i$ which have more degrees of freedom, so the algorithm must eventually terminate.


Examples of functions that I have in mind are numerical solutions of radial Schroedinger or Dirac equations on a finite interval (either as part of DFT or Hartree-Fock), as well as the various corresponding potentials. All these functions are infinitely differentiable and the numerical solver can solve those to arbitrary numerical accuracy. Then I set e.g. $10^{-6}$ in L2 norm and I want to know the most efficient representation in terms of $hp$-FEM degrees of freedom.


1 Answer 1


I don't know whether that's already published, but Peter Minev of the University of South Carolina has developed algorithms that produce $hp$ meshes that are provably within a fixed factor of the optimal number of degrees of freedom to represent a given function with a prescribed accuracy $\varepsilon$.

In general, it is quite clear that even for $C^\infty$ or analytic functions, the optimal mesh will not use the same polynomial degree everywhere. It is easy to conceive functions that will have large derivatives somewhere and be very smooth elsewhere, and if you don't ask for very small tolerances $\varepsilon$, then it's quite clear that you should use low and high polynomial degrees in these regions, respectively.

  • $\begingroup$ Actually, it's not clear to me at all, that one cannot simply use dense mesh where the high derivatives are and coarse mesh where they are low (and use the same polynomial order). $\endgroup$ Oct 16, 2013 at 14:58
  • 2
    $\begingroup$ Take a Gaussian on $[-10,10]$ and ask for the best way to approximate to $\varepsilon=0.1$ in, say, the $L_2$ norm. I'm quite certain that the best approach is to use a quadratic element in the middle and higher order polynomials to the sides. My point was that if $\varepsilon$ is "large" then I would imagine that you wouldn't want to use the same polynomial degree everywhere. I can't say with any kind of intuition that this will also be the case as $\varepsilon\rightarrow 0$. $\endgroup$ Oct 18, 2013 at 4:25
  • $\begingroup$ I see. If I have time, I'll try to write a program to do this. It would be interesting to see how the meshes change as $\epsilon\to0$. $\endgroup$ Oct 18, 2013 at 20:20
  • $\begingroup$ How are you going to know whether your mesh and degree assignment is optimal? You'll need to implement Minev's algorithm because that's the only one I know is asymptotically optimal up to a constant. $\endgroup$ Oct 20, 2013 at 2:57

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.