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
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
.
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.
|