# Registered Data

## [02181] Numerical methods and analysis for linear systems and eigenvalue problems

**Session Date & Time**:- 02181 (1/2) : 3C (Aug.23, 13:20-15:00)
- 02181 (2/2) : 3D (Aug.23, 15:30-17:10)

**Type**: Proposal of Minisymposium**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.**Organizer(s)**: Lei Du, Hongjia Chen, Jintao Zhang**Classification**:__65F10__,__65F15__**Speakers Info**:- Yanfei Jing (University of Electronic Science and Technology of China)
**Lei Du**(Dalian University of Technology)- Ning Zheng (Tongji University)
- Ke Zhang (Shanghai Maritime University)
- Hongjia Chen (Nanchang University)
- Xiaoping Chen (Taizhou University)
- Guojian Yin (Shenzhen University)
- Jie Meng (Ocean University of China)

**Talks in Minisymposium**:**[03254] Interpretation of partial convergence from space partition for linear systems****Author(s)**:**Yanfei Jing**(University of Electronic Science and Technology of China)- Luc Giraud (Inria Bordeaux -- Sud-Ouest)
- Yanfei Xiang (Cerfacs, Inria Bordeaux -- Sud-Ouest)

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

**[03264] Computing eigenvalues of semi-infinite quasi-Toeplitz matrices****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****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.

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

**[04340] The FEAST algorithm accelerated by subspace expansion for eigenproblems****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.

**[04345] A Class of Randomized Block Reflective Kaczmarz Method for Linear Systems with Automatic Restart****Author(s)**:**Ning Zheng**(The Institute of Statistical Mathematics)- Junfeng Yin (Tongji University)
- Nan Li (Tongji University)
- Jichen Zhao (Tongji University)

**Abstract**: We propose novel deterministic and randomized block reflective Kaczmarz methods, which are based on the row partitions block Householder transformation, for solving linear systems. The convergence analysis on both consistent and inconsistent cases are discussed, which sheds light on why the reflective type method may converge slower than the projection type method. Subsequently, the proposed methods are restarted automatically to further speed up the convergence. Numerical experiments on the synthetic random problems and image restoration problems show the efficiency of the proposed methods.

**[04543] A variant algorithm of the IDR(s) method for solving linear systems****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.