Zhongxiao Jia

Zhongxiao Jia, Qian Zhang

We investigate the SPAI and PSAI preconditioning procedures and shed light on two important features of them: (i) For the large linear system $Ax=b$ with $A$ irregular sparse, i.e., with $A$ having $s$ relatively dense columns, SPAI may be very costly to implement, and the resulting sparse approximate inverses may be ineffective for preconditioning. PSAI can be effective for preconditioning but may require excessive storage and be unacceptably time consuming; (ii) the situation is improved drastically when $A$ is regular sparse, that is, all of its columns are sparse. In this case, both SPAI and PSAI are efficient. Moreover, SPAI and, especially, PSAI are more likely to construct effective preconditioners. Motivated by these features, we propose an approach to making SPAI and PSAI more practical for $Ax=b$ with $A$ irregular sparse. We first split $A$ into a regular sparse $\tilde A$ and a matrix of low rank $s$. Then exploiting the Sherman--Morrison--Woodbury formula, we transform $Ax=b$ into $s+1$ new linear systems with the same coefficient matrix $\tilde A$, use SPAI and PSAI to compute sparse approximate inverses of $\tilde A$ efficiently and apply Krylov iterative methods to solve the preconditioned linear systems. Theoretically, we consider the non-singularity and conditioning of $\tilde A$ obtained from some important classes of matrices. We show how to recover an approximate solution of $Ax=b$ from those of the $s+1$ new systems and how to design reliable stopping criteria for the $s+1$ systems to guarantee that the approximate solution of $Ax=b$ satisfies a desired accuracy. Given the fact that irregular sparse linear systems are common in applications, this approach widely extends the practicability of SPAI and PSAI. Numerical results demonstrate the considerable superiority of our approach to the direct application of SPAI and PSAI to $Ax=b$.

Yi Huang, Zhongxiao Jia

LSQR, a Lanczos bidiagonalization based Krylov subspace iterative method, and its mathematically equivalent CGLS applied to normal equations system, are commonly used for large-scale discrete ill-posed problems. It is well known that LSQR and CGLS have regularizing effects, where the number of iterations plays the role of the regularization parameter. However, it has long been unknown whether the regularizing effects are good enough to find best possible regularized solutions. Here a best possible regularized solution means that it is at least as accurate as the best regularized solution obtained by the truncated singular value decomposition (TSVD) method. In this paper, we establish bounds for the distance between the $k$-dimensional Krylov subspace and the $k$-dimensional dominant right singular space. They show that the Krylov subspace captures the dominant right singular space better for severely and moderately ill-posed problems than for mildly ill-posed problems. Our general conclusions are that LSQR has better regularizing effects for the first two kinds of problems than for the third kind, and a hybrid LSQR with additional regularization is generally needed for mildly ill-posed problems. Exploiting the established bounds, we derive an estimate for the accuracy of the rank $k$ approximation generated by Lanczos bidiagonalization. Numerical experiments illustrate that the regularizing effects of LSQR are good enough to compute best possible regularized solutions for severely and moderately ill-posed problems, stronger than our theory predicts, but they are not for mildly ill-posed problems and additional regularization is needed.

Zhongxiao Jia, Bingyu Li

This paper concerns singular value decomposition (SVD)-based computable formulas and bounds for the condition number of the Total Least Squares (TLS) problem. For the TLS problem with the coefficient matrix $A$ and the right-hand side $b$, a new closed formula is presented for the condition number. Unlike an important result in the literature that uses the SVDs of both $A$ and $[A,\ b]$, our formula only requires the SVD of $[A,\ b]$. Based on the closed formula, both lower and upper bounds for the condition number are derived. It is proved that they are always sharp and estimate the condition number accurately. A few lower and upper bounds are further established that involve at most the smallest two singular values of $A$ and of $[A,\ b]$. Tightness of these bounds is discussed, and numerical experiments are presented to confirm our theory and to demonstrate the improvement of our upper bounds over the two upper bounds due to Golub and Van Loan as well as Baboulin and Gratton. Such lower and upper bounds are particularly useful for large scale TLS problems since they require the computation of only a few singular values of $A$ and $[A, \ b]$ other than all the singular values of them.

Zhongxiao Jia, Cen Li

Using a new analysis approach, we establish a general convergence theory of the Shift-Invert Residual Arnoldi (SIRA) method for computing a simple eigenvalue nearest to a given target $σ$ and the associated eigenvector. In SIRA, a subspace expansion vector at each step is obtained by solving a certain inner linear system. We prove that the inexact SIRA method mimics the exact SIRA well, that is, the former uses almost the same outer iterations to achieve the convergence as the latter does if all the inner linear systems are iteratively solved with {\em low} or {\em modest} accuracy during outer iterations. Based on the theory, we design practical stopping criteria for inner solves. Our analysis is on one step expansion of subspace and the approach applies to the Jacobi--Davidson (JD) method with the fixed target $σ$ as well, and a similar general convergence theory is obtained for it. Numerical experiments confirm our theory and demonstrate that the inexact SIRA and JD are similarly effective and are considerably superior to the inexact SIA.

Zhongxiao Jia, Yanfei Yang

In this paper, we propose new randomization based algorithms for large scale linear discrete ill-posed problems with general-form regularization: ${\min} \|Lx\|$ subject to ${\min} \|Ax - b\|$, where $L$ is a regularization matrix. Our algorithms are inspired by the modified truncated singular value decomposition (MTSVD) method, which suits only for small to medium scale problems, and randomized SVD (RSVD) algorithms that generate good low rank approximations to $A$. We use rank-$k$ truncated randomized SVD (TRSVD) approximations to $A$ by truncating the rank-$(k+q)$ RSVD approximations to $A$, where $q$ is an oversampling parameter. The resulting algorithms are called modified TRSVD (MTRSVD) methods. At every step, we use the LSQR algorithm to solve the resulting inner least squares problem, which is proved to become better conditioned as $k$ increases so that LSQR converges faster. We present sharp bounds for the approximation accuracy of the RSVDs and TRSVDs for severely, moderately and mildly ill-posed problems, and substantially improve a known basic bound for TRSVD approximations. We prove how to choose the stopping tolerance for LSQR in order to guarantee that the computed and exact best regularized solutions have the same accuracy. Numerical experiments illustrate that the best regularized solutions by MTRSVD are as accurate as the ones by the truncated generalized singular value decomposition (TGSVD) algorithm, and at least as accurate as those by some existing truncated randomized generalized singular value decomposition (TRGSVD) algorithms.

Tsung-Ming Huang, Zhongxiao Jia, Wen-Wei Lin

For a given subspace, the Rayleigh-Ritz method projects the large quadratic eigenvalue problem (QEP) onto it and produces a small sized dense QEP. Similar to the Rayleigh-Ritz method for the linear eigenvalue problem, the Rayleigh-Ritz method defines the Ritz values and the Ritz vectors of the QEP with respect to the projection subspace. We analyze the convergence of the method when the angle between the subspace and the desired eigenvector converges to zero. We prove that there is a Ritz value that converges to the desired eigenvalue unconditionally but the Ritz vector converges conditionally and may fail to converge. To remedy the drawback of possible non-convergence of the Ritz vector, we propose a refined Ritz vector that is mathematically different from the Ritz vector and is proved to converge unconditionally. We construct examples to illustrate our theory.

Zhongxiao Jia

For the large-scale linear discrete ill-posed problem $\min\|Ax-b\|$ or $Ax=b$ with $b$ contaminated by Gaussian white noise, the Lanczos bidiagonalization based Krylov solver LSQR and its mathematically equivalent CGLS, the Conjugate Gradient (CG) method implicitly applied to $A^TAx=A^Tb$, are most commonly used, and CGME, the CG method applied to $\min\|AA^Ty-b\|$ or $AA^Ty=b$ with $x=A^Ty$, and LSMR, which is equivalent to the minimal residual (MINRES) method applied to $A^TAx=A^Tb$, have also been choices. These methods exhibit typical semi-convergence feature, and the iteration number $k$ plays the role of the regularization parameter. However, there has been no definitive answer to the long-standing fundamental question: {\em Can LSQR and CGLS find 2-norm filtering best possible regularized solutions}? The same question is for CGME and LSMR too. At iteration $k$, LSQR, CGME and LSMR compute {\em different} iterates from the {\em same} $k$ dimensional Krylov subspace. A first and fundamental step towards to answering the above question is to {\em accurately} estimate the accuracy of the underlying $k$ dimensional Krylov subspace approximating the $k$ dimensional dominant right singular subspace of $A$. Assuming that the singular values of $A$ are simple, we present a general $\sinΘ$ theorem for the 2-norm distances between these two subspaces and derive accurate estimates on them for severely, moderately and mildly ill-posed problems. We also establish some relationships between the smallest Ritz values and these distances. Numerical experiments justify the sharpness of our results.

Zhongxiao Jia

For the large-scale linear discrete ill-posed problem $\min\|Ax-b\|$ or $Ax=b$ with $b$ contaminated by Gaussian white noise, there are four commonly used Krylov solvers: LSQR and its mathematically equivalent CGLS, the Conjugate Gradient (CG) method applied to $A^TAx=A^Tb$, CGME, the CG method applied to $\min\|AA^Ty-b\|$ or $AA^Ty=b$ with $x=A^Ty$, and LSMR, the minimal residual (MINRES) method applied to $A^TAx=A^Tb$. These methods have intrinsic regularizing effects, where the number $k$ of iterations plays the role of the regularization parameter. In this paper, we establish a number of regularization properties of CGME and LSMR, including the filtered SVD expansion of CGME iterates, and prove that the 2-norm filtering best regularized solutions by CGME and LSMR are less accurate than and at least as accurate as those by LSQR, respectively. We also prove that the semi-convergence of CGME and LSMR always occurs no later and sooner than that of LSQR, respectively. As a byproduct, using the analysis approach for CGME, we improve a fundamental result on the accuracy of the truncated rank $k$ approximate SVD of $A$ generated by randomized algorithms, and reveal how the truncation step damages the accuracy. Numerical experiments justify our results on CGME and LSMR.

Zhongxiao Jia

LSQR and its mathematically equivalent CGLS have been popularly used over the decades for large-scale linear discrete ill-posed problems, where the iteration number $k$ plays the role of the regularization parameter. It has been long known that if the Ritz values in LSQR converge to the large singular values of $A$ in natural order until its semi-convergence then LSQR must have the same the regularization ability as the truncated singular value decomposition (TSVD) method and can compute a 2-norm filtering best possible regularized solution. However, hitherto there has been no definitive rigorous result on the approximation behavior of the Ritz values in the context of ill-posed problems. In this paper, for severely, moderately and mildly ill-posed problems, we give accurate solutions of the two closely related fundamental and highly challenging problems on the regularization of LSQR: (i) How accurate are the low rank approximations generated by Lanczos bidiagonalization? (ii) Whether or not the Ritz values involved in LSQR approximate the large singular values of $A$ in natural order? We also show how to judge the accuracy of low rank approximations reliably during computation without extra cost. Numerical experiments confirm our results.

Zhongxiao Jia, Cen Li

This paper concerns the harmonic shift-invert residual Arnoldi (HSIRA) and Jacobi--Davidson (HJD) methods as well as their refined variants RHSIRA and RHJD for the interior eigenvalue problem. Each method needs to solve an inner linear system to expand the subspace successively. When the linear systems are solved only approximately, we are led to the inexact methods. We prove that the inexact HSIRA, RHSIRA, HJD and RHJD methods mimic their exact counterparts well when the inner linear systems are solved with only low or modest accuracy. We show that (i) the exact HSIRA and HJD expand subspaces better than the exact SIRA and JD and (ii) the exact RHSIRA and RHJD expand subspaces better than the exact HSIRA and HJD. Based on the theory, we design stopping criteria for inner solves. To be practical, we present restarted HSIRA, HJD, RHSIRA and RHJD algorithms. Numerical results demonstrate that these algorithms are much more efficient than the restarted standard SIRA and JD algorithms and furthermore the refined harmonic algorithms outperform the harmonic ones very substantially.

Yi Huang, Zhongxiao Jia

For large scale symmetric discrete ill-posed problems, MINRES and MR-II are often used iterative regularization solvers. We call a regularized solution best possible if it is at least as accurate as the best regularized solution obtained by the truncated singular value decomposition (TSVD) method. In this paper, we analyze their regularizing effects and establish the following results: (i) the filtered SVD expression are derived for the regularized solutions by MINRES; (ii) a hybrid MINRES that uses explicit regularization within projected problems is needed to compute a best possible regularized solution to a given ill-posed problem; (iii) the $k$th iterate by MINRES is more accurate than the $(k-1)$th iterate by MR-II until the semi-convergence of MINRES, but MR-II has globally better regularizing effects than MINRES; (iv) bounds are obtained for the 2-norm distance between an underlying $k$-dimensional Krylov subspace and the $k$-dimensional dominant eigenspace. They show that MR-II has better regularizing effects for severely and moderately ill-posed problems than for mildly ill-posed problems, and a hybrid MR-II is needed to get a best possible regularized solution for mildly ill-posed problems; (v) bounds are derived for the entries generated by the symmetric Lanczos process that MR-II is based on, showing how fast they decay. Numerical experiments confirm our assertions. Stronger than our theory, the regularizing effects of MR-II are experimentally shown to be good enough to obtain best possible regularized solutions for severely and moderately ill-posed problems.

Jinzhi Huang, Zhongxiao Jia

We make a convergence analysis of the harmonic and refined harmonic extraction versions of Jacobi-Davidson SVD (JDSVD) type methods for computing one or more interior singular triplets of a large matrix $A$. At each outer iteration of these methods, a correction equation, i.e., inner linear system, is solved approximately by using iterative methods, which leads to two inexact JDSVD type methods, as opposed to the exact methods where correction equations are solved exactly. Accuracy of inner iterations critically affects the convergence and overall efficiency of the inexact JDSVD methods. A central problem is how accurately the correction equations should be solved so as to ensure that both of the inexact JDSVD methods can mimic their exact counterparts well, that is, they use almost the same outer iterations to achieve the convergence. In this paper, similar to the available results on the JD type methods for large matrix eigenvalue problems, we prove that each inexact JDSVD method behaves like its exact counterpart if all the correction equations are solved with $low\ or\ modest$ accuracy during outer iterations. Based on the theory, we propose practical stopping criteria for inner iterations. Numerical experiments confirm our theory and the effectiveness of the inexact algorithms.

Zhongxiao Jia, Yuquan Sun

We investigate the generalized second-order Arnoldi (GSOAR) method, a generalization of the SOAR method proposed by Bai and Su [{\em SIAM J. Matrix Anal. Appl.}, 26 (2005): 640--659.], and the Refined GSOAR (RGSOAR) method for the quadratic eigenvalue problem (QEP). The two methods use the GSOAR procedure to generate an orthonormal basis of a given generalized second-order Krylov subspace, and with such basis they project the QEP onto the subspace and compute the Ritz pairs and the refined Ritz pairs, respectively. We develop implicitly restarted GSOAR and RGSOAR algorithms, in which we propose certain exact and refined shifts for respective use within the two algorithms. Numerical experiments on real-world problems illustrate the efficiency of the restarted algorithms and the superiority of the restarted RGSOAR to the restarted GSOAR. The experiments also demonstrate that both IGSOAR and IRGSOAR generally perform much better than the implicitly restarted Arnoldi method applied to the corresponding linearization problems, in terms of the accuracy and the computational efficiency.

Zhongxiao Jia, Qian Zhang

Dropping tolerance criteria play a central role in Sparse Approximate Inverse preconditioning. Such criteria have received, however, little attention and have been treated heuristically in the following manner: If the size of an entry is below some empirically small positive quantity, then it is set to zero. The meaning of "small" is vague and has not been considered rigorously. It has not been clear how dropping tolerances affect the quality and effectiveness of a preconditioner $M$. In this paper, we focus on the adaptive Power Sparse Approximate Inverse algorithm and establish a mathematical theory on robust selection criteria for dropping tolerances. Using the theory, we derive an adaptive dropping criterion that is used to drop entries of small magnitude dynamically during the setup process of $M$. The proposed criterion enables us to make $M$ both as sparse as possible as well as to be of comparable quality to the potentially denser matrix which is obtained without dropping. As a byproduct, the theory applies to static F-norm minimization based preconditioning procedures, and a similar dropping criterion is given that can be used to sparsify a matrix after it has been computed by a static sparse approximate inverse procedure. In contrast to the adaptive procedure, dropping in the static procedure does not reduce the setup time of the matrix but makes the application of the sparser $M$ for Krylov iterations cheaper. Numerical experiments reported confirm the theory and illustrate the robustness and effectiveness of the dropping criteria.

Zhongxiao Jia, Yanfei Yang

Based on the joint bidiagonalization process of a large matrix pair $\{A,L\}$, we propose and develop an iterative regularization algorithm for the large scale linear discrete ill-posed problems in general-form regularization: $\min\|Lx\| \ \mbox{\rm subject to} \ x\in\mathcal{S} = \{x|\ \|Ax-b\|\leq τ\|e\|\}$ with a Gaussian white noise $e$ and $τ>1$ slightly, where $L$ is a regularization matrix. Our algorithm is different from the hybrid one proposed by Kilmer {\em et al.}, which is based on the same process but solves the general-form Tikhonov regularization problem: $\min_x\left\{\|Ax-b\|^2+λ^2\|Lx\|^2\right\}$. We prove that the iterates take the form of attractive filtered generalized singular value decomposition (GSVD) expansions, where the filters are given explicitly. This result and the analysis on it show that the method must have the desired semi-convergence property and get insight into the regularizing effects of the method. We use the L-curve criterion or the discrepancy principle to determine $k^*$. The algorithm is simple and effective, and numerical experiments illustrate that it often computes more accurate regularized solutions than the hybrid one.

Zhongxiao Jia

For the large-scale linear discrete ill-posed problem $\min\|Ax-b\|$ or $Ax=b$ with $b$ contaminated by a white noise, the Lanczos bidiagonalization based LSQR method and its mathematically equivalent Conjugate Gradient (CG) method for $A^TAx=A^Tb$ are most commonly used. They have intrinsic regularizing effects, where the number $k$ of iterations plays the role of regularization parameter. However, there has been no answer to the long-standing fundamental concern by Björck and Eldén in 1979: for which kinds of problems LSQR and CGLS can find best possible regularized solutions? Here a best possible regularized solution means that it is at least as accurate as the best regularized solution obtained by the truncated singular value decomposition (TSVD) method or standard-form Tikhonov regularization. In this paper, assuming that the singular values of $A$ are simple, we analyze the regularization of LSQR for severely, moderately and mildly ill-posed problems. We establish accurate estimates for the 2-norm distance between the underlying $k$-dimensional Krylov subspace and the $k$-dimensional dominant right singular subspace of $A$. For the first two kinds of problems, we then prove that LSQR finds a best possible regularized solution at semi-convergence occurring at iteration $k_0$ and that, for $k=1,2,\ldots,k_0$, (i) the $k$-step Lanczos bidiagonalization always generates a near best rank $k$ approximation to $A$; (ii) the $k$ Ritz values always approximate the first $k$ large singular values in natural order; (iii) the $k$-step LSQR always captures the $k$ dominant SVD components of $A$. For the third kind of problem, we prove that LSQR generally cannot find a best possible regularized solution. Numerical experiments confirm our theory.

Zhongxiao Jia, Bingyu Li

This paper concerns cheaply computable formulas and bounds for the condition number of the TLS problem. For a TLS problem with data $A$, $b$, two formulas are derived that are simpler and more compact than the known results in the literature. One is derived by exploiting the properties of Kronecker products of matrices. The other is obtained by making use of the singular value decomposition (SVD) of $[A \,\,b]$, which allows us to compute the condition number cheaply and accurately. We present lower and upper bounds for the condition number that involve the singular values of $[A \,\, b]$ and the last entries of the right singular vectors of $[A \,\, b]$. We prove that they are always sharp and can estimate the condition number accurately by no more than four times. Furthermore, we establish a few other lower and upper bounds that involve only a few singular values of $A$ and $[A \,\, b]$. We discuss how tight the bounds are. These bounds are particularly useful for large scale TLS problems since for them any formulas and bounds for the condition number involving all the singular values of $A$ and/or $[A \ b]$ are too costly to be computed. Numerical experiments illustrate that our bounds are sharper than a known approximate condition number in the literature.

Zhongxiao Jia, Qingqing Zheng

We establish a general convergence theory of the Rayleigh--Ritz method and the refined Rayleigh--Ritz method for computing some simple eigenpair $(λ_{*},x_{*})$ of a given analytic regular nonlinear eigenvalue problem (NEP). In terms of the deviation $\varepsilon$ of $x_{*}$ from a given subspace $\mathcal{W}$, we establish a priori convergence results on the Ritz value, the Ritz vector and the refined Ritz vector. The results show that, as $\varepsilon\rightarrow 0$, there exists a Ritz value that unconditionally converges to $λ_*$ and the corresponding refined Ritz vector does so too but the Ritz vector converges conditionally and it may fail to converge and even may not be unique. We also present an error bound for the approximate eigenvector in terms of the computable residual norm of a given approximate eigenpair, and give lower and upper bounds for the error of the refined Ritz vector and the Ritz vector as well as for that of the corresponding residual norms. These results nontrivially extend some convergence results on these two methods for the linear eigenvalue problem to the NEP. Examples are constructed to illustrate the main results.

Zhongxiao Jia, Wenjie Kang

A sparse matrix is called double irregular sparse if it has at least one relatively dense column and row, and it is double regular sparse if all the columns and rows of it are sparse. The sparse approximate inverse preconditioning procedures SPAI, PSAI($tol$) and RSAI($tol$) are costly and even impractical to construct preconditioners for a large sparse nonsymmetric linear system with the coefficient matrix being double irregular sparse, but they are efficient for double regular sparse problems. Double irregular sparse linear systems have a wide range of applications, and 4.4\% of the nonsymmetric matrices in the Florida University collection are double irregular sparse. For this class of problems, we propose a transformation approach, which consists of four steps: (i) transform a given double irregular sparse problem into a small number of double regular sparse ones with the same coefficient matrix $\hat{A}$, (ii) use SPAI, PSAI($tol$) and RSAI($tol$) to construct sparse approximate inverses $M$ of $\hat{A}$, (iii) solve the preconditioned double regular sparse linear systems by Krylov solvers, and (iv) recover an approximate solution of the original problem with a prescribed accuracy from those of the double regular sparse ones. A number of theoretical and practical issues are considered on the transformation approach. Numerical experiments on a number of real-world problems confirm the very sharp superiority of the transformation approach to the standard approach that preconditions the original double irregular sparse problem by SPAI, PSAI($tol$) or RSAI($tol$) and solves the resulting preconditioned system by Krylov solvers.

Zhongxiao Jia

For the large-scale linear discrete ill-posed problem $\min\|Ax-b\|$ or $Ax=b$ with $b$ contaminated by a white noise, Lanczos bidiagonalization based LSQR and its mathematically equivalent CGLS are most commonly used. They have intrinsic regularizing effects, where the number $k$ of iterations plays the role of regularization parameter. However, hitherto there has been no answer to the long-standing fundamental concern of Björck and Eldén in 1979: {\em for which kinds of problems LSQR and CGLS can find best possible regularized solutions}? Here a best possible regularized solution means that it is at least as accurate as the best regularized solution obtained by the truncated singular value decomposition (TSVD) method or by standard-form Tikhonov regularization and cannot be improved under certain conditions. In this paper we make a detailed analysis on the regularization of LSQR for severely, moderately and mildly ill-posed problems. For the first two kinds of problems, we prove that LSQR finds best possible solutions at semi-convergence and the following results hold until semi-convergence: (i) the $k$-step Lanczos bidiagonalization always generates a near best rank $k$ approximation to $A$; (ii) the $k$ Ritz values always approximate the first $k$ large singular values of $A$ in natural order; (iii) the $k$-step LSQR always captures the $k$ dominant SVD components of $A$; (iv) the diagonals and subdiagonals of the bidiagonal matrices generated by Lanczos bidiagonalization decay as fast as the singular values of $A$. However, for the third kind of problem, the above results do not hold generally. We also analyze the regularization of the other two Krylov solvers LSMR and CGME, proving that LSMR has similar regularizing effects to LSQR for each kind of problem and both are superior to CGME. Numerical experiments confirm our theory on LSQR.

Zhongxiao Jia, Tianhang Liu

Under the hypothesis that the deviations of the desired eigenvectors of the matrix $A$ from the underlying subspace tend to zero, the Ritz vectors may not converge and have poor or little accuracy. This phenomenon is not unusual and particularly occurs when the associated Ritz values are close, which is independent of the eigenvalue distribution of $A$. For the (block) SS--RR methods, there are possibly {\em more} Ritz values that converge to the same desired eigenvalue(s) counting multiplicity in the region of interest, meaning that some of the Ritz values must be spurious and the corresponding residual norms of the Ritz pairs may not be small. Consequently, the (block) SS--RR methods including the CJ--SS--RR method cannot base on the corresponding residual norms to effectively identify if the Ritz values in the region are genuine or spurious. This paper proposes refined SS--RR, abbreviated as SS--RRR, methods based on the refined Rayleigh--Ritz projection that compute the eigenpairs of large matrices with the eigenvalues located in the given region. We present a new approach to accurately implement the RRR methods more efficiently than ever before for a general subspace.Exploiting the unconditional convergence of the refined Ritz vectors when the subspace is sufficiently accurate, we propose a tune-free removal approach to effectively remove spurious Ritz values with a rigorous theory supported, and develop a restarted CJ--SS--RRR algorithm. Numerical experiments show that the restarted CJ--SS--RRR algorithm is more efficient and effective than the restarted CJ--SS--RR algorithm.

Jinzhi Huang, Zhongxiao Jia

Three refined and refined harmonic extraction-based Jacobi--Davidson (JD) type methods are proposed, and their thick-restart algorithms with deflation and purgation are developed to compute several generalized singular value decomposition (GSVD) components of a large regular matrix pair. The new methods are called refined cross product-free (RCPF), refined cross product-free harmonic (RCPF-harmonic) and refined inverse-free harmonic (RIF-harmonic) JDGSVD algorithms, abbreviated as RCPF-JDGSVD, RCPF-HJDGSVD and RIF-HJDGSVD, respectively. The new JDGSVD methods are more efficient than the corresponding standard and harmonic extraction-based JDSVD methods proposed previously by the authors, and can overcome the erratic behavior and intrinsic possible non-convergence of the latter ones. Numerical experiments illustrate that RCPF-JDGSVD performs better for the computation of extreme GSVD components while RCPF-HJDGSVD and RIF-HJDGSVD suit better for that of interior GSVD components.

Zhongxiao Jia

For the Hermitian inexact Rayleigh quotient iteration (RQI), the author has established new local general convergence results, independent of iterative solvers for inner linear systems. The theory shows that the method locally converges quadratically under a new condition, called the uniform positiveness condition. In this paper we first consider the local convergence of the inexact RQI with the unpreconditioned Lanczos method for the linear systems. Some attractive properties are derived for the residuals, whose norms are $ξ_{k+1}$'s, of the linear systems obtained by the Lanczos method. Based on them and the new general convergence results, we make a refined analysis and establish new local convergence results. It is proved that the inexact RQI with Lanczos converges quadratically provided that $ξ_{k+1}\leqξ$ with a constant $ξ\geq 1$. The method is guaranteed to converge linearly provided that $ξ_{k+1}$ is bounded by a small multiple of the reciprocal of the residual norm $\|r_k\|$ of the current approximate eigenpair. The results are fundamentally different from the existing convergence results that always require $ξ_{k+1}<1$, and they have a strong impact on effective implementations of the method. We extend the new theory to the inexact RQI with a tuned preconditioned Lanczos for the linear systems. Based on the new theory, we can design practical criteria to control $ξ_{k+1}$ to achieve quadratic convergence and implement the method more effectively than ever before. Numerical experiments confirm our theory.

Zhongxiao Jia

For the Hermitian inexact Rayleigh quotient iteration (RQI), we present a new general theory, independent of iterative solvers for shifted inner linear systems. The theory shows that the method converges at least quadratically under a new condition, called the uniform positiveness condition, that may allow inner tolerance $ξ_k\geq 1$ at outer iteration $k$ and can be considerably weaker than the condition $ξ_k\leqξ<1$ with $ξ$ a constant not near one commonly used in literature. We consider the convergence of the inexact RQI with the unpreconditioned and tuned preconditioned MINRES method for the linear systems. Some attractive properties are derived for the residuals obtained by MINRES. Based on them and the new general theory, we make a more refined analysis and establish a number of new convergence results. Let $\|r_k\|$ be the residual norm of approximating eigenpair at outer iteration $k$. Then all the available cubic and quadratic convergence results require $ξ_k=O(\|r_k\|)$ and $ξ_k\leqξ$ with a fixed $ξ$ not near one, respectively. Fundamentally different from these, we prove that the inexact RQI with MINRES generally converges cubically, quadratically and linearly provided that $ξ_k\leqξ$ with a constant $ξ<1$ not near one, $ξ_k=1-O(\|r_k\|)$ and $ξ_k=1-O(\|r_k\|^2)$, respectively. Therefore, the new convergence conditions are much more relaxed than ever before. The theory can be used to design practical stopping criteria to implement the method more effectively. Numerical experiments confirm our results.

Zhongxiao Jia, Datian Niu

The harmonic Lanczos bidiagonalization method can be used to compute the smallest singular triplets of a large matrix $A$. We prove that for good enough projection subspaces harmonic Ritz values converge if the columns of $A$ are strongly linearly independent. On the other hand, harmonic Ritz values may miss some desired singular values when the columns of $A$ almost linearly dependent. Furthermore, harmonic Ritz vectors may converge irregularly and even may fail to converge. Based on the refined projection principle for large matrix eigenproblems due to the first author, we propose a refined harmonic Lanczos bidiagonalization method that takes the Rayleigh quotients of the harmonic Ritz vectors as approximate singular values and extracts the best approximate singular vectors, called the refined harmonic Ritz approximations, from the given subspaces in the sense of residual minimizations. The refined approximations are shown to converge to the desired singular vectors once the subspaces are sufficiently good and the Rayleigh quotients converge. An implicitly restarted refined harmonic Lanczos bidiagonalization algorithm (IRRHLB) is developed. We study how to select the best possible shifts, and suggest refined harmonic shifts that are theoretically better than the harmonic shifts used within the implicitly restarted Lanczos bidiagonalization algorithm (IRHLB). We propose a novel procedure that can numerically compute the refined harmonic shifts efficiently and accurately. Numerical experiments are reported that compare IRRHLB with five other algorithms based on the Lanczos bidiagonalization process. It appears that IRRHLB is at least competitive with them and can be considerably more efficient when computing the smallest singular triplets.