Search

The randomized block Kaczmarz method aims to solve linear system A x = b by iteratively projecting the current estimate to the solution space of a subset of the constraints. Recent works analyzed the method for the overdetermined least-squares problem, showing expected linear rate of convergence to the ordinary least squares solution with the use of a randomized control scheme to choose the subset at each step. This paper considers the natural follow-up to the randomized control scheme—greedy strategies like the greedy probability criterion and the almost-maximal residual control, and show convergence to a least-squares least-norm solution. Numerical results show that our proposed methods are feasible and have faster convergence rate than the randomized block Kaczmarz method.

The block Gauss–Seidel algorithm can significantly outperform the simple randomized Gauss–Seidel algorithm for solving overdetermined least-squares problems since it moves a large block of columns rather than a single column into working memory. Here, with the help of the maximum residual rule, we construct a two-step Gauss–Seidel (2SGS) algorithm, which selects two different columns simultaneously at each iteration. As a natural extension of the 2SGS algorithm, we further propose a multi-step Gauss–Seidel algorithm, that is, the maximum residual block Gauss–Seidel (MRBGS) algorithm for solving overdetermined least-squares problems. We prove that these two different algorithms converge to the unique solution of the overdetermined least-squares problem when its coefficient matrix is of full column rank. Numerical experiments on Gaussian models as well as on 2D image reconstruction problems, show that 2SGS is more effective than the greedy randomized Gauss–Seidel algorithm, and MRBGS apparently outperforms both the greedy and randomized block Gauss–Seidel algorithms in terms of numerical performance.

The PageRank algorithm for determining the importance of Web pages has become a central technique in Web search. we propose a new method to speed up the convergence performance for computing PageRank when the damping factor is close to one, called as GMRES-Power, which is based on a periodic combination of the power method with the GMRES algorithm. The description and convergence analysis of the new algorithm are discussed in detail. Numerical results are reported to confirm the efficiency of the new algorithm.

We propose a randomized sampling Kaczmarz algorithm for the solution of very large systems of linear equations by introducing a maximal sampling probability control criterion, which is aimed at grasping the largest entry of the absolute sampling residual vector at each iteration. This new method differs from the greedy randomized Kaczmarz algorithm, which needs not to compute the residual vector of the whole linear system to determine the working rows. Numerical experiments show that the proposed algorithm has the most significant effect when the selected row number, i.e, the size of samples, is equal to the logarithm of all rows. Finally, we extend the randomized sampling Kaczmarz to signal reconstruction problems in compressed sensing. Signal experiments show that the new extended algorithm is more effective than the randomized sparse Kaczmarz method for online compressed sensing.

The function-valued Padé-type approximation (2DFPTA) is used to solve two-dimensional Fredholm integral equation of the second kind. In order to compute 2DFPTA, a triangle recursive algorithm based on Sylvester identity is proposed. The advantage of this algorithm is that, in the process of calculating 2DFPTA to avoid the calculation of the determinant, it can start from the initial value, from low to high order, and gradually proceeds. Compared with the original two methods, the numerical examples show that the algorithm is effective.

Tensor exponential function is an important function that is widely used. In this paper, tensor Pade´-type approximant (TPTA) is defined by introducing a generalized linear functional for the first time. The expression of TPTA is provided with the generating function form. Moreover, by means of formal orthogonal polynomials, we propose an efficient algorithm for computing TPTA. As an application, the TPTA for computing the tensor exponential function is presented. Numerical examples are given to demonstrate the efficiency of the proposed algorithm.

A new relaxed PSS-like iteration scheme for the nonsymmetric saddle point problem is proposed. As a stationary iterative method, the new variant is proved to converge unconditionally. When used for preconditioning, the preconditioner differs from the coefficient matrix only in the upper-right components. The theoretical analysis shows that the preconditioned matrix has a well-clustered eigenvalues around (1, 0) with a reasonable choice of the relaxation parameter. This sound property is desirable in that the related Krylov subspace method can converge much faster, which is validated by numerical examples.

In this paper, based on the iteration framework (Tian et al., 2019) and relaxed two-step splitting (RTSS) iteration method (Xie and Ma, 2018), we present two relaxed iteration methods for solving the PageRank problem, which are the relaxed generalized inner–outer (RGIO) and relaxed generalized two-step splitting (RGTSS) iteration methods, respectively. Next, their overall convergence properties are analyzed in detail, and choices of the parameters in these algorithms are also discussed. Finally, several numerical examples are given to illustrate the effectiveness of the proposed algorithms.

In this paper, an improved block splitting preconditioner for a class of complex symmetric indefinite linear systems is proposed. By adopting two iteration parameters and the relaxation technique, the new preconditioner not only remains the same computational cost with the block preconditioners but also is much closer to the original coefficient matrix. The theoretical analysis shows that the corresponding iteration method is convergent under suitable conditions and the preconditioned matrix can have well-clustered eigenvalues around (0,1) with a reasonable choice of the relaxation parameters. An estimate concerning the dimension of the Krylov subspace for the preconditioned matrix is also obtained. Finally, some numerical experiments are presented to illustrate the effectiveness of the presented preconditioner.

In this paper, an accelerated Jacobi-gradient based iterative (AJGI) algorithm for solving Sylvester matrix equations is presented, which is based on the algorithms proposed by Ding and Chen [6], Niu et al. [18] and Xie et al. [25]. Theoretical analysis shows that the new algorithm will converge to the true solution for any initial value under certain assumptions. Finally, three numerical examples are given to verify the eficiency of the accelerated algorithm proposed in this paper.

For nonsymmetric saddle point problems, Pan et al. (Appl Math Comput 172:762–771, 2006) proposed a deteriorated positive-definite and skew-Hermitian splitting (DPSS) preconditioner. In this paper, a variant of the DPSS preconditioner is proposed to accelerate the convergence of the associated Krylov subspace methods. The new preconditioner is much closer to the coefficient matrix than the DPSS preconditioner. The spectral properties of the new preconditioned matrix are analyzed. Theorem which provides the dimension of the Krylov space for the preconditioned matrix is obtained. Numerical experiments of a model Navier–Stokes problem are presented to illustrate the effectiveness of the new preconditioner.