# What is the most efficient way to represent a 1D function using $hp$-finite element basis functions

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.

### Motivation

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.

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.
• 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$. – Wolfgang Bangerth Oct 18 '13 at 4:25
• 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$. – Ondřej Čertík Oct 18 '13 at 20:20