Abstract : In this mini-symposium, speakers will present recent developments in the numerical methods for linear systems and eigenvalue problems. The topics of interest include, iterative methods such as IDR(s) and randomized block Kaczmarz methods for linear systems with single right-hand side, and block GMRES-type solvers for linear systems with multiple right-hand sides, acceleration and preconditioning techniques for both linear and nonlinear eigenvalue problems, and algorithms for computing eigenvalues of semi‐infinite quasi‐Toeplitz matrices.
Abstract : Efficient solution of large-scale systems of linear equations with multiple right-hand sides is important. Partial convergence and inexact breakdown detection mechanism in the block classical GMRES method characterized by Robbe and Sadkane is a significant progress.
We interpret such partial convergence from space partition, providing flexible choices for approximation search subspace at each iteration.
Beyond, we report our recent progress in block GMRES-type solvers, and show the efficiency of our solvers by some typical numerical experiments..
[04340] The FEAST algorithm accelerated by subspace expansion for eigenproblems
Format : Talk at Waseda University
Author(s) :
Guojian Yin (Shenzhen University)
Abstract : The FEAST algorithm, a contour-integral based eigensolver, was developed for computing the eigenvalues inside a given region, along with their eigenvectors, of generalized eigenproblems. The FEAST algorithm is always fast, stable and easily parallelizable. It can be understood as an accelerated subspace iteration algorithm in conjunction with the Rayleigh–Ritz procedure. Unlike the classic subspace eigensolvers, the FEAST algorithm does not include a subspace expansion procedure when updating the search subspace but filters the search subspace iteratively using an approximate spectral projector. In this talk, I will introduce a subspace expansion scheme for the FEAST algorithm with the hope of producing a better search subspace and the improving convergence rate, especially when it comes to the ill-conditioned problems.
[03264] Computing eigenvalues of semi-infinite quasi-Toeplitz matrices
Format : Talk at Waseda University
Author(s) :
Dario Bini (University of Pisa)
Bruno Iannazzo (University of Perugia)
Beatrice Meini (University of Pisa)
Jie Meng (Ocean University of China)
Leonardo Robol (University of Pisa)
Abstract : A quasi-Toeplitz (QT) matrix is a semi-infinite matrix of the form $A=T(a)+E$ where $T(a)$ is the Toeplitz matrix with
entries $(T(a))_{i,j}=a_{j-i}$, for $a_{j-i}\in\mathbb C$, $i,j\ge 1$, while $E$ is a matrix representing a compact
operator in $\ell^2$. The matrix $A$ is finitely representable if $a_k=0$ for $k<-m$ and for $k>n$, given $m,n>0$, and if $E$ has a finite number of nonzero entries. The problem of numerically computing eigenpairs of a finitely
representable QT matrix is investigated, i.e., pairs $(\lambda, v)$ such that $A v=\lambda v$, with $\lambda\in\mathbb C$, $v=(v_j)_{j\in\mathbb Z^+}$, $ v\ne 0$, and $\sum_{j=1}^\infty |v_j|^2<\infty$. It is shown that the problem is
reduced to a finite nonlinear eigenvalue problemof the kind $ WU(\lambda) \beta=0$, where $W$ is a constant matrix and $U$ depends on $\lambda$ and can be given in terms of either a Vandermonde matrix or a companion matrix.
Algorithms relying on Newton's method applied to the equation $\det WU(\lambda)=0$ are analyzed. Numerical
experiments show the effectiveness of this approach.
[03454] Preconditioning techniques for nonlinear eigenvalue problem expressed in non-monomial basis
Format : Talk at Waseda University
Author(s) :
Hongjia Chen (Nanchang University)
Abstract : One of the most successful methods for solving a polynomial (PEP) or rational eigenvalue
problem (REP) is to recast it, by linearization, as an equivalent but larger generalized eigenvalue problem which can be solved by standard eigensolvers. In this work, we investigate the
backward errors of the computed eigenpairs incurred by the application of the well-received
compact rational Krylov (CORK) linearization. Our treatment is unified for the PEPs or REPs
expressed in various commonly used bases, including Taylor, Newton, Lagrange, orthogonal,
and rational basis functions. We construct one-sided factorizations that relate the eigenpairs
of the CORK linearization and those of the PEPs or REPs. With these factorizations, we establish upper bounds for the backward error of an approximate eigenpair of the PEPs or REPs
relative to the backward error of the corresponding eigenpair of the CORK linearization.
These bounds suggest scaling techniques to improve the accuracy of the computed eigenpairs.
We show, by numerical experiments, that the actual backward errors can be successfully
reduced by scaling and the errors, before and after scaling, are both well predicted by the
bounds.
[04543] A variant algorithm of the IDR(s) method for solving linear systems
Format : Talk at Waseda University
Author(s) :
Lei Du (Dalian University of Technology)
Abstract : The Induced Dimension Reduction method (IDR($s$) proposed by Sonneveld and van Gijzen is an efficient method for solving large, sparse and nonsymmetric linear systems, after then many variants have been proposed. The method has also been generalized to solve matrix equations and eigenvalue problems. In this talk, we consider using the Anderson acceleration technique and propose a new variant to accelerate the IDR($s$) method. Some numerical experiments are presented to show the efficiency of our proposed algorithm.
[03550] Randomized block Kaczmarz methods with k-means clustering for solving linear systems
Author(s) :
Ke Zhang (Shanghai Maritime University)
Xiang-Long Jiang (Shanghai Maritime University)
Junfeng Yin (Tongji University)
Abstract : In this talk, by following the philosophy of the block Kaczmarz methods, we propose a randomized block Kaczmarz method with the blocks determined by the k-means clustering. It can be considered as an efficient variant of the relaxed greedy randomized Kaczmarz algorithm by using a practical probability criterion for selecting the working block submatrix per iteration. The new algorithm is proved to be convergent when the linear system is consistent. A practical variant of the new method is also given. Some numerical examples are given to verify the effectiveness of the proposed methods.
