University of Tokyo, 113, JAPAN

Abstract

In this paper, we propose a highly efficient accelerating method for
the restarted Arnoldi iteration to compute the eigenvalues of a large
nonsymmetric matrix. Its effectiveness is proved by various numerical
experiments and comparisons with other approaches. Several new
results on the characteristics of the polynomial acceleration are also
reported.

The Arnoldi iteration has been the most popular method for
nonsymmetric large eigenproblems. Although the defect of increasing
computational complexity per iteration step can be improved with the
explicitly restarting technique, by which the dimensions of the Krylov
subspaces are kept modest, the dimension of the subspace becomes
large, in particular when the required eigenvalues are clustered. In
our study, an accelerating polynomial is chosen to minimize an $L_2$
norm of the polynomial on the boundary of the convex hull with respect
to some suitable weight function. A new simple algorithm is proposed
for the efficient computation of the mini-max polynomial to accelerate
the convergence of the Arnoldi iteration.

>From the numerical results, we can derive the strong dependency of the
polynomial acceleration on the distribution of spectrum, which proves
the better performance of our algorithm than the Chebyshev
acceleration, in the cases where the moduli of the wanted eigenvalues
are considerably larger than those of the unwanted eigenvalues, and
the faster convergence than those of all the other approaches,
especially when the shape of the convex hull of the unwanted
eigenvalues bears little resemblance with an ellipse.

Finally, we propose a new parallelization technique for the
nonsymmetric double shifted QR algorithm with perfect load balance and
uninterrupted pipelining on distributed memory parallel architectures,
which is strongly required from the viewpoint of complexity of the
Arnoldi iteration. Its parallel efficiency is much higher than those
reported in other papers.

---------------------------------------------------------------------