概要: 数値線形代数(IDR法, 非線形固有値問題解法)に関する講演会です.
国立情報学研究所 12階 講義室1(1212) (アクセス)
National Institute of Informatics 12F Lecture room 1(1212) (access)
Lectures on Numerical Linear Algebra
You are all welcome to attend the following lectures.
Dr. Gerard L.G. Sleijpen,
Department of Mathematics,
Utrecht University, Netherlands
March 24th (Thursday)
講演題目(Title): IDR as a deflation method
IDR (Induced Dimension Reduction) is a family of efficient iterative
methods for the numerical solution of large non-symmetric systems of linear
equations Ax=b. Examples of IDR methods are Bi-CGSTAB (van der Vorst, SISC
1992), BiCGstab(ell) (Sleijpen and Fokkema, ETNA 1993) and BiCGStab2
(Gutknecht, SISC 1993) and the more recent methods, IDR(s) (Yeung and Chan,
SISC 1999, Sonneveld and van Gijzen, SISC 2008} and IDRstab (Sleijpen and
van Gijzen, SISC 2010, Tanio and Sugihara JCAM 2010); Bi-CGSTAB is
equivalent to the original IDR method of Sonneveld (in Wesseling
and Sonneveld, LNM 771, 1980). These IDR methods rely on short recurrences
and all iteration steps are equally fast. Often the convergence (in terms
of the number of multiplications of vectors by the matrix A) of the recent
versions is comparable to the convergence of GMRES.
In this talk the IDR method is interpreted in the context of deflation
methods. It is shown that IDR can be seen as a Richardson iteration
preconditioned by a variable deflation-type preconditioner.
The main result of this talk is the IDR projection theorem, which relates
the spectrum of the deflated system in each IDR cycle to all previous
cycles. The theorem shows that this so-called active spectrum becomes
increasingly more clustered. This clustering property may serve as an
intuitive explanation for the excellent convergence properties of IDR.
These remarkable spectral properties exist whilst using a deflation
subspace matrix of fixed rank.
The theoretical results are illustrated by numerical experiments.
This is joint work with
T. Collignon and Martin van Gijzen (Technical University Delft, Netherlands)
March 25th (Friday)
An SVD-Jacobi-Davidson approach to solution of
nonpolynomial integrated-optics eigenproblems
We consider nonlinear, nonpolynomial eigenvalue problems stemming from
a finite element discretization of the Helmholtz equation and arising in
a simulation of integrated optical devices.
We start with the Helmholtz eigenvalue problem
Delta E + omega^2 n(x,z)^2 E = 0,
posed in an infinite domain but to be solved numerically in a bounded
domain with artificial boundary conditions. These boundary conditions
can be of different types (and be called by different names, e.g.,
transparent, nonreflecting, absorbing). They guarantee transparency of
the domain boundary for outgoing waves. Here, we use transparent-influx
boundary conditions (TIBS) [Nicolau and Van Groesen, 2005]. These nonlocal
integral boundary conditions are obtained by solving the problem in the
exterior of the computational domain analytically. The approach has a
number of advantages as compared to other known formulations of
transparent or nonreflecting boundary conditions.
A finite element discretization of the Helmholtz equation leads to a
high dimensional eigenvalue problem
(S - lambda M + B(lambda))u=0, where lambda:=omega^2.
The TIBCs cause a nonlinear, nonpolynomial dependence of the matrix
B on the eigenvalue. Moreover, it is not trivial to express this
nonlinearity in an explicit way. However, since the nonlinearity results
from the boundary conditions, the matrix $B$ can be seen a smaller
dimensional discrete operator. This allows for a relatively cheap low-rank
SVD parametrization of the nonlinear dependence so that it can be
approximated by a low-degree matrix polynomial:
B(lambda) = B_0 + lambda B_1 + lambda^2 B_2 + ...
Thus, we reduce the nonlinear nonpolynomial eigenvalue problem to a
nonlinear polynomial one. Once this reduction is done, the Jacobi-Davidson
eigenvalue solver can readily be applied. Depending on the accuracy
requirements of the eigenvalue problem, the polynomial approximation can
be refined during the Jacobi-Davidson iterations.
This is joint work with:
Mike Botchev and Sena Sopaheluwakan,
University of Twente, Enschede, Netherlands
速水 謙 Ken Hayami (National Institute of Informatics)
〒101-8430 東京都千代田区一ツ橋 2-1-2 国立情報学研究所