Fast Leja Points

An applet would normally go here...

This page illustrates how fast Leja points are distributed on an interval. We allow the interval to be updated during the generation of fast Leja points. This situation occurs in applications of fast Leja points to large-scale eigenvalue computations; see Section 4.2 of the paper. You should see three boxes for specifying the input; two for the endpoints of the interval on which the fast Leja points are to be allocated, and one for the number of fast Leja points to be allocated. A very large or a very small interval and a large number of fast Leja points may give rise to overflow or underflow. We require the input to satisfy

left endpoint < right endpoint
0 < total number of fast Leja points < 500

Note that these restrictions do not guarantee that underflow or overflow is avoided. Intervals of length 4 have capacity 1 and allow the computations of a fairly large number of fast Leja points without underflow or overflow. The buttons immediately below the input fields work as follows:
  • Plot calculates new fast Leja points. The input fields determine the interval in which these points are allocated and their number. The new fast Leja points are displayed by red dots red dot in the graph below the ``Clear Data'' and ``Plot'' buttons. The distribution of the new Leja points depends on where previous fast Leja points have been allocated. The latter points are marked by blue dots blue dot. Clicking on the plot button repeatedly adds the same number of new Leja points for each successive ``click.'' It is possible to update the input fields during the generation of a sequence of new Leja points. A display window below the plot of the fast Leja points shows the numerical value of the fast Leja points in the order they are generated. The endpoints of the intervals specified in the input fields are also displayed.
  • Clear Data removes all the fast Leja points allocated. The current plot and display windows are erased.
Standard ``non-fast'' Leja points are used in several areas of Scientific Computing, such as for
  • polynomial interpolation,
  • iterative methods for the solution of large linear systems of equations, and
  • iterative methods for the computation of a few eigenvalues of large sparse matrices.
The computation of a large number of standard ``non-fast'' Leja points for an intervals [a,b] can be quite expensive, because the determination of each point requires the solution of an optimization problem on the interval [a,b]. In the computation of fast Leja points, the optimization over the interval is replaced by an optimization over a set of finitely many grid points. The number of grid points is proportional to the number of fast Leja points already allocated. The number of arithmetic floating point operations required to generate n fast Leja points therefore is proportional to only n2. This makes it possible to rapidly generate a large number of fast Leja points. When the interval is kept fixed, the plots show fast Leja points to be distributed like zeros of Chebyshev polynomials, with more points near the endpoints of the interval than in the middle. Many theoretical questions related to the distribution of fast Leja points require further attention.