September 10, 2012
Polymath7 research threads 4: the Hot Spots Conjecture
Filed under: hot spots,research — Terence Tao @ 7:28 pm
It’s time for another rollover of the Polymath7 “Hot Spots” conjecture, as the previous research thread has again become full.
Activity has now focused on a numerical strategy to solve the hot spots conjecture for all acute angle triangles ABC. In broad terms, the strategy (also outlined in this document) is as follows. (I’ll focus here on the problem of estimating the eigenfunction; one also needs to simultaneously obtain control on the eigenvalue, but this seems to be to be a somewhat more tractable problem.)
- First, observe that as the conjecture is scale invariant, the only relevant parameters for the triangle ABC are the angles , which of course lie between 0 and and add up to . We can also order , giving a parameter space which is a triangle between the values .
- The triangles that are too close to the degenerate isosceles triangle or the equilateral triangle need to be handled by analytic arguments. (Preliminary versions of these arguments can be found here and Section 6 of these notes respectively, but the constants need to be made explicit (and as strong as possible)).
- For the remaining parameter space, we will use a sufficiently fine discrete mesh of angles ; the optimal spacing of this mesh is yet to be determined.
- For each triplet of angles in this mesh, we partition the triangle ABC (possibly after rescaling it to a reference triangle , such as the unit right-angled triangle) into smaller subtriangles, and approximate the second eigenfunction (or the rescaled triangle ) by the eigenfunction (or ) for a finite element restriction of the eigenvalue problem, in which the function is continuous and piecewise polynomial of low degree (probably linear or quadratic) in each subtriangle; see Section 2.2 of these notes. With respect to a suitable basis, can be represented by a finite vector .
- Using numerical linear algebra methods (such as Lanczos iteration) with interval arithmetic, obtain an approximation to , with rigorous bounds on the error between the two. This gives an approximation to or with rigorous error bounds (initially of L^2 type, but presumably upgradable).
- After (somehow) obtaining a rigorous error bound between and (or and ), conclude that stays far from its extremum when one is sufficiently far away from the vertices A,B,C of the triangle.
- Using stability theory of eigenfunctions (see Section 5 of these notes), conclude that stays far from its extremum even when is not at a mesh point. Thus, the hot spots conjecture is not violated away from the vertices. (This argument should also handle the vertex that is neither the maximum nor minimum value for the eigenfunction, leaving only the neighbourhoods of the two extremising vertices to deal with.)
- Finally, use an analytic argument (perhaps based on these calculations) to show that the hot spots conjecture is also not violated near an extremising vertex.
This all looks like it should work in principle, but it is a substantial amount of effort; there is probably still some scope to try to simplify the scheme before we really push for implementing it.
About these ads
Comments (103)
It seems that one of the weaker links in the above process, at least at our current level of understanding, is Step 6. If we had L^2 bounds on the residual , then one could get H^2 (and thence L^infty) bounds on the error , but with piecewise polynomial approximations that are only continuous at the edges, is going to have some singular components on the edges of the triangle and so L^2 bounds for the residual are not available.
On the other hand, if we get really good bounds for Step 6, then maybe these bounds would also work for perturbations of the triangle and we could skip Step 7.
Comment by Terence Tao — September 10, 2012 @ 7:36 pm
There are two pieces to Step 6.
part a. Denote as the discrete approximant of from the finite-dimensional subspace , where is computed by solving the discrete eigenvalue problem DVP2 exactly.
part b. Denote as the approximation of , computed using an iterative process for computing eigenfunctions of discrete systems.
What we need is a rigorous estimate on the residual , since what we have in hand is .
I think one can use inverse and duality estimates to compute the finite element residual , since is approximating a function, and can try to post some notes/references.
If we denote the quantity , then we want to be well-controlled. We only have in hand and , so the error estimate we want will have to boot-strap from these.
Apart from using interval arithmetic, I’m not sure how to proceed on this. Insight into part b. is key.
Comment by nilimanigam — September 12, 2012 @ 5:11 pm
One possibility is to not work with residuals, but instead with the Rayleigh quotient of (which is finite, because it only requires square integrability of the first derivative of w_h, not square integrability of the second derivative). If this Rayleigh quotient is known to be close to the true second eigenvalue , then is necessarily close in H^1 norm to a true second eigenfunction. On the plus side, this lets us skip Steps 6 and 7 (since the Rayleigh quotient is quite stable wrt perturbation of the triangle) and would be relatively simple to implement.
On the minus side, it only gives H^1 control on the true eigenfunction, which isn’t quite enough by itself to give L^infty control. But perhaps we can combine it with some elliptic regularity or something. For instance, in any disk in the triangle ABC, one can write the value of the eigenfunction at the centre of the the disk in terms of an integral on the disk involving a Bessel function. So if one has H^1 control on the eigenfunction in that disk, one gets pointwise control at the centre of the disk. If one is near an edge of the triangle, but not near a corner, one can do something similar after first applying a reflection. Things get worse near the corners, but we were planning to use a different argument for that case anyway (Step 8).
Another minus is that I suspect the dependence of the error on the mesh size is poor (something like the square root of the mesh size, perhaps). And it requires quite precise control on the second eigenvalue. But it may still be the lesser of two evils.
Comment by Terence Tao — September 14, 2012 @ 5:18 am
Let’s see. For a symmetric positive-definite , the Lanzcos iteration for the smallest eigenvalue of proceeds until a certain error criteria is met. This error criteria is based on the discrete Rayleigh quotient ($v$ is assumed to be normalized).
In our setting, the quantity is the quantity , where I am using the notation to be the element of constructed by using the coefficients in some basis.
In other words, the algorithm already minimizes the discrete Rayleigh quotient. The nature of the matrix tells us that the true discrete eigenvalue converges to the true one (for the continuous one) quadratically in the mesh size. The asymptotic constant depends on the true eigenvalue and the spectral gap. Eigenvectors converge quadratically with tesselation size in the H1 norm, eigenvalues converge quartically.
Backward error analysis tells us that the computed is close to the true for a given matrix size. The asymptotic constant again depends on the spectral gap. web.eecs.utk.edu/~dongarra/etemplates/node151.html
So I think we already have control, and I should attempt to explicitly string together the constants.
I suspect you may be right: since the asymptotic constants above for any FIXED triangle PQR depend on the spectral gap, and since this spectral gap varies as we change the angles of PQR, we may have poor control in terms of the angle parameters. But staring at the spectral gap plot
I am optimistic that away from the equilateral triangle one could actually make the dependence of asymptotic constants precise.
What’s harder to get a hand on is the residual of the computed (ie, not the finite element, but actually computed) eigenvector in terms of the direct application of the Laplacian.
Comment by nilimanigam — September 14, 2012 @ 6:45 pm
Here are some brief computations illustrating how an L^2 bound on the error in an approximate eigenfunction can be turned into L^infty bounds, at least if one is away from corners, thus avoiding the need to have to understand the residual.
More precisely, suppose that we have a true eigenfunction and some discretised approximation to this eigenfunction, and that we have somehow obtained a bound on the L^2 error (e.g. we should be able to get this if the Rayleigh quotient of is close to the minimum value of ).
Now suppose that the triangle ABC contains the disk for some radius R. A bit of messing around with polar coordinates shows that the function
is smooth on , equal to at the origin, and obeys the Bessel differential equation
which can be solved using Bessel functions as
thus
for all . Integrating this against a test function we get
Splitting into and and using Cauchy-Schwarz to bound the latter term, we obtain
.
This gives a computable upper and lower bound for . From the Cauchy-Schwarz inequality, we see that the optimal value of here is , leading to the bound
(1)
where
(2)
Of course, this estimate works best when R is large, and we can only fit a big ball B(0,R) inside the triangle ABC if the origin 0 is deep in the interior of ABC. But if instead 0 is near an edge of ABC, but far from the vertices, one can still get a big ball inside the domain after reflecting the triangle across the edge 0 is near (but this multiplies the L^2 norm of the residual by a factor of sqrt(2)). In principle, this gives L^infty control on u everywhere except near the corners. (Of course, one still has to numerically integrate the expressions in (1) and (2), but this looks doable, albeit messy.)
Comment by Terence Tao — September 20, 2012 @ 10:42 pm
This is really useful!
Here’s how I was trying to proceed:
Suppose u is the exact eigenfunction, and its exact projection onto the finite dimensional subspace . I was trying to compute the precise asymptotic constant in the sup-norm estimate (this is the kind of FEM estimate one gets, eg. page 3 of people.math.sfu.ca/~nigam/polymath-figures/Validation+Numerics.pdf), but I think your argument above may help with this.
One then has to estimate , where both now live in . I think this can be controlled using the inverse and backward error estimates for eigenvalue problems – the trick is getting the asymptotic constants decently. One then puts these estimates together
I’m also (still!) trying to debug the code to locate the extrema of the piecewise quadratics on the smaller triangles. This would circumvent the interpolation-to-linears step. The calculations are so very messy (not hard), so I’m going very slowly.